frågor om Hashmap

Försöker få en förståelse för hur HashMap fungerar. Läst mig till dokumentationen och letat igenom källkoden men verkar inte hitta de bitar jag är intresserad av.

Säg att vi har skapar en HashMap med en egenskriven Klass som nyckel. Vad sker innuti hashmap, konverteras detta till en integer med någon funktion som "läser av minnesinnehållet i objectet" eller hur gör den för att kunna lagra datan och komma åt den på konstant tid?
Vi kan också ställa in loadfactor vilket antyder att den inre strukturen måste ha en datastruktur kopplad till varje inre nyckel.

Dvs min tanke var att hashmap läser av minnet, skapar ett hashvärde av detta. Till varje hashvärde har vi en annan datastruktur som innehåller alla element med det värdet. För att sedan skillja på objecten söks listan igenom efter det exakt tillståndet. På så vis så får vi utåt att varje nyckel endast pekar på ett objekt (förutsatt jag är dum nog att skicka in samma objekt flera gånger i vilket fall den raderas.

Är jag rätt ut? Hur fungerar det egentligen? Det jag helt enkelt vill få reda på hur den är uppyggd (en överblick) samt vara säker på att oavsett hur många objekt jag skickar in kommer de aldrig att kolidera även om den lir långsam pga av att den inre strukturen lagrar flera element i samma lista.


Försökt formulera mina fråger så tydligt som möjligt men kan se själv det är otydligt. Detta beror till stor del på att jag inte vet vad jag riktigt frågar efter.

En HashMap fungerar enligt samma principer som det som brukar kallas för hashtabeller. Det finns en hel del skrivet om dessa strukturer. En bra start är att läsa artikeln på wikipedia:
https://secure.wikimedia.org/wikipedia/en/wiki/Hash_table

Internt arbetar en HashMap med en stor array. För att veta vart ett värde ska placeras anropar den hashCode-funktionen hos nyckelobjektet. Indexet i arrayen är baserat på det värdet. Kan man räkna ut indexet på konstant tid kan man även placera det på rätt plats i arrayen på konstant tid, förutsatt att man inte har några kollisioner.

Har inte så jättebra koll på vad loadfactorn, men varje plats i arrayen består i alla fall av en länkad lista. Varför dessa finns och hur de används verkar du i stora drag förstått.

Det är svårt att helt skydda sig från kollisioner. Har man valt bra hashfunktioner bör risken att få för många kollisioner vara rätt så låg. I idealfallet vill man att det ska finnas högst ett element i varje länkad lista.

Tycker faktiskt källkoden talar klarspråk:
[PHP] public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
[/PHP]

Tack, svaret på min första fråga. Lyckades tillslut lokalisera den också, var en statisk klass som hette Entry som fanns gömd inuti hashmap.

Tack, precis koden jag letade efter. Tycker det är riktigt svårt att hitta den relevanta delen när den är gömd inuti så många dokumentationskommentarer. (som visserligen är väldigt trevligt när man vill läsa dokumentationen men inte när man letar kod)

Lyckades tillslut även lokalisera equals i Object vilket endast returnerar true om det är samma object (alltså samma som (k = e.key) == key förutsatt jag inte överlagrat equals.)
Enda tråkiga var att hashcode i object bara var en "pure virtual function/interface" och själva implementationen sköttes olika på olika VM. Får göra antagandet att den ger en någorlunda vettig spridning alternativt skriva min egen pseubdoslumpgenerator för att ge en hashcode.

Slutsats: Tack du besvarade min fråga!