Quando si inserisce/cerca una chiave in una tabella hash, il libro di testo dice che è O (1) volta. Eppure, come è possibile avere un tempo di ricerca O (1)? Se la tabella hash memorizza la chiave in un vettore, costerà O (N), se in un albero binario, sarà O (logN). Non riesco a immaginare alcuna struttura dati con O (1) che accede al tempo.tempo di ricerca tabella hash
Grazie!
L'hashtable esegue l'hashing della chiave e la mette in serie.
Ad esempio, hash (x) = 3, dove x è la chiave. La tabella quindi la mette in array [3]. L'accesso dall'array è O (1).
Le tabelle di hash sono costituite almeno da una matrice e da una funzione hash. Quando un oggetto viene aggiunto alla tabella, la funzione di hash viene calcolata sull'oggetto e viene memorizzata nell'array all'indice del valore corrispondente che è stato calcolato. ad esempio, se hash(obj) = 2 quindi arr[2] = obj.
L'inserimento/ricerca media su una tabella hash è O(1).
Tuttavia è possibile avere collisioni quando gli oggetti calcolano lo stesso valore di hash.
Nel caso generale ci sono "bucket" in ciascun indice dell'array per gestire queste collisioni. Significato, tutti e tre gli oggetti sono memorizzati in qualche altra struttura dati (forse una lista collegata o un'altra matrice) all'indice della tabella hash.
Pertanto, il caso peggiore per la ricerca su una tabella hash è O(n) perché è possibile che tutti gli oggetti memorizzati nella tabella hash siano entrati in collisione e siano memorizzati nello stesso bucket.
Il caso peggiore per la ricerca su una tabella hash è 'O (n)'. Considera: 'hash (x) = 3',' hash (y) = 3' 'hash (z) = 3', etc etc –