Hash: ¿Cómo funciona internamente?

Question

Esto puede sonar como una pregunta muy vaga por adelantado pero no lo es. He pasado por la descripción de Hash Function en wiki, pero no es muy útil de entender.

Estoy buscando respuestas simples para temas bastante complejos como Hashing. Aquí están mis preguntas:

1. ¿Qué entendemos por hashing? ¿Cómo funciona internamente?
2. ¿Qué algoritmo sigue?
3. ¿Cuál es la diferencia entre HashMap, HashTable y HashList?
4. ¿Qué entendemos por 'Complejidad del tiempo constante' y por qué la implementación diferente del hash brinda un funcionamiento constante del tiempo?
5. Por último, ¿por qué en la mayoría de las preguntas de la entrevista Hash y LinkedList se preguntan si existe alguna lógica específica para probar el conocimiento del entrevistado?

Sé que mi lista de preguntas es grande, pero realmente agradecería si puedo obtener algunas respuestas claras a estas preguntas, ya que realmente quiero entender el tema.

Answer 1

1. Here es una buena explicación acerca de hash. Por ejemplo, si desea almacenar la cadena "Rachel", aplica una función hash a esa cadena para obtener una ubicación de memoria. myHashFunction(key: "Rachel" value: "Rachel") --> 10. La función puede devolver 10 para la entrada "Rachel", suponiendo que tiene una matriz de tamaño 100, almacena "Rachel" en el índice 10. Si desea recuperar ese elemento, simplemente llame al GetmyHashFunction("Rachel") y devolverá 10. Tenga en cuenta que para esto Por ejemplo, la clave es "Rachel" y el valor es "Rachel", pero podría usar otro valor para esa clave, por ejemplo, fecha de nacimiento o un objeto. Su función hash puede devolver la misma ubicación de memoria para dos entradas diferentes, en este caso tendrá una colisión. Si está implementando su propia tabla hash, debe ocuparse de esto, tal vez utilizando una lista vinculada u otras técnicas.

2. Here son algunas de las funciones hash más utilizadas. Una buena función de hash satisface eso: cada tecla tiene la misma probabilidad de ir a cualquiera de las n ranuras de memoria, independientemente de donde cualquier otra tecla tenga hash. Uno de los métodos se llama método de división. Asignamos una clave k en una de n ranuras tomando el resto de k dividido por n. h(k) = k mod n. Por ejemplo, si su tamaño de matriz es n = 100 y su clave es un número entero k = 15 y luego h(k) = 10.

3. Hashtable está sincronizado y Hashmap no lo está. Hashmap permite valores nulos como clave pero Hashtable no.

4. El objetivo de una tabla hash es tener O (c) complejidad de tiempo constante al agregar y obtener los elementos. En una lista vinculada de tamaño N, si desea obtener el último elemento, debe atravesar toda la lista hasta que lo obtenga, de modo que la complejidad sea O (N). Con una tabla hash si quieres recuperar un elemento, simplemente pasas la tecla y la función hash te devolverá el elemento deseado. Si la función hash está bien implementada, estará en tiempo constante O (c) Esto significa que no tiene que atravesar todos los elementos almacenados en la tabla hash. Obtendrás el elemento "al instante".

5. De couse un informático programador/desarrollador necesita saber acerca de las estructuras de datos y la complejidad =)

Answer 2

1. Hashing significa generar (con suerte) un número único que representa un valor.
2. Diferentes tipos de valores (Integer, String, etc.) utilizan algoritmos diferentes para calcular un hashcode.
3. HashMap y HashTable son mapas; son una colección de claves únicas, cada una de las cuales está asociada a un valor.
   Java no tiene una clase HashList. Un Hash Set es un conjunto de valores únicos.
4. Obtener un elemento de una tabla hash es constante en relación con el tamaño de la tabla.
   Calcular un hash no es necesariamente un tiempo constante con respecto al valor que se va a aplicar.
   Por ejemplo, calcular el hash de una cadena implica iterar la cadena, y no es de tiempo constante con respecto al tamaño de la cadena.
5. Estas son cosas que las personas deberían saber.

Answer 3

