HashSet Implementierung

[j-frost]

Hallo Leute,

ich habe folgende Methode geschrieben:

	public boolean hasValue(int value) {
		int hash = hash(value);
		Integer element = list.get(hash);
		//return (element != null);
		if (element == null)
			return false;
		else 
			return true;
		
	}

Warum liefert die immer true?

LG,

j-frost

 

[Haave]

Hab noch nicht so recht nen Plan, aber: was ist denn hash() für eine Methode? Was macht die mit value?

[JAVA=2]int hash = hash(value);[/code]

 

[Gast2]

Warum liefert die immer true?

Weil element nie null ist, warum ist das so? Dazu musst du uns noch sagen was liste ist oder was hash() macht.

 

[j-frost]

Hab noch nicht so recht nen Plan, aber: was ist denn hash() für eine Methode? Was macht die mit value?

[JAVA=2]int hash = hash(value);[/code]

Naja, vom Prinzip her soll hash(int) irgendwann die Hashfunktion sein. Allerdings ist sie bis jetzt nur

	private int hash(int x) {
		int m = n - 1; // Something's wrong. Can you see what? x_X 
		return x % m;
	}

und ich bin mir ziemlich sicher, dass das so nicht stimmt...

 

[Haave]

	private int hash(int x) {
		int m = n - 1; // Something's wrong. Can you see what? x_X 
		return x % m;
	}

Das wird sich schon nicht kompilieren lassen, weil du n nirgendwo deklarierst

Naja, vom Prinzip her soll hash(int) irgendwann die Hashfunktion sein.

Ich weiß ja nicht genau, was du vorhast, aber wäre es nicht u.U. sinnvoller, gleich die eingebaute hashCode()-Methode zu überschreiben?

 

[ARadauer]

ich würde mal den ganzen code posten... sonst dauert das noch die ganze nacht...

 

[j-frost]

ich würde mal den ganzen code posten... sonst dauert das noch die ganze nacht...

Sorry, glaub auch, dass das das Beste ist. Hier isser:

package blatt7_aufgabe1;

import java.util.LinkedList;

public class MyHashSet implements HashInterface {

	int n;
	LinkedList<Integer> list = new LinkedList<Integer>();
		
	public MyHashSet(int size) {
		n = size;
		for(int i = 0; i < n; i++) {
			list.add(null);     // Generating n buckets... is that right? 
		}
	}

	private int hash(int x) {
		int m = n - 1; // Something's wrong. Can you see what? x_X 
		return x % m;
	}

	public void insert(int value) {	
		if (!(hasValue(value))) {
			list.remove(hash(value));
			list.add(hash(value), value);
		}
	}

	public void delete(int value) {	
		if (hasValue(value)) {
			list.remove(hash(value));
		}
	}

	public boolean hasValue(int value) {
		int hash = hash(value);
		Integer element = list.get(hash);
		//return (element != null);
		if (element == null)
			return false;
		else 
			return true;
		
	}

	public double[] statistics() {
		// needs implementation desperately... 
		return null;
	}

}

 

[Gast2]

Funzt bei mir eig. ohne Probleme.
Zeig mal deinen Testcode.

 

[j-frost]

Funzt bei mir eig. ohne Probleme.
Zeig mal deinen Testcode.

Testcode:

package blatt7_aufgabe1;

public class TestHashSet {

	public static void main(String[] args) {
		int n = 10000;
		
		MyHashSet myHashSet = new MyHashSet(n);
		
		for(int i = 0; i < n; i++) {
			myHashSet.insert(i);
		}
		/*
		System.out.print("minimale Kollisionsliste:"+hashSet.statistics()[0]);
		System.out.print("maximale Kollisionsliste:"+hashSet.statistics()[1]);
		System.out.print("Mittelwert Kollisionslänge:"+hashSet.statistics()[2]);
		System.out.print("Standardabweichung Kollisionslänge:"+hashSet.statistics()[3]);
		*/
		System.out.println(myHashSet.hasValue(1234));
		System.out.println(myHashSet.hasValue(0));
		System.out.println(myHashSet.hasValue(9999));
		System.out.println(myHashSet.hasValue(10000));
		System.out.println(myHashSet.hasValue(10001));
		System.out.println(myHashSet.hasValue(20001));
	
	}

}

 

[ARadauer]

// Generating n buckets... is that right?

ja

// Something's wrong. Can you see what? x_X

mhn ok...
ich würd das -1 weg lasssen...
schreiben.. mach dir eine print methode die dir die liste ausgibt..

 public void print(){
    	for(int i = 0; i < list.size(); i++)
    		System.out.println(i+" "+list.get(i));
    }

dann siehst du was passiert..

