Come funziona una tabella hash? E 'più veloce di "SELECT * da .."

Question

Diciamo, ho:

 
Key | Indexes | Key-values 
----+---------+------------ 
001 | 100001 | Alex 
002 | 100002 | Micheal 
003 | 100003 | Daniel 

consente di dire, vogliamo cercare 001, come fare il processo di ricerca veloce utilizzando la tabella di hash?

Non è lo stesso che usiamo "SELECT * from .." in mysql? Ho letto molto, dicono, la "SELECT *" ricerca dall'inizio alla fine, ma la tabella hash non lo è? Perché e come?

Utilizzando la tabella hash, stiamo riducendo i record che stiamo cercando? Come?

Qualcuno può dimostrare come inserire e recuperare il processo della tabella hash nel codice di query mysql? per esempio,

SELECT * from table1 where hash_value="bla" ... 

Un altro scenario: Se gli indici sono come S0001, S0002, T0001, T0002, ecc mysql ho potuto utilizzare:

SELECT * from table WHERE value = S* 

non è lo stesso e più veloce?

Answer 1

Una semplice tabella di hash funziona mantenendo gli elementi su più elenchi, invece di uno solo. Utilizza un metodo molto veloce e ripetibile (vale a dire non casuale) per scegliere in quale elenco conservare ciascun elemento. Quindi, quando è il momento di trovare di nuovo l'oggetto, ripete quel metodo per scoprire in quale lista cercare, e poi fa una normale (lenta) ricerca lineare in quella lista.

Dividendo gli articoli in 17 elenchi, la ricerca diventa 17 volte più veloce, il che rappresenta un buon miglioramento.

Anche se questo è vero solo se le liste hanno all'incirca la stessa lunghezza, è quindi importante scegliere un buon metodo di distribuzione degli articoli tra gli elenchi.

Nella tabella di esempio, la prima colonna è la chiave, la cosa di cui abbiamo bisogno per trovare l'elemento. E supponiamo che manterremo 17 liste.Per inserire qualcosa, eseguiamo un'operazione sul tasto chiamato hashing. Questo trasforma semplicemente la chiave in un numero. Non restituisce un numero casuale, perché deve sempre restituire lo stesso numero per la stessa chiave. Ma allo stesso tempo, i numeri devono essere "diffusi" ampiamente.

poi prendiamo il numero e l'uso conseguente modulo a restringersi verso il basso per la dimensione della nostra lista:

Hash(key) % 17 

Tutto questo avviene estremamente veloce. Le nostre liste sono in un array, quindi:

_lists[Hash(key % 17)].Add(record); 

E poi, di trovare la voce usando quella chiave:

Record found = _lists[Hash(key % 17)].Find(key); 

Nota che ogni lista può essere un qualsiasi tipo di contenitore, o una lista collegata classe che scrivi a mano. Quando eseguiamo un Find nell'elenco, funziona in modo lento (esaminare la chiave di ogni record).

Answer 2

Le tabelle hash sono ideali per individuare le voci al costo O (1) in cui la chiave (utilizzata per l'hashing) è già nota. Sono ampiamente utilizzati sia nelle librerie di raccolta che nei motori di database. Dovresti essere in grado di trovare molte informazioni su di loro su internet. Perché non inizi con Wikipedia o fai semplicemente una ricerca su Google?

Non conosco i dettagli di mysql. Se c'è una struttura in là chiamata "tabella hash", probabilmente sarebbe un tipo di tabella che usa l'hashing per localizzare le chiavi. Sono sicuro che qualcun altro te lo dirà. =)

EDIT: (in risposta al commento)

Ok. Proverò a fare una spiegazione grossolanamente semplificata: una tabella hash è una tabella in cui le voci si trovano in base a una funzione della chiave. Ad esempio, supponi di voler memorizzare informazioni su un gruppo di persone. Se lo si archivia in una matrice semplice e non ordinata, sarà necessario scorrere gli elementi in sequenza per trovare la voce che si sta cercando. In media, questo richiederà N/2 confronti.

