java - separate - hashing c++ code

Hash: ¿Cómo funciona internamente?

Question

Esto puede sonar como una pregunta muy vaga por adelantado pero no lo es. He revisado la descripción de la función Hash 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é queremos decir con hash? ¿Cómo funciona internamente?
2. ¿Qué algoritmo sigue?
3. ¿Cuál es la diferencia entre HashMap , HashTable y HashList ?
4. ¿Qué queremos decir con ''Complejidad del tiempo constante'' y por qué la implementación diferente del hash brinda una operación de tiempo constante?
5. Por último, ¿por qué en la mayoría de las preguntas de la entrevista se le pregunta a Hash y LinkedList si existe alguna lógica específica para probar el conocimiento del entrevistado?

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

Answer 1

¿Qué queremos decir con Hashing, cómo funciona internamente?

Hash es la transformación de una cadena de valor o clave de longitud fija 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 simples, la mayoría de los algoritmos Hash funcionan con la lógica "index = f (key, arrayLength)"

Por último, ¿por qué en la mayoría de las preguntas de la entrevista se le pregunta a Hash y LinkedList si existe alguna lógica específica para probar el conocimiento del entrevistado?

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

Answer 2

1. Hashing significa generar (con suerte) un número único que represente un valor.
2. Los diferentes tipos de valores ( Integer , String , etc.) utilizan algoritmos diferentes para calcular un código hash.
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 conjunto de hash 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 la gente debería saber.

Answer 3

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

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

3. Hashtable y hashmap son lo mismo. Ellos pares clave-valor, donde las claves son hash. Las listas hash y hashsets no almacenan valores, solo claves.

4. Tiempo constante significa que no importa cuántas entradas haya en la tabla hash (o cualquier otra colección), el número de operaciones necesarias para encontrar un objeto dado por su clave es constante. Eso es - 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

1. Aquí hay una buena explicación sobre 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 a GetmyHashFunction("Rachel") y le devolverá 10 Tenga en cuenta que, para este 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 hay algunas funciones hash comunes que se usan. 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 el tamaño de su matriz es n = 100 y su clave es un número entero k = 15 entonces h(k) = 10 .

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

4. El propósito 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. Por supuesto, un informático programador / desarrollador necesita saber sobre las estructuras de datos y la complejidad =)

Answer 5

Considere el problema de buscar una matriz por un valor dado. 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.

Answer 6

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

Primero, 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 forma 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 notar que los resultados no son tan perfectos. Primero, solo hay 30 de ellos, y no podemos cambiarlo. En segundo lugar, algunas letras se usan 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 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 pareja y una cantidad configurable de conjuntos (también llamados segmentos).