[Alg] HashTable vs HashTree

[Daos]

Overal om je heen zie je hashtables, maar de hashtree is vrij zeldzaam.

De informatie die ik nu heb:

HashTable:
De Hash is index in tabel. In tabel staan linked lists met de objecten.
Voordelen:
klein: 2 pointers per object
snel: als er genoeg ruimte is in tabel heb je O(1).
Nadelen:
formaat past zich niet aan en daardoor traag: 100000 elementen in tabel met 5 plaatsen geeft O(n)
of ruimte verspillend: 5 elementen in tabel met 100000 plaatsen = 99.995 % niet gebruikt.

HashTree:
De Hash wordt gebruikt om het object in een boom te plaatsen. Het object komt bij linker kind als hash kleiner is en bij rechter als deze groter is. Als er al wat staat, dan zoek je bij dat kind verder.
Voordelen:
formaat is flexibel: meer elementen => grotere boom
snelheid kan gegarandeerd worden: gebruik 2-3 tree ipv binairy tree. Altijd O(log(N))
Nadelen:
hash moet uniek zijn
groot: hash + 3 pointers (1 naar object + 2 kinderen)


Waarom wordt bijna altijd die tabel gebruikt? Een boom werkt volgens mij beter. Zeker als je een variabele hoeveelheid data hebt. Maar compilers gebruiken allemaal een tabel voor de identifiers

[Alarmnummer]

Daos schreef op woensdag 13 april 2005 @ 16:00:
Overal om je heen zie je hashtables, maar de hashtree is vrij zeldzaam.

De informatie die ik nu heb:

HashTable:
De Hash is index in tabel. In tabel staan linked lists met de objecten.
Voordelen:
klein: 2 pointers per object
snel: als er genoeg ruimte is in tabel heb je O(1).
Nadelen:
formaat past zich niet aan en daardoor traag: 100000 elementen in tabel met 5 plaatsen geeft O(n)
of ruimte verspillend: 5 elementen in tabel met 100000 plaatsen = 99.995 % niet gebruikt.

Hashtables/maps doen een rehash

hash moet uniek zijn
groot: hash + 3 pointers (1 naar object + 2 kinderen)

Unieke hash is wel ff iets complexer dan een 'het mag ook eens niet uniek zijn' hash.

[ Voor 6% gewijzigd door Alarmnummer op 13-04-2005 16:08 ]

[Infinitive]

Nadelen:
formaat past zich niet aan en daardoor traag: 100000 elementen in tabel met 5 plaatsen geeft O(n)
of ruimte verspillend: 5 elementen in tabel met 100000 plaatsen = 99.995 % niet gebruikt.

Dat is niet helemaal waar... als de hashtable bij elke resize zich verdubbeld, dan is inserten nog steeds O(1) als je alle inserts tegelijk beschouwd.

[Daos]

Alarmnummer schreef op woensdag 13 april 2005 @ 16:06:
[...]

Hashtables/maps doen een rehash

Kan je dat zomaar doen? Je hebt dan toch ook een andere hashfunctie nodig? Bij een tabel is de hash namelijk je index. Of maak je een grote hash (veel bits) en gebruik je een deel hiervan als index?

[Soultaker]

de 'kosten' van opnieuw alloceren ongeveer lineair zijn met het aantal elementen dat er in zit (wat me wel logisch lijkt; 10 MB alloceren duurt ongeveer twee keer zo lang als 5 MB alloceren), dan kost het toevoegen van een element O(N) (worst-case) en O(log N) (average&amortized). Dat is nog steeds prima, maar geen O(1).

Verder zie ik het nut van hash tables in een boom gebruiken niet echt; maak dan je objecten comparable zodat je ze echt kan ordenen en dan kun je bovendien efficiënte range queries doen (geef me alle objecten groter dan X en kleiner dan Y; geef me het grootste element kleiner dan Z; enzovoorts). Het idee is waarschijnlijk dat eenmaal een hashcode genereren en daarna daarmee vergelijken iets efficiënter is, maar of het netto heel veel scheelt betwijfel ik en het verlies in functionaliteit is aanzienlijk.

Als je alleen maar elementen wil toevoegen en verwijderen, of wil kunnen zien of een element al is toegevoegd, dan is een hash table gewoon voldoende. Een hash tree is nauwelijks ruimte-efficiënter omdat elke allocatie overhead produceert (en je hebt ook nog eens meer links tussen nodes dan met een single linked hash table).

Daos schreef op woensdag 13 april 2005 @ 16:29:
Kan je dat zomaar doen? Je hebt dan toch ook een andere hashfunctie nodig? Bij een tabel is de hash namelijk je index. Of maak je een grote hash (veel bits) en gebruik je een deel hiervan als index?

