W dniu czwartek, 28 marca 2013 17:33:04 UTC+1 użytkownik firr napisał:
> robiona na zwyklej tablicy to jej rozmiar jest dosyc bolasty i jest
> odpowiedni wielkosci hasza
> np hasz 20 bitów - tablica 1 MB ???
Jeśli ilość entry-points w hash-table jest 2^N, to można zrobić
mikro-optymalizację:
hash_table[ makeKey( data ) & ((1<<N)-1) ] = data;
Jeśli rozmiar jest inny, to nie ma problemu, można tak:
hash_table[ makeKey( data ) % inny_roziar ] = data;



> 2) drugi problem - jak z danym haszem jest
> kojarzona lista sów, powiedzmy ze krzesło i hipopotam daja jednego hasza
> 777889 to chyba musza siedziec tam obok w postaci listy ?
W tym zadaniu nie są potrzebne w ogóle żadne listy.

key = makeKey( "hipopotam" );
entry = key % hash_size;
C = 1;
while( ! isEmpty( hash_table[entry] ) )
entry = (entry+C) % hash_size;
hash_table[ entry ] = "hipopotam";


Można C obliczać drugą funkcją hash:

key = makeKey( "hipopotam" );
entry = key % hash_size;
C = makeKey2( "hipopotam" );
while( ! isEmpty( hash_table[entry] ) )
entry = (entry+C) % hash_size;
hash_table[ entry ] = "hipopotam";



Pozdrawiam