Cosa sono gli Hash Bucket?

In informatica, una tabella hash [mappa hash] è una struttura di dati che offre un accesso virtualmente diretto a oggetti sulla base di una chiave [una stringa o un numero intero unico]. Una tabella hash usa una funzione hash per calcolare un indice in una serie di bucket o slot, da cui può essere ricavato il valore desiderato. Le caratteristiche principali della chiave utilizzata sono le seguenti:

• la chiave utilizzata può essere il numero della propria tessera sanitaria, del proprio telefono o conto corrente ecc.;
• deve avere chiavi uniche;
• ogni chiave è associata (mappata) a un valore.

Gli hash bucket vengono utilizzati per distribuire dati per scopi di ordinamento o ricerca. Lo scopo è indebolire le liste collegate, in modo che la ricerca di un elemento specifico risulti accessibile in un tempo più breve. Una tabella hash che usa bucket è sostanzialmente una combinazione di un array e una lista collegata. Ogni elemento dell'array [la tabella hash] è l'intestazione di una lista collegata. Tutti gli elementi che fanno riferimento alla stessa posizione verranno memorizzati nella lista. La funzione hash assegna ogni record al primo slot all'interno di uno dei bucket. Qualora lo slot risulti occupato, gli slot dei bucket verranno passati in sequenza fino a trovare uno slot aperto. Nel caso in cui un bucket risulti completamente pieno, il record verrà memorizzato in un bucket di overflow con capacità infinita alla fine della tabella. Tutti i bucket condividono lo stesso bucket di overflow. Tuttavia, una buona implementazione utilizzerà una funzione hash che distribuisce i record uniformemente fra i bucket, in modo che nel bucket di overflow finisca il minor numero possibile di record.

Risorse aggiuntive

• Rilevare abusi su larga scala: Uber Engineering usa l'hashing con sensibilità locale
• Notebook con esempi di bucketing