Kort samengevat: ja. (Als je het goed doet gebruik je natuurlijk niet zomaar een deel van de code, maar hash je de hele code naar een kortere code, zodat de kwaliteit van de hash code niet nodeloos achteruit gaat.)

[ Voor 84% gewijzigd door Soultaker op 13-04-2005 16:35 ]

[Alarmnummer]

Daos schreef op woensdag 13 april 2005 @ 16:29:
[...]


Kan je dat zomaar doen?

Hoef je niet zelf te doen. Zo gauw de loadfactor wordt overschreden, dan wordt dit automatisch gedaan. (Een op de zoveel inserts is dus erg traag omdat er een rehash gedaan moet worden).

Je hebt dan toch ook een andere hashfunctie nodig? Bij een tabel is de hash namelijk je index. Of maak je een grote hash (veel bits) en gebruik je een deel hiervan als index?

Uhh... Hashtables hebben meestal een array met buckets. Je komt bij de juiste bucket uit door bij n buckets, hashcode mod n te gaan doen. Dus bij hashcode 20 en 18 buckets, kom je bij bucket 2 (20 mod 18 = 2) uit.

[Daos]

Soultaker schreef op woensdag 13 april 2005 @ 16:31:
...

Verder zie ik het nut van hash tables in een boom gebruiken niet echt; maak dan je objecten comparable zodat je ze echt kan ordenen en dan kun je bovendien efficiënte range queries doen (geef me alle objecten groter dan X en kleiner dan Y; geef me het grootste element kleiner dan Z; enzovoorts). Het idee is waarschijnlijk dat eenmaal een hashcode genereren en daarna daarmee vergelijken iets efficiënter is, maar of het netto heel veel scheelt betwijfel ik en het verlies in functionaliteit is aanzienlijk.
...

Stel je data is al een soort boom. Van een paar deelbomen maak je een nieuwe boom en wil je deze ergens in de grote zetten. Om ruimte te sparen of bij een bewerking wil je kijken of deze nieuwe deelboom al ergens in de grote boom bestaat.

Als je het zonder hashes doet:
N elementen in grote boom. Deelboom heeft volgens mij gemiddeld O(N) elementen.
Vergelijken nieuwe met alle deelbomen kost volgens mij N * O(N) = O(N^2).

Met hashes:
Elke deelboom heeft unieke hash. De hash kan je berekenen uit de naam en hashes van de kinderen.
Opzoeken van deelboom in hashtable gaat met O(1).

Alarmnummer schreef op woensdag 13 april 2005 @ 16:34:

[...]

Uhh... Hashtables hebben meestal een array met buckets. Je komt bij de juiste bucket uit door bij n buckets, hashcode mod n te gaan doen. Dus bij hashcode 20 en 18 buckets, kom je bij bucket 2 (20 mod 18 = 2) uit.

Dus je maakt een grote hash en je gebruikt een deel hiervan als index om de juiste bucket te vinden.

[...]

Hoef je niet zelf te doen. Zo gauw de loadfactor wordt overschreden, dan wordt dit automatisch gedaan. (Een op de zoveel inserts is dus erg traag omdat er een rehash gedaan moet worden).

Ik moet me er dus niet druk om maken en een taal zoals Java gebruiken.

[MSalters]

Alarmnummer schreef op woensdag 13 april 2005 @ 16:34:
[...]
Hoef je niet zelf te doen. Zo gauw de loadfactor wordt overschreden, dan wordt dit automatisch gedaan. (Een op de zoveel inserts is dus erg traag omdat er een rehash gedaan moet worden).

Dat is de gangbare implementatie, maar ik dacht dat de nieuwe Dinkumware C++ hashcontainers aan incremental rehashing deden. Je hoeft niet altijd alle buckets leeg te kieperen en opnieuw te vullen, je kunt jezelf soms ook beperken tot overlopende buckets.

[Alarmnummer]

MSalters schreef op woensdag 13 april 2005 @ 17:36:
[...]

Dat is de gangbare implementatie, maar ik dacht dat de nieuwe Dinkumware C++ hashcontainers aan incremental rehashing deden. Je hoeft niet altijd alle buckets leeg te kieperen en opnieuw te vullen, je kunt jezelf soms ook beperken tot overlopende buckets.

Ik was ten onrechte uitgegaan van Java. Maar wat bedoel je met overlopende buckets? Buckets die mee groeien alhoewel de performance winst naar zijn grootje is? Of buckets die elementen kwijtraken?