hash de tiempo constante para cadenas?

Question

Otra pregunta sobre SO trajo las instalaciones en algunos idiomas a cadenas de hash para darles una búsqueda rápida en una tabla. Dos ejemplos de esto son el diccionario <> en .NET y la {} estructura de almacenamiento en Python. Otros idiomas ciertamente apoyan ese mecanismo. C++ tiene su mapa, LISP tiene un equivalente, al igual que la mayoría de los otros idiomas modernos.

Se sostuvo en las respuestas a la pregunta que los algoritmos hash en cadenas se pueden llevar a cabo en tiempo constante con un miembro SO que tiene 25 años de experiencia en programación afirmando que cualquier cosa se puede codificar en tiempo constante. Mi opinión personal es que esto no es cierto, a menos que su aplicación particular establezca un límite en la longitud de la cadena. Esto significa que una constante K dictará la longitud máxima de una cuerda.

Estoy familiarizado con el algoritmo Rabin-Karp que utiliza una función hash para su funcionamiento, pero este algoritmo no dicta una función hash específica para usar, y el que los autores sugirieron es O (m), donde m es la longitud de la secuencia hash.

Veo algunas otras páginas como esta (http://www.cse.yorku.ca/~oz/hash.html) que muestran algunos algoritmos hash, pero parece que cada uno de ellos itera sobre toda la longitud de la cadena para llegar a su valor.

De mi lectura comparativamente limitada sobre el tema, parece que la mayoría de las matrices asociativas para tipos de cadenas se crean realmente utilizando una función de hashing que opera con un árbol de algún tipo debajo del capó. Puede ser un árbol AVL o un árbol rojo/negro que apunta a la ubicación del elemento de valor en el par clave/valor.

Incluso con esta estructura de árbol, si vamos a permanecer en el orden de theta (log (n)), siendo n el número de elementos en el árbol, necesitamos tener un algoritmo hash de tiempo constante. De lo contrario, tenemos la penalidad aditiva de iterar sobre la cadena. Aunque theta (m) sería eclipsado por theta (log (n)) para índices que contienen muchas cadenas, no podemos ignorarlo si estamos en tal dominio que los textos que buscamos serán muy grandes.

Soy consciente de que los árboles/matrices de sufijo y Aho-Corasick pueden llevar la búsqueda a theta (m) para un gasto mayor en memoria, pero lo que estoy preguntando específicamente es si existe un método hash de tiempo constante para cadenas de longitudes arbitrarias como fue reclamado por el otro miembro SO.

Gracias.

Answer 1

En general, creo que cualquier hash de cadena completo debe usar todos los caracteres de la cadena y, por lo tanto, debería crecer como O (n) para n caracteres. Sin embargo, creo que para hash de cadenas prácticas puedes usar hashes aproximados que pueden ser fácilmente O (1).

Considere un hash de cadena que siempre usa Min (n, 20) caracteres para calcular un hash estándar. Obviamente esto crece como O (1) con el tamaño de la cuerda. ¿Funcionará de manera confiable? Depende de su dominio ...

Answer 2

Una función hash no tiene que (y no puede) devolver un valor único para cada cadena.

Puede utilizar los primeros 10 caracteres para inicializar un generador de números aleatorios y luego usar eso para sacar 100 caracteres aleatorios de la cadena, y hash eso. Esto sería un tiempo constante.

También podría devolver el valor constante 1. Estrictamente hablando, esta sigue siendo una función hash, aunque no muy útil.

Answer 3

Puede esperanza para asintóticamente menos de tiempo de las dispersiones lineales si utilizar ropes en lugar de cuerdas y tienen intercambio que le permite pasar por alto algunos cálculos. Pero, obviamente, una función hash no puede separar las entradas que no ha leído, por lo que no tomaría demasiado en serio el "todo se puede codificar en tiempo constante".

Cualquier cosa es posible en el compromiso entre la calidad de la función hash y la cantidad de cálculos que requiere, y una función hash en cadenas largas debe tener colisiones de todos modos.

Usted tiene que determinar si las cadenas que probablemente se producirán en su algoritmo colisionarán con demasiada frecuencia si la función de almohadilla solo mira un prefijo.

Answer 4

Aunque no puedo imaginar una función hash de tiempo fijo para cadenas de longitud ilimitada, realmente no hay necesidad de ello.

La idea detrás de usar una función hash es generar una distribución de los valores hash que hace que sea poco probable que muchas cadenas colisionen - para el dominio bajo consideración. Esta clave permitiría el acceso directo a un almacén de datos. Estos dos resultados combinados en una búsqueda de tiempo constante - en promedio.

En caso de que se produzca una colisión, el algoritmo de búsqueda recurre a una subestrategia de búsqueda más flexible.

Answer 5

No se puede lograr fácilmente un algoritmo general de hash de tiempo constante para cadenas sin riesgo de casos graves de colisiones hash.

Para que sea un tiempo constante, no podrá acceder a todos los caracteres de la cadena. Como un simple ejemplo, supongamos que tomamos los primeros 6 caracteres. Luego viene alguien e intenta mezclar una serie de URL. La función has verá "http: /" para cada cadena.

Escenarios similares pueden ocurrir para otros esquemas de selección de caracteres. Podrías elegir personajes de forma pseudoaleatoria en función del valor del personaje anterior, pero aún así corres el riesgo de fallar espectacularmente si las cuerdas por algún motivo tienen el patrón "incorrecto" y muchas terminan con el mismo valor hash.

Answer 6

Ciertamente, esto es factible, siempre y cuando se asegure de que todas sus cadenas estén 'internados', antes de pasarlos a algo que requiera hash. El internamiento es el proceso de inserción de la cadena en una tabla de cadenas, de modo que todas las cadenas internas con el mismo valor son de hecho el mismo objeto. Luego, simplemente puede hash el puntero (longitud fija) a la cadena interna, en lugar de hash la cadena en sí.

Answer 7

Puede que le interese el siguiente resultado matemático que obtuve el año pasado.

Considere el problema de hash un número infinito de claves, como el conjunto de todas las cadenas de cualquier longitud, para el conjunto de números en {1,2, ..., b}. El hash aleatorio se lleva a cabo seleccionando aleatoriamente una función hash h en una familia de funciones H.

Mostraré que siempre hay un número infinito de teclas que con seguridad colisionarán sobre todas las funciones H, es decir, que siempre tienen el mismo valor hash para todas las funciones hash.

Elija cualquier función hash h: hay al menos un valor hash y tal que el conjunto A = {s: h (s) = y} es infinito, es decir, tiene infinitamente muchas cadenas colisionando. Escoge cualquier otra función hash h 'y hash las teclas en el conjunto A. Hay al menos un valor hash y' tal que el conjunto A '= {s está en A: h' (s) = y '} es infinito, es decir, hay infinitas cadenas que colisionan en dos funciones hash.Puedes repetir este argumento muchas veces. Repítelo H veces. Entonces usted tiene un conjunto infinito de cadenas donde todas las cadenas colisionan sobre todas sus funciones H hash. CQFD.

lectura adicional: hash sensible de cadenas de longitud variable es imposible http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/