public static void main(String[] args) {
		MyHashSet set = new MyHashSet(5);
		System.out.println(set.hasValue(3));
		set.insert(2);
		set.insert(3);
		set.insert(4);
                         set.insert(5);
		
		set.print();
	}

0 5
1 null
2 2
3 3
4 4

es kommt halt drauf an was man bei 5 elementen vor hast


also grundsätzlich funktioniert das mit hashvalue schon..
hier musst du aufpassen..
list.remove(hash(value));
achtung... du vernichtest dein bucket. also wenn du remove machst und du hast 2, 3, 4 drinnen, machst ein remove auf 3 dann ist 4 anstelle von 3... du willst eher 3 auf null setzen..

 

[Gast2]

Also du füllst dein komplettes Hashset, hast ne Hashfunktion die dir lediglich mit modulo die hashs berechnet. Und dann kommts dir komisch vor dass alle prüfungen auf hasValue true ergeben?

EDIT:
Du solltest anstatt der Liste ne Map<Integer, Integer> nehmen und die Hashfunktion gegen eine geignetere (z.b. von Eclipse generierte) austauschen, dann solltest du weniger Kollisionen haben und deine Tests sollten hinhaun

 

[j-frost]

hier musst du aufpassen..
list.remove(hash(value));
achtung... du vernichtest dein bucket. also wenn du remove machst und du hast 2, 3, 4 drinnen, machst ein remove auf 3 dann ist 4 anstelle von 3... du willst eher 3 auf null setzen..

Ja richtig, ich muss an der Stelle hash(value) das element = null; setzen. Danke

Also du füllst dein komplettes Hashset, hast ne Hashfunktion die dir lediglich mit modulo die hashs berechnet. Und dann kommts dir komisch vor dass alle prüfungen auf hasValue true ergeben?

EDIT:
Du solltest anstatt der Liste ne Map<Integer, Integer> nehmen und die Hashfunktion gegen eine geignetere (z.b. von Eclipse generierte) austauschen, dann solltest du weniger Kollisionen haben und deine Tests sollten hinhaun

Ich hab mir jetzt mal gedacht, dass ich ein array mache, wo LinkedList<Integer>'s drin sind und Integer. Bloß weiß ich nicht, wie ich das abfragen soll. Und warum soll ich 'ne Map nehmen? Das kenn' ich gar nicht. Wie funktioniert das?

Also was ich bis jetzt geschaffen habe ist:

package blatt7_aufgabe1;

import java.util.LinkedList;

public class MyHashSet implements HashInterface {

	int n;
	Object[] array;
	
	public MyHashSet(int size) {
		n = size;
		for(int i = 0; i < n; i++) {
			array[i] = null;
		}
	}

	private int hash(int x) {
		int m = n; // Something's wrong. Can you see what? x_X 
		return x % m;
	}

	public void insert(int value) {	
		if (!(hasValue(value))) {
			array[hash(value)] = value;
		}
		else if (hasValue(value)) {
			LinkedList<Integer> foo = new LinkedList();
			foo.add(value);
                        // TODO write foo into the array 
		}
	}

	public void delete(int value) {	
		/*if (hasValue(value)) {
			list.remove(hash(value));
		}*/
	}

	public boolean hasValue(int value) {
		Object element = array[hash(value)];
		if (element == null) 
			return false;
		/* if (element an Integer)
		 * 		if (element == value)
		 * 			return true;
		 * else if (element a LinkedList<Integer>)
		 * 		if (element.contains(value)
		 * 			return true;
		 * else 
		 * 		return false;
		*/
	}

	public double[] statistics() {
		// needs implementation desperately... 
		return null;
	}

}

Bloß den groß auskommentierten Teil kann ich nicht implementieren. Keine Ahnung wie.

 

[Gast2]

Ich hab mir jetzt mal gedacht, dass ich ein array mache, wo LinkedList<Integer>'s drin sind und Integer. Bloß weiß ich nicht, wie ich das abfragen soll. Und warum soll ich 'ne Map nehmen? Das kenn' ich gar nicht. Wie funktioniert das?

Erstmal zum warum:
Du hast in deinem Array n mögliche Keys. Wenn du deine Hashfunktion auf die keys (0...n-1) abbildest dann bekommst du sehr viele Kollisionen , und das ist in ner hashmap immer mist.
Nimmst du ne Map<Integer, Integer> dann hast du als möglichen Wertebereich den Wertebereich Integer.MIN_VALUE bis Integer.MAX_VALUE. Mit ner geschickten Hashfunktion kannst du damit dann deine anzahl an Kollisionen verringern und bekommst somit auch genauere Werte bei hasValue.
Zur Anwendung:
einfach mal googlen

 

