algorithm
Funciones hash

Introducción a las funciones hash.

La función hash h() es una función arbitraria que mapea los datos x ∈ X de tamaño arbitrario para valorar y ∈ Y de tamaño fijo: y = h(x) . Las buenas funciones de hash tienen restricciones siguientes:

• Las funciones hash se comportan como distribución uniforme

• Las funciones hash son deterministas. h(x) siempre debe devolver el mismo valor para una x dada

• cálculo rápido (tiene tiempo de ejecución O (1))

En general, el tamaño de la función hash es menor que el tamaño de los datos de entrada: |y| < |x| . Las funciones de hash no son reversibles o, en otras palabras, pueden ser colisiones: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X puede ser un conjunto finito o infinito y Y es un conjunto finito.

Las funciones de hash se utilizan en muchas partes de la informática, por ejemplo, en ingeniería de software, criptografía, bases de datos, redes, aprendizaje automático, etc. Hay muchos tipos diferentes de funciones hash, con diferentes propiedades específicas de dominio.

A menudo, hash es un valor entero. Existen métodos especiales en los lenguajes de programación para el cálculo de hash. Por ejemplo, en C# método GetHashCode() C# para todos los tipos, se devuelve el valor Int32 (número entero de 32 bits). En Java cada clase proporciona el método hashCode() que devuelve int . Cada tipo de datos tiene implementaciones propias o definidas por el usuario.

Métodos hash

Hay varios enfoques para determinar la función hash. Sin pérdida de generalidad, sea x ∈ X = {z ∈ ℤ: z ≥ 0} son números enteros positivos. A menudo m es primo (no demasiado cerca de una potencia exacta de 2).

Tabla de picadillo

Funciones de hash usadas en tablas hash para calcular el índice en una matriz de ranuras. La tabla de hash es una estructura de datos para implementar diccionarios (estructura clave-valor). Las buenas tablas hash implementadas tienen O (1) tiempo para las siguientes operaciones: insertar, buscar y eliminar datos por clave. Más de una de las teclas pueden ser hash en la misma ranura. Hay dos formas de resolver la colisión:

1. Encadenamiento: la lista enlazada se usa para almacenar elementos con el mismo valor hash en la ranura

2. Direccionamiento abierto: cero o un elemento se almacena en cada ranura

Los siguientes métodos se utilizan para calcular las secuencias de sondeo requeridas para el direccionamiento abierto

Donde i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) son funciones hash auxiliares, c1, c2 son constantes auxiliares positivas.

Ejemplos

Permite x ∈ U{1, 1000}, h = x mod m . La siguiente tabla muestra los valores de hash en caso de que no sean primos y primos. El texto en negrita indica los mismos valores hash.

Campo de golf

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introducción a los algoritmos.

• Resumen de las tablas de hash

• Wolfram MathWorld - Hash Function

Códigos hash para tipos comunes en C #

Los códigos hash producidos por el método GetHashCode() para los tipos C # incorporados y comunes del espacio de nombres del System se muestran a continuación.

Booleano

1 si el valor es verdadero, 0 de lo contrario.

Byte , UInt16 , Int32 , UInt32 , Single

Valor (si es necesario casteado a Int32).

SByte

((int)m_value ^ (int)m_value << 8);

Carbonizarse

(int)m_value ^ ((int)m_value << 16);

Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64 , doble

Xor entre los 32 bits inferior y superior del número de 64 bits

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64 , DateTime , TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

Decimal

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Objeto

RuntimeHelpers.GetHashCode(this);

La implementación por defecto se utiliza el índice de bloque de sincronización .

Cuerda

El cálculo del código hash depende del tipo de plataforma (Win32 o Win64), la característica de usar hashing de cadenas aleatorias, el modo Debug / Release. En caso de plataforma Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
    hash1 = ((hash1 << 5) + hash1) ^ c;
    c = s[1];
    if (c == 0)
        break;
    hash2 = ((hash2 << 5) + hash2) ^ c;
    s += 2;
}
return hash1 + (hash2 * 1566083941);

Tipo de valor

El primer campo no estático es buscar y obtener su código hash. Si el tipo no tiene campos no estáticos, se devuelve el código hash del tipo. El código hash de un miembro estático no se puede tomar porque si ese miembro es del mismo tipo que el tipo original, el cálculo termina en un bucle infinito.

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

Formación

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++) 
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

Referencias

• GitHub .Net Core CLR