hash costante in tempo per le stringhe?

Question

Un'altra domanda su SO portato le strutture in alcune lingue di hash stringhe per dare loro una ricerca veloce in una tabella. Due esempi di questo sono dizionario <> in .NET e {} struttura di archiviazione in Python. Altre lingue certamente sostenere un tale meccanismo. C ++ ha la sua mappa, LISP ha un equivalente, come la maggior parte altre lingue moderne.

E 'stato sostenuto nelle risposte alla domanda che gli algoritmi di hash sulle stringhe possono essere condotte in costante TEMPOM con un SO socio che ha 25 anni di esperienza nella programmazione sostenendo che tutto può essere generato un hash in tempo costante. La mia tesi personale è che questo non è vero, a meno che la vostra applicazione particolare pone un limite sulla lunghezza della stringa. Ciò significa che alcuni costante K imporrebbe la lunghezza massima di una stringa.

mi è familiare con l'algoritmo di Rabin-Karp, che utilizza una funzione di hash per il suo funzionamento, ma questo algoritmo non impone una funzione hash specifico da utilizzare, e quello gli autori hanno suggerito è O (m), dove m è la lunghezza della stringa hash.

Ho visto alcune altre pagine come questa ( http: // www. cse.yorku.ca/~oz/hash.html ) che visualizzare alcuni algoritmi hash, ma sembra che ciascuno di essi itera sull'intera lunghezza della stringa per arrivare al suo valore.

Dal mio relativamente limitata lettura sul tema, sembra che la maggior parte degli array associativi per i tipi di stringa sono effettivamente creati utilizzando una funzione di hashing che opera con un albero di qualche tipo sotto il cofano. Questo può essere un albero AVL o rosso albero / nero che punta alla posizione dell'elemento valore della coppia chiave / valore.

Anche con questa struttura ad albero, se vogliamo rimanere su ordine di theta (log (n)), con n è il numero di elementi nella struttura, abbiamo bisogno di avere un algoritmo di hash tempo costante. In caso contrario, abbiamo la pena di additivo iterare su stringa. Anche se theta (m) sarebbe eclissata da theta (log (n)) per gli indici che contengono molte stringhe, non possiamo ignorare che se siamo in un tale dominio che i testi che abbiamo di perquisizione contro sarà molto grande.

Sono consapevole del fatto che gli alberi suffisso / array e Aho-Corasick possono portare la ricerca verso il basso per theta (m) per una maggiore spesa in memoria, ma quello che sto chiedendo in particolare se un metodo hash costante di tempo esiste per stringhe di arbitraria lunghezze come è stato sostenuto dagli altri Stati SO.

Grazie.

Answer 1

In generale, credo che qualsiasi hash stringa completa deve utilizzare tutti i caratteri della stringa e quindi avrebbe bisogno di crescere come O (n) per n caratteri. Comunque credo che per la stringa pratico hash è possibile utilizzare gli hash approssimative che possono facilmente essere O (1).

Si consideri un hash stringa che utilizza sempre Min (n, 20) caratteri per calcolare un hash standard. Ovviamente questo cresce come O (1) con il formato stringa. Funzionerà in modo affidabile? Dipende dal vostro dominio ...

Answer 2

Una funzione hash non deve (e non può) restituire un valore unico per ogni stringa.

È possibile utilizzare i primi 10 caratteri per inizializzare un generatore di numeri casuali e quindi utilizzare tale per tirare fuori 100 caratteri a caso dalla stringa, e hash. Questo sarebbe costante di tempo.

Si potrebbe anche solo restituire il valore costante 1. A rigor di termini, questo è ancora una funzione di hash, anche se non molto utile.

Answer 3

Non si può facilmente ottenere una costante di tempo generale algoritmo di hash per le stringhe senza rischiare gravi casi di collisioni hash.

Per essere costante di tempo, non sarà in grado di accedere a tutti i caratteri della stringa. Come semplice esempio, supponiamo di prendere i primi 6 caratteri. Poi arriva qualcuno e cerca di hash una serie di URL. La funzione ha vedrà "http: /". Per ogni singola stringa

scenari simili possono verificarsi per altri personaggi selezioni schemi. Si poteva scegliere caratteri in base pseudo-casualmente sul valore del carattere precedente, ma è ancora correre il rischio di non spettacolare se le stringhe per qualche motivo hanno il pattern "sbagliato" e molti finiscono con lo stesso valore di hash.

Answer 4

Puoi speranza per asintoticamente inferiore al tempo di hashing lineare se si utilizza corde invece di stringhe e hanno la condivisione che permette di saltare alcuni calcoli. Ma ovviamente una funzione di hash può ingressi non separate che non ha letto, quindi vorrei non prendere il "tutto può essere generato un hash in tempo costante" troppo sul serio.

Tutto è possibile nel compromesso tra la qualità della funzione di hash e la quantità di calcolo che ci vuole, e una funzione di hash su lunghe stringhe deve avere collisioni in ogni caso.

avere per determinare se le stringhe che possono verificarsi nel vostro algoritmo si scontreranno troppo spesso se la funzione di hash guarda solo un prefisso.

Answer 5

Anche se non riesco a immaginare una funzione di hash a tempo determinato per le stringhe di lunghezza illimitata, non c'è davvero alcun bisogno di esso.

L'idea alla base utilizzando una funzione di hash è quello di generare una distribuzione dei valori di hash che lo rende improbabile che molti avrebbero stringhe collidono - per il dominio in esame. Questa chiave potrebbe consentire l'accesso diretto in un archivio dati. Questi due risultati combinati in un ricerca costante di tempo -. In media

Se si verifica mai tale collisione, l'algoritmo di ricerca ricade su un sub-strategia di ricerca più flessibile.

Answer 6

Certamente questo è fattibile, purché si assicura tutte le stringhe sono 'internati', prima di passare a qualcosa che richiede di hashing. Interning è il processo di inserimento della stringa in una tabella di stringhe, in modo tale che tutte le stringhe internati con lo stesso valore sono infatti lo stesso oggetto. Quindi, si può semplicemente hash la (lunghezza fissa) puntatore alla stringa internati, invece di hashing della stringa stessa.

Answer 7

Si può essere interessato al seguente risultato matematico mi è venuta l'anno scorso.

Si consideri il problema di hashing un numero infinito di chiavi, ad esempio l'insieme di tutte le stringhe di qualsiasi lunghezza, per l'insieme dei numeri in {1,2, ..., b}. Casualmente hashing procede per primo raccolto a caso una funzione hash h in una famiglia di funzioni H.

mostrerò che c'è sempre un numero infinito di chiavi che sono certi di entrare in collisione su tutte le funzioni H, cioè, hanno sempre lo stesso valore di hash per tutte le funzioni di hash.

Scegliere qualsiasi funzione hash h: c'è almeno un valore di hash y tale che l'insieme A = {s: h (s) = y} è infinita, cioè, si dispone di un numero infinito di stringhe in collisione. Scegliere qualsiasi altra funzione hash h 'e hashing le chiavi nel set A. C'è almeno un valore hash y' tale che l'insieme A '= {s è in A: h' (s) = y '} è infinito, cioè, ci sono infinitamente molte stringhe che collidono su due funzioni di hash. È possibile ripetere questo argomento un numero illimitato di volte. Ripetere H volte. Allora avete un insieme infinito di stringhe in cui tutte le stringhe collidono su tutte le funzioni di hash H. CQFD.

Letture consigliate : hashing Sensible di stringhe di lunghezza variabile è impossibile http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/