Sono comparso per un colloquio in cui mi è stato chiesto di scrivere un algoritmo per l'hashing delle chiavi parziali i.e; se ABCBC è inserito nell'hash, allora la ricerca di una stringa secondaria dovrebbe restituire il valore memorizzato. La mia risposta è stata quella di creare una raccolta di tutte le sottostringhe possibili di una determinata chiave e di mantenere una mappatura tra ciascuna sottostringa alla sua una o più string padre. Quindi mantenere un BST della raccolta di tutte le sottostringhe. Ogni nodo punterà a una raccolta di valori effettivi a cui la sottostringa potrebbe corrispondere. Ad es. A, AB, ABC, ABCB, ABCBC, B, BC, BCB, BCBC, C, CB, CBC sono possibili sottostringhe per questa stringa. Potrebbero esserci altre stringhe come BAB di cui, AB e B sono sottostringa di. Quindi dato AB, si associerà a due stringhe BAB e ABCBC.Il modo migliore per implementare l'hashing delle chiavi parziali
Esiste un altro modo più efficiente? Grazie
È possibile memorizzare i nodi della sottostringa in una tabella hash (hashing sul valore della sottostringa, ovviamente). Questo porterebbe la tua ricerca da O (log n) a O (1). La complessità dello spazio sarebbe comparabile o leggermente peggiore (a causa degli slot vuoti nella tabella). – jpm
Sembra che la creazione di un hash per ogni sottostringa possa diventare non fattibile ... forse c'è un altro trucco in corso qui? Qualcosa utilizzabile con alberi prefissi? –
Suffix tree (http://en.wikipedia.org/wiki/Suffix_tree) forse, anche se non è veramente "hashing". Non capisco davvero come funzioni la collezione generale: supponiamo di inserire ABCBC con un valore di 4. Quindi, cercando ABC restituisce 4, abbastanza equo. Cosa succede se inserisco anche CDABC con valore 5. Ora, cosa restituisce la ricerca di ABC? Non puoi dire "dovrebbe restituire il valore memorizzato" e anche dire "mapperà a due stringhe", perché non può fare entrambe le cose. –