¿Hash de tiempo constante para cadenas?

Question

Otra pregunta sobre SO mencionó las funciones en algunos idiomas para codificar cadenas para brindarles 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 lenguajes ciertamente apoyan este mecanismo.C++ tiene su mapa, LISP tiene un equivalente, al igual que la mayoría de los demás lenguajes modernos.

En las respuestas a la pregunta se sostuvo que los algoritmos hash en cadenas se pueden realizar en tiempo constante y un miembro de SO que tiene 25 años de experiencia en programación afirma que cualquier cosa se puede aplicar hash 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ía 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 a utilizar, y la que los autores sugirieron es O(m), donde m es la longitud del cadena 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 a lo largo de toda 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 en realidad se crean usando una función hash que opera con un árbol de algún tipo bajo el 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 queremos permanecer en el orden theta(log(n)), siendo n el número de elementos del árbol, necesitamos tener un algoritmo hash de tiempo constante.De lo contrario, tenemos la penalización aditiva de iterar sobre la cadena.Aunque theta(m) sería eclipsada por theta(log(n)) en índices que contienen muchas cadenas, no podemos ignorarlo si estamos en un dominio en el que los textos que buscamos serán muy grandes.

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

Gracias.

Answer 1

En general, creo que cualquier hash de cadena completa debe utilizar cada carácter de la cadena y por lo tanto tendría que crecer como O (n) para n caracteres. Sin embargo creo que para cuerdas práctica hashes puede utilizar hashes aproximados que pueden ser fácilmente O (1).

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

Answer 2

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

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

También puedes, simplemente devuelva el valor constante 1. En sentido estricto, esto sigue siendo una función hash, aunque no sea muy útil.

Answer 3

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

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

Pueden ocurrir escenarios similares para otros esquemas de selección de personajes.Puede elegir caracteres pseudoaleatoriamente según el valor del carácter anterior, pero aún corre el riesgo de fallar espectacularmente si, por alguna razón, las cadenas tienen el patrón "incorrecto" y muchas terminan con el mismo valor hash.

Answer 4

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

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

que determinar si las cadenas que puedan ocurrir en su algoritmo de chocarán con demasiada frecuencia si la función hash sólo se basa en un prefijo.

Answer 5

Aunque no puedo imaginar una función hash a tiempo fijo para cadenas de longitud ilimitada, en realidad 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 chocarían - para el dominio en cuestión. Esta clave sería permitir el acceso directo en un almacén de datos. Estos dos resultado combinado en un de búsqueda constante de tiempo -. En promedio

Si se produce alguna colisión de este tipo, el algoritmo de búsqueda en verano en un sub-estrategia de búsqueda más flexible.

Answer 6

Esto es ciertamente factible, siempre y cuando se aseguren que todos sus cuerdas son 'internados', antes de que les pasa a algo que requiere de hash. Internación es el proceso de inserción de la cadena en una tabla de cadenas, de manera que todas las cadenas internadas con el mismo valor, de hecho, el mismo objeto. A continuación, sólo tiene que desmenuzar el puntero (longitud fija) a la cadena de internados, en lugar de hash de la propia cadena.

Answer 7

Usted puede estar interesado en el siguiente resultado matemático que se me ocurrió el año pasado.

Considere el problema de hash de un número infinito de claves, tales como el conjunto de todas las cadenas de cualquier longitud, al conjunto de números en {1,2, ..., b}. hashing producto azar por primera recoger al azar una función hash h en una familia de funciones H.

voy a demostrar que siempre hay un número infinito de teclas que están determinados a chocar sobre todas las funciones H, es decir, siempre tienen el mismo valor hash para todas las funciones de hash.

Escoja 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 un número infinito de cadenas que chocan. Escoja cualquier otra función hash h 'y croquetas de las teclas en el conjunto A. Hay al menos un valor de hash y' tal que el conjunto A '= {s está en A: h' (s) = y '} es infinito, es decir, hay un número infinito de cadenas chocan en dos funciones hash. Puede repetir este argumento cualquier número de veces. Repetirlo H veces. Entonces usted tiene un conjunto infinito de cadenas, donde todas las cadenas chocan sobre la totalidad de sus funciones hash H. 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/