Se, invece, si inseriscono tutte le voci negli indici in base al primo carattere del nome della persona. (A = 0, B = 1, C = 2 ecc.), Sarai immediatamente in grado di trovare la voce corretta purché tu conosca il nome. Questa è l'idea di base. Probabilmente ti rendi conto che per gestire più voci con la stessa prima lettera è necessario un trattamento speciale (rimodellamento o elenco di voci). Se hai una tabella hash ben dimensionata, dovresti essere in grado di arrivare direttamente all'elemento che stai cercando. Ciò significa circa un confronto, con il disclaimer della gestione speciale che ho appena menzionato.

Answer 3

Immagino che si possa usare una funzione di hash per ottenere l'ID da cui si desidera effettuare la selezione. Come

SELECT * FROM tabella WHERE value = hash_fn (whatever_input_you_build_your_hash_value_from)

Allora non c'è bisogno di conoscere l'ID della riga che si desidera selezionare e può fare una query esatta. Dato che sai che la riga avrà sempre lo stesso id a causa dell'input costruisci il modulo del valore hash e puoi sempre ricreare questo id attraverso la funzione hash.

Tuttavia, questo non è sempre vero a seconda della dimensione della tabella e del numero massimo di hashvalues ​​(spesso è presente "X mod hash-table-size" nel proprio hash). Per prenderti cura di questo dovresti avere una strategia deterministica che usi ogni volta che ottieni due valori con lo stesso id. Dovresti controllare Wikipedia per maggiori informazioni su questa strategia, la sua chiamata gestione delle collisioni e dovrebbe essere menzionata nello stesso articolo delle tabelle hash.

MySQL utilizza probabilmente le hash da qualche parte a causa della funzione O (1) norheim.se (sopra) menzionata.

Answer 4

Non preoccuparti di ciò che MySQL sta eseguendo internamente per individuare rapidamente i record. Il lavoro di un database è di fare questo genere di cose per te. Basta eseguire una query SELECT [columns] FROM table WHERE [condition]; e lasciare che il database generi un piano di query per te. Si noti che non si desidera utilizzare SELECT *, poiché se si aggiunge una colonna alla tabella che interromperà tutte le query precedenti a cui si è basato un determinato numero di colonne in un determinato ordine.

Se si vuole veramente sapere cosa sta succedendo sotto il cofano (è bene sapere, ma non implementarla da sé: questo è lo scopo di un database), è necessario sapere che cosa gli indici sono e come lavorano. Se una tabella non ha un indice sulle colonne coinvolte nella clausola WHERE, allora, come dici tu, il database dovrà cercare in ogni riga della tabella per trovare quelle corrispondenti alla tua condizione. Ma se è un indice, il database cercherà l'indice per trovare la posizione esatta delle righe desiderate e salterà direttamente su di esse. Gli indici vengono solitamente implementati come B+-trees, un tipo di albero di ricerca che utilizza pochissimi confronti per individuare un elemento specifico. La ricerca di un albero B per una chiave specifica è molto veloce. MySQL è anche in grado di utilizzare gli indici hash, ma questi tendono ad essere più lenti per gli usi del database. Gli indici hash di solito si comportano bene solo con i tasti lunghi (specialmente le stringhe di caratteri), poiché riducono la dimensione della chiave a una dimensione hash fissa. Per tipi di dati come numeri interi e numeri reali, che hanno un ordine ben definito e una lunghezza fissa, la facile ricercabilità di un albero B di solito offre prestazioni migliori.

Si consiglia di consultare i capitoli nel MySQL manual e PostgreSQL manual sull'indicizzazione.

Answer 5

http://en.wikipedia.org/wiki/Hash_table

tabelle hash può essere utilizzato come strutture di dati in memoria. Le tabelle hash possono anche essere adottate per l'uso con strutture di dati persistenti; database indices a volte utilizzano strutture dati basate su disco basate su tabelle hash, anche se balanced trees sono più popolari.