[j-frost]

Erstmal zum warum:
Du hast in deinem Array n mögliche Keys. Wenn du deine Hashfunktion auf die keys (0...n-1) abbildest dann bekommst du sehr viele Kollisionen , und das ist in ner hashmap immer mist.
Nimmst du ne Map<Integer, Integer> dann hast du als möglichen Wertebereich den Wertebereich Integer.MIN_VALUE bis Integer.MAX_VALUE. Mit ner geschickten Hashfunktion kannst du damit dann deine anzahl an Kollisionen verringern und bekommst somit auch genauere Werte bei hasValue.
Zur Anwendung:
einfach mal googlen

OK, gut, aber da ich nur Zahlen abspeichern will kann ich doch auch 'n Array von LinkedLists machen? Denn auf dem Aufgabenblatt steht (diesmal zum ersten Mal) "Sie dürfen java.util.LinkedList verwenden". Ich gehe also davon aus, dass eine Lösung LinkedLists verwenden soll und sonst eher nichts, da keine Aussage darüber gemacht wurde, ob andere java.*s benutzt werden dürfen. Und in dieser Veranstaltung zählen die Blätter schon auf die finale Note drauf. D.h. ich will da kein Risiko eingehen.

Ich bastel noch ein bisschen und poste dann mal wieder 'ne geupdatete Version. Hoffentlich ist die dann auch fertig Ansonsten hoffe ich, hier weiter Hilfe zu erhalten, ihr seid super(,) Leute! (nur so nebenbei)

LG,

j-frost

 

[Landei]

Nebenbei gesagt kräuseln sich mir bei

        if (element == null)
            return false;
        else 
            return true;

die Fußnägel. Das schreibt man so:

      return element != null;

 

[j-frost]

OK, danke für alle Tips bis hierher. Ich hab's jetzt mal so gemacht, hoffe, das findet eure Zustimmung. [edit: jetzt müsste auch die statistics() so stimmen] Findet noch wer 'nen Fehler? Ansonsten halt close, ne? ^^

package blatt7_aufgabe1;
 
import java.util.LinkedList;
 
public class MyHashSet implements HashInterface {
 
    int n;
    LinkedList[] array;
    
    public MyHashSet(int size) {
        n = size;
        array = new LinkedList[n];
        for(int i = 0; i < n; i++) {
            array[i] = null;
        }
    }
 
    private int hash(int x) {
        int m = n; // Something's wrong. Can you see what? x_X 
        return x % m;
    }
 
    public void insert(int value) { 
        if (!(hasValue(value))) {
			if ((array[hash(value)]) != null)
				array[hash(value)].add(value);
			else {
				array[hash(value)] = new LinkedList<Integer>();
				array[hash(value)].add(value);
			}
        }
    }
 
    public void delete(int value) { 
    	Integer valueObj = value;
        if (hasValue(value)) {
            array[(hash(value))].remove(valueObj);
        }
    }
 
    public boolean hasValue(int value) {
        LinkedList<Integer> list = array[hash(value)];
        if (list != null)
        	return list.contains(value);
        return false;
    }
 
    public double[] statistics() {
    	double min_size = Integer.MAX_VALUE, max_size = 0, mean_size = 0, deviation = 0;
    	for(int i = 0; i < n; i++) {
			if (array[i] != null) {
				int size = array[i].size();
				if (size < min_size)
					min_size = size;
				if (size > max_size)
					max_size = size;
				mean_size += size;
			}
		}
		mean_size /= n;
		for (int i = 0; i < n; i++) {
			if (array[i] != null) {
				int size = array[i].size();
				deviation += Math.pow(size - mean_size, 2);
			}
		}
    	deviation /= n;
    	deviation = Math.sqrt(deviation);
        double[] result = new double[4];
        result[0] = min_size;
        result[1] = max_size;
        result[2] = mean_size;
        result[3] = deviation;
        return result;
    }
 
}

edit:

Nebenbei gesagt kräuseln sich mir bei

        if (element == null)
            return false;
        else 
            return true;

die Fußnägel. Das schreibt man so:

      return element != null;

Ja, ich weiß, das ist ziemlich hässlich, aber darüber steht ja auskommentiert dasselbe, was du wolltest. Ich war mir nur kurz mal nicht sicher, weil irgendwie gar nichts ging, und hab' dann erstmal foolproof getestet.

 

[Landei]

Ja, ich weiß, das ist ziemlich hässlich, aber darüber steht ja auskommentiert dasselbe, was du wolltest. Ich war mir nur kurz mal nicht sicher, weil irgendwie gar nichts ging, und hab' dann erstmal foolproof getestet.

Ach, hatte ich überlesen...