Cuckoo hashing

Cuckoo hashing. Les fleches mostren l'ubicació alternativa de cada clau. Un nou element s'inserta en el lloc de movent A a la seua ubicació alternativa, actualment ocupat per B i B en moviment a la seua ubicació alternativa que es troba actualment disponible. L'inserció d'un nou element en l'ubicació d'H no tindria èxit: H és part d'un cicle (junt en W), el nou element seria expulsat de nou

Cuckoo Hashing (hash del cuco) és un estructura de senyes usada en la programació informàtica per a la resolució de colisions hash dels valors de la funció de hash en una Taula, en case pijor constant en temps de busca. El nom deriva del comportament d'algunes espècies de cuculidae, a on la cría del cuco espenta els atres ous o crío del niu quan incuba; análogamente, l'inserció d'una nova clau en una taula cuckoo hashing pot espentar una clau més per a una ubicació diferent en la taula.

Història

Cuckoo hashing va ser descrita per primera volta per Rasmus Pagh i Flemming Friche Rodler en 2001.

Teoria

L'idea bàsica és usar dos funcions hash en lloc de només una. Açò proporciona dos possibles ubicacions en la taula hash per a cada clau única. En una de les variants d'us comú de l'algoritme, la taula hash es dividix en dos taules més chicotetes d'igual tamany, i cada funció hash proporciona un índex en una d'estes dos taules.

Quan s'inserta una nova clau, un algoritme voraç és usat per a insertar el duplicat de la clau en una de les seues dos possibles ubicacions, "patear", és dir, desplaçar, qualsevol clau que podria residir en esta ubicació. Després s'inserta esta clau desplaçada en el seu lloc alternatiu, de nou expulsar a qualsevol clau que podria residir en eixe lloc, fins que es trobe un lloc disponible, o el procediment podria caure en un cicle infinit. En este últim cas, la taula hash es reconstruïx en el lloc en una nova funció hash:

No hi ha necessitat d'assignar noves taules per al rehashing: Podem simplement eixecutar a través de les taules d'eliminar, i realisar el procediment d'inserció habitual per a totes les claus trobades que no estan en la seua posició prevista en la taula.

Les operacions de busca requerixen l'inspecció de només dos llocs en la taula hash, que pren temps constant en el pijor dels casos (vore Cota superior asintòtica). Açò està en contrast en molts atres algoritmes de taula de hash, que poden no tindre una constant pijor dels casos, en destí en el temps per a fer una busca.

També pot demostrar-se que les insercions poden tindre èxit en la constant de temps esperat, inclús tenint en conte la possibilitat de tindre que reconstruir la taula, sempre i quan es manté el número de claus per baix de la mitat de la capacitat de la taula hash, és dir, el factor de càrrega és inferior a 50%. Un método per a provar açò utilisa la teoria de grafos aleatoris: un pot formar un grafo no dirigit cridat el "grafo cuckoo" que té un vèrtiç per a cada ubicació en la taula hash, i una aresta per a cada valor hash, en els extrems de l'aresta sent les dos possibles ubicacions del valor. Llavors, l'algoritme d'inserció per adició d'un conjunt de valors d'una taula hash cuckoo té èxit si i només si el grafo cuckoo per a este conjunt de valors és un pseudoforest, un grafo en a lo manco un cicle per cada una dels seus components conexas, com qualsevol subgrafo induït en més arestes que vèrtiços corresponent a un joc de claus per als que hi ha un número insuficient de llocs en la taula hash. Esta propietat es complix en alta provabilitat per a un grafo aleatori en el que el número d'arestes és menor que la mitat del número de vèrtiços.

Vore també

• Colisió de hash
• Funció hash