1. Hashing está transformando una entidad dada (en términos de Java - un objeto) a un número (o secuencia). La función hash no es reversible, es decir, no puede obtener el objeto original del hash. Internamente se implementa (por java.lang.Object por conseguir un poco de dirección de memoria por la JVM.

   cosa

2. La dirección de JVM es detalle sin importancia. Cada clase puede reemplazar el método hashCode() con su propio algoritmo. Modren Java IDE permiten la generación de buenos métodos hashCode .

3. Hashtable y hashMap son la misma cosa que los pares clave-valor, donde son ordenadas llaves listas de hash y hashsets hacer no almacenar valores -... sólo teclas

4. constante en el tiempo significa que no importa cuántas entradas hay en la tabla hash (o cualquier otra colección), el número de operaciones ns necesario para encontrar un objeto dado por su clave es constante.Es decir - 1, o cerca de 1

5. Este es un material básico de ciencias de la computación, y se supone que todos están familiarizados con él. Creo que Google ha especificado que el hashtable es la estructura de datos más importante en ciencias de la computación.

Answer 4

¿Qué entendemos por Hashing, ¿cómo funciona internamente ?

Hash es la transformación de una cadena de valor de longitud fija o clave más corta que representa la cadena original. No está indexando. El corazón de hash es la tabla hash. Contiene una variedad de elementos. Las tablas hash contienen un índice de la clave del elemento de datos y usan este índice para colocar los datos en la matriz.

¿Qué algoritmo sigue?

En palabras sencillas la mayoría de los algoritmos hash trabajar en la lógica "index = f (clave, arrayLength)"

Por último, ¿por qué en la mayoría entrevista preguntas hash y LinkedList son pedido, se Existe alguna lógica específica para de la prueba del conocimiento del entrevistado conocimiento?

Se trata de lo bueno que eres en el razonamiento lógico. Es la estructura de datos más importante que todos los programadores conocen.

Answer 5

Trataré de dar explicaciones simples de hashing y de su propósito.

En primer lugar, considere una lista simple. Cada operación (insertar, encontrar, eliminar) en dicha lista tendría O (n) complejidad, lo que significa que tiene que analizar toda la lista (o la mitad de ella, en promedio) para realizar dicha operación.

Hashing es una manera muy simple y efectiva de acelerarlo: considere que dividimos toda la lista en un conjunto de listas pequeñas. Los elementos en una lista tan pequeña tendrían algo en común, y este algo se puede deducir de la clave. Por ejemplo, al tener una lista de nombres, podríamos usar la primera letra como la calidad que elegirá en qué lista pequeña buscar. De esta forma, al dividir los datos por la primera letra de la clave, obtuvimos un hash simple, que podría dividir toda la lista en ~ 30 listas más pequeñas, de modo que cada operación tomaría O (n)/30 veces. .

Sin embargo, podemos observar que los resultados no son tan perfectos. Primero, solo hay 30 de ellos, y no podemos cambiarlo. En segundo lugar, algunas letras se utilizan con más frecuencia que otras, por lo que el conjunto con Y o Z será mucho más pequeño que el conjunto con A. Para obtener mejores resultados, es mejor encontrar una manera de dividir los elementos en conjuntos de aproximadamente el mismo tamaño. ¿Cómo podríamos resolver eso? Aquí es donde usas funciones hash. Es una función tal que puede crear un número arbitrario de particiones con aproximadamente el mismo número de elementos en cada una. En nuestro ejemplo, con los nombres, podríamos usar algo como

int hash(const char* str){ 
    int rez = 0; 
    for (int i = 0; i < strlen(str); i++) 
     rez = rez * 37 + str[i]; 
    return rez % NUMBER_OF_PARTITIONS; 
}; 

Esto aseguraría una distribución bastante uniforme y número configurable de conjuntos (también llamados cubos).

Answer 6

Considere el problema de buscar una matriz por un valor determinado. Si la matriz no está ordenada, la búsqueda puede requerir el examen de todos y cada uno de los elementos de la matriz. Si la matriz está ordenada, podemos usar la búsqueda binaria y, por lo tanto, reducir la complejidad del tiempo de ejecución en el peor de los casos a O (log n). Podríamos buscar aún más rápido si sabemos de antemano el índice en el que se encuentra ese valor en la matriz. Supongamos que tenemos esa función mágica que nos dirá el índice para un valor dado. Con esta función mágica, nuestra búsqueda se reduce a una sola sonda, dándonos un tiempo de ejecución constante O (1). Tal función se llama función hash. Una función hash es una función que cuando se le da una clave, genera una dirección en la tabla.