Java Hashtable

[philBerlin]

Hallo hallo,

bei der Initialisierung einer Hashtable mit:

Hashtable<String, String> hash = new Hashtable<String, String>(100);

Wie groß ist jetzt die Hashtable? Ist diese dann schon um den Vergrößerungsfaktor größer, oder muss man den selber vorher berechnen...

Viele Grüße
Phil

 

[MeinerEiner_80]

Moin!
100 Einträge, Vergrösserungsfaktor 0.75 ..
Aber das steh auch alles in der Doku, u.a. auch das man den Vergrösserungsfaktor explizit mitangeben kann..

*grüssle*
MeinerEiner

 

[philBerlin]

Ok, also hat die Table eigentlich eine Größe von 125 und reorganisiert sich wenn sie ganz voll ist? Oder hat die Tabelle eine Größe von 100 und reorganisiert sich wenn Sie zu 75% voll ist?

 

[Matthias Reitinger]

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

Grüße,
Matthias

 

[philBerlin]

Also um es an einem Beispiel zu veranschaulichen, nehmen wir mal an ich wollte eine Liste mit der Größe von 100 Elementen in einer Hashtable speichern, und ich würde die Hashtable mit der Größe der Liste initialisieren, dann würde die Hashtable sich nach dem 75. Eintrag reorganisieren, richtig? Dann müsste ich die Hashtable so initialisieren, dass ich die 100 Einträge ohne Reorganisierung reinbekomme, also mit dem Faktor 1,25 multiplizieren, wenn ich die Formel jetzt richtig umgestellt habe... Demnach initialisiere ich die Hashtable mit:
liste.size() * 1.25 um alle Listenelemente ohne Reorganisation zu speichern.
Ich hoffe ich hab das jetzt so richtig verstanden...

Was mich jetzt aber vollkommen verwirrt ist das Zitat!! Dort steht:

Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially.

Wenn man sich aber das Kommentar und den Quelltext von "put" ansieht, dann steht da:

@return the previous value of the specified key in this hashtable

	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		V old = e.value;
		e.value = value;
		return old;
	    }
	}

Das sieht mir eher danach aus, dass der alte Wert gnadenlos rausgeworfen wird. Noch anschaulicher ist putAll:

Copies all of the mappings from the specified map to this hashtable. These mappings will replace any mappings that this hashtable had for any of the keys currently in the specified map.

Hmmm, hmmmm, hmmm hab gerade noch etwas darüber nachgedacht, ob ich mich da nicht gerade komplett irre... ick wees et nüscht

 

[philBerlin]

Sorry, die richtige Formel wäre:

Initialwert = liste.size() / faktor

also in unserem Beispiel würde 133,33.. sprich 134 rauskommen...

 

[MeinerEiner_80]

Moin!

Was mich jetzt aber vollkommen verwirrt ist das Zitat!! Dort steht:

Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially.

Wenn man sich aber das Kommentar und den Quelltext von "put" ansieht, dann steht da:

    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
        }
    }

"Gnadenlos rausgeworfen" wird der Wert nur, wenn sowohl hash Wert gleich sind, als auch beide keys gleich sind im Sinne von der equals Methode.
Falls 2 Objekte equals gleich sind, dann sollte auch der hash Wert gleich sein. Umgekehrt muss dies aber nicht so sein, auch wenn es vielfach so ist.. D.h., sind 2 Objekte equals gleich, aber haben unterschiedliche Hash Werte, so werden beide im selben "Bucket" gespeichert..
Dazu auch, Kommentar zur Methode hashCode in der Klasse Object:

Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.

Mich würde mal interessieren, wieso du dich denn da so detailliert für interessierst?

*grüssle*
MeinerEiner