Cosa succede nelle tabelle hash Hopscotch quando sono presenti più collisioni hash effettive di sizeof (Neighborhood)?

Question

collegamento relativo: http://en.wikipedia.org/wiki/Hopscotch_hashing

Hopscotch tabelle hash sembrano grande, ma io non hanno trovato una risposta a questa domanda nella letteratura: che cosa succede se la mia taglia quartiere è N e (a causa di illeciti o estremamente sfortuna) I inserire N + 1 elementi che hanno tutti lo stesso hash allo stesso valore?

Answer 1

Nell'originale article è scritto quel tavolo deve essere ridimensionata:

Infine, si noti che se più di un numero costante di elementi viene eseguito l'hashing da h in un dato secchio, la tabella deve essere ridimensionato Fortunatamente, come dimostriamo, per una funzione di hash h universale , la probabilità che questo tipo di ridimensionamento si verifichi dato H = 32 è 1/32 !.

Answer 2

Ci sono due casi in cui dobbiamo ridimensionare hash campana

1. avete collisioni H per la data secchio
2. il fattore di carico è davvero troppo grande per trovare il secchio libero. In pratica, dovresti impostare un massimo per il bucket gratuito di ricerca.

Data la funzione di hash universale, hai solo 1/32! possibilità di entrare nel caso # 1, in altre parole, se si inseriscono continuamente 2^35 elementi, allora si ha una possibilità di ridimensionamento a causa di collisioni.

Il caso # 2 è un motivo più popolare per ridimensionare, in pratica, si potrebbe fare riferimento a alcune implementazioni di secondo grado per il modo in cui decidono di ridimensionare [C# hashmap e Google hashmap sparse], non v'è alcun reale implementazione per sonda lineare a causa della sua svantaggio del cluster, cioè non può garantire una ricerca costante.