Archive

Posts Tagged ‘Funciones de Hash’

Funciones de Hash

February 20th, 2011 No comments
Share Button

Una función de hash es aquella que convierte una serie de datos en otra serie de datos más corta (generalmente en una simple variable entera de 32 o 64 bits).
Esto es especialmente útil para poder identificar/representar una secuencia de datos de una forma mucho más rápida y eficiente. Pero hay que tener en cuenta que existen infinitas secuencias de datos que dan como resultado el mismo código de hash por lo que no es un proceso reversible, es decir, es prácticamente imposible obtener la secuencia de datos con la que fue calculado el hash a partir del propio hash.

Por ejemplo, es muy útil para codificar cadenas de caracteres y de esta forma poder realizar búsquedas mucho más rápidamente, o como simple sistema de indexación de datos.
También se utilizan en criptografía y como sistemas de comprobación de integridad de los datos, algunos ejemplos de este tipo de funciones de hash son la CRC, MD5, MD4, Tiger, RMD, SHA, etc.

El principal problema surge cuando es imprescindible que cada secuencia de datos tenga un identificador hash único, si dos o más secuencias tienen el mismo hash se produce una colisión de hash. En este ejemplo las cadenas “Jirafa” y “Tigre” tienen el mismo hash, 02.

Existen infinitas formas de hacer una función de hash y puedes crear la tuya propia fácilmente, el problema es conseguir que la función genere una buena distribución de los hashes y, a ser posible, que produzca las menores colisiones posibles incluso con secuencias de datos muy cortas y similares. Por eso es recomendable utilizar alguna de las muchas funciones de hash que se utilizan desde hace tiempo y están muy probadas.
Aqui dejo un video del MIT de introducción a las técnicas de hashing:

Sin mas historias vamos con algunas de las funciones de hashing de 32 bits más básicas y utilizadas:

Esta es mi favorita, surgió de una idea presentada al comité del IEEE POSIX P1003.2 por Glenn Fowler y Phong Vo en 1991, luego Landon Curt Noll la mejoró.
Funciona muy bien, es rápida y produce pocas colisiones. Realiza una buena dispersión de los hashes y va muy bien para hacer hashing en cadenas casi idénticas como URLs, URIs, IPs, nombres de archivo, etc.
Esta es la implementación mejorada FNV-1a de 32 bits (la única diferencia con la original FNV-1 es que se invierte el orden del XOR y la multiplicación, produciendo así una mejor dispersión):

1
2
3
4
5
6
7
8
9
10
11
12
13
uint32_t HashFNV32(const char *data, uint32_t len)
{
  const uint32_t fnv_prime = 0x1000193;

  uint32_t hash = 0x811C9DC5;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = (hash ^ (*data)) * fnv_prime;
  }

  return hash;
}

Y esta es la versión de 64 bits:

1
2
3
4
5
6
7
8
9
10
11
12
13
uint64_t HashFNV64(const char *data, uint64_t len)
{
  const uint64_t fnv_prime = 0x100000001B3;

  uint64_t hash = 0xCBF29CE484222325;

  for (uint64_t i = 0; i < len; data++, i++)
  {
    hash = (hash ^ (*data)) * fnv_prime;
  }

  return hash;
}

Esta es del profesor Daniel J. Bernstein, es una de las más eficientes:

1
2
3
4
5
6
7
8
9
10
11
uint32_t HashDJB(const char *data, uint32_t len)
{
  uint32_t hash = 5381;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = ((hash << 5) + hash) + (*data);
  }

  return hash;
}

Esta es de Donald E. Knuth, está en el volumen III de su libro “The Art of Computer Programming”:

1
2
3
4
5
6
7
8
9
10
11
uint32_t HashDEK(const char *data, uint32_t len)
{
  uint32_t hash = len;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = ((hash << 5) ^ (hash >> 27)) ^ (*data);
  }

  return hash;
}

Esta está basada en el trabajo de Peter J. Weinberger de los laboratorios AT&T.
En el libro “Compilers (Principles, Techniques and Tools)” se recomienda su uso:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
uint32_t HashPJW(const char *data, uint32_t len)
{
  const uint32_t bits_in_ui32   = (uint32_t)(sizeof(uint32_t) * 8);
  const uint32_t three_quarters = (uint32_t)((bits_in_ui32 * 3) / 4);
  const uint32_t one_eighth     = (uint32_t)(bits_in_ui32 / 8);
  const uint32_t high_bits      = (uint32_t)(0xFFFFFFFF) << (bits_in_ui32 - one_eighth);

  uint32_t test = 0;
  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = (hash << one_eighth) + (*data);

    if (test = hash & high_bits)
    {
      hash = (hash ^ (test >> three_quarters)) & (~high_bits);
    }
  }

  return hash;
}

Esta es muy similar a la PJW, pero está optimizada para procesadores de 32 bits.
Se utiliza en la mayoría de los sistemas UNIX:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
uint32_t HashELF(const char *data, uint32_t len)
{
  uint32_t x    = 0;
  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = (hash << 4) + (*data);

    if (x = hash & 0xF0000000)
    {
      hash ^= x >> 24;
    }

    hash &= ~x;
  }

  return hash;
}

Esta es del libro “The C Programming Language” de Dennis Ritchie y Brian Kernighan:

1
2
3
4
5
6
7
8
9
10
11
12
13
uint32_t HashBKDR(const char *data, uint32_t len)
{
  const uint32_t seed = 131;

  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = hash * seed + (*data);
  }

  return hash;
}

Esta es una función de hash del libro “Algorithms in C” de Robert Sedgwicks:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint32_t HashRS(const char *data, uint32_t len)
{
  uint32_t a    = 63689;
  uint32_t b    = 378551;
  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = hash * a + (*data);
    a = a * b;
  }

  return hash;
}

Esta es una función de hash de Justin Sobel:

1
2
3
4
5
6
7
8
9
10
11
uint32_t HashJS(const char *data, uint32_t len)
{
  uint32_t hash = 1315423911;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash ^= (hash << 5) + (*data) + (hash >> 2);
  }

  return hash;
}

Esta realiza una buena distribución de los hash en muchos tipos diferentes de secuencias de datos:

1
2
3
4
5
6
7
8
9
10
11
uint32_t HashSDBM(const char *data, uint32_t len)
{
  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = (*data) + (hash << 6) + (hash << 16) - hash;
  }

  return hash;
}

Esta realiza un simple hashing rotativo/aditivo:

1
2
3
4
5
6
7
8
9
10
11
uint32_t HashBP(const char *data, uint32_t len)
{
  uint32_t hash = 0;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash = (hash << 7) ^ (*data);
  }

  return hash;
}

Y por último, ésta hecha a partir de las anteriores, también es una mezcla de hash rotativo y aditivo:

1
2
3
4
5
6
7
8
9
10
11
12
13
uint32_t HashAP(const char *data, uint32_t len)
{
  uint32_t hash = 0xAAAAAAAA;

  for (uint32_t i = 0; i < len; data++, i++)
  {
    hash ^= ((i & 1) == 0) ?
            (hash << 7) ^ (*data) * (hash >> 3) :
            ~((hash << 11) + ((*data) ^ (hash >> 5)));
  }

  return hash;
}