hashing estendibile: perché qualcuno usa i bit più significativi?

Question

Quando si codifica l'hashing estendibile, si ha la scelta di utilizzare i bit più significativi oi bit meno significativi del valore di hash per determinare a quale bucket eseguire l'hash. Utilizzando bit meno significativi ha una serie di vantaggi:

• quando si raddoppia la directory, si può semplicemente copiare tutti i puntatori, invece di dover creare una nuova directory che li interleaves.
• È possibile semplificare la discussione dell'algoritmo non parlando nemmeno di bit, e semplicemente utilizzando l'aritmetica modulare come si farebbe con l'hashing in generale. Usare i 3 bit meno significativi per scegliere un bucket è lo stesso di h (x) = x mod 2^3.
• Non è necessario specificare in anticipo una larghezza dei numeri binari; se si utilizzano i bit più significativi, è necessario avere una lunghezza di bit specifica in mente.

Quello che non posso avvolgere la mia testa intorno è il motivo per reference dopo reference dopo reference mostra hashing estendibile fatto con bit più significativi. Per quanto ne so, l'unico vantaggio che offre i bit più significativi è un diagramma su carta (o sullo schermo) che non ha linee incrociate. C'è una buona ragione per cui così tante fonti così tanto più significative, invece che meno?

Answer 1

Sono finalmente tornato allo original source paper di Fagin, et. al. Si rivolgono a questo:

"Prendiamo atto che se avessimo usato suffissi di pseudokeys invece di prefissi, quindi l'algoritmo per il raddoppio della directory sarebbe particolarmente facile: sarebbe essenzialmente consistere di fare una seconda copia della porzione nonheader della directory, immediatamente dopo la prima copia.Tuttavia, abbiamo scelto di usare prefissi per il bene di semplicità intuitiva (quindi, utilizzando i prefissi le chiavi possono essere facilmente accessibili nell'ordine pseudokey, piuttosto che nell'ordine pseudokey invertito). "

Non capisco perché hanno visto questo approccio come più intuitivo, come si potrebbe fare a meno dell'idea del tutto e andare invece con l'aritmetica modulare, ma sembra che questo fosse almeno il loro fondamento logico.