Non-cryptographic hashing

Adam Harvey
@LGnome
New Relic

What?

Hash function

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer vitae ex nec nisl fermentum sodales in ut lectus.
61df8894 0ec572f8 19e37640 372ecf1b

MD5 SHA-1 SHA-256 SHA-512

Non-Cryptographic hash function

Non-Cryptographic hash function

Why?

Hash tables

What have I seen?

Is this valid?

Interoperability

It's fun?

How?

Goals

  • Fast
  • Well distributed output

Avalanche effect

00010000
00001000
00011000
00000000
000??000

Avalanche effect

00010000
00001000
00011000
00000000
???????? 

def hash_function(data: bytes) -> int:
  for chunk in md_pad(data):
    hash = cleverness(hash, chunk)

  return hash

Cleverness

  • Unsigned, fixed length integers
  • Bitwise operations (xor; bitshifts)
  • Multiplication

Integers

  0xffffffff
+ 0x00000001
= 0x00000000

Primes

FNV-1a

FNV-1a


uint32_t fnv1a32(const char *data, size_t len) {
  uint32_t hash = 2166136261;
  for (char *byte = data; byte < (data + len); byte++) {
    hash ^= *byte;
    hash *= 16777619;
  }
  return hash;
}

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
>   uint32_t hash = 2166136261;
    for (char *byte = data; byte < (data + len); byte++) {
      hash ^= *byte;
      hash *= 16777619;
    }
    return hash;
  }
hash:  1000 0001 0001 1100 1001 1101 1100 0101
 
*byte: (unset)

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
>   for (char *byte = data; byte < (data + len); byte++) {
      hash ^= *byte;
      hash *= 16777619;
    }
    return hash;
  }
hash:  1000 0001 0001 1100 1001 1101 1100 0101
 
*byte:                               0110 0001

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
    for (char *byte = data; byte < (data + len); byte++) {
>     hash ^= *byte;
      hash *= 16777619;
    }
    return hash;
  }
hash:  1000 0001 0001 1100 1001 1101 1010 0100
 
*byte:                               0110 0001

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
    for (char *byte = data; byte < (data + len); byte++) {
      hash ^= *byte;
>     hash *= 16777619;
    }
    return hash;
  }
hash:  1110 0100 0000 1100 0010 1001 0010 1100
 
*byte:                               0110 0001

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
>   for (char *byte = data; byte < (data + len); byte++) {
      hash ^= *byte;
      hash *= 16777619;
    }
    return hash;
  }
hash:  1110 0100 0000 1100 0010 1001 0010 1100
 
*byte:                               0110 0010

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
    for (char *byte = data; byte < (data + len); byte++) {
>     hash ^= *byte;
      hash *= 16777619;
    }
    return hash;
  }
hash:  1110 0100 0000 1100 0010 1001 0100 1110
 
*byte:                               0110 0001

fnv1a32("ab", 2)

  uint32_t fnv1a32(const char *data, size_t len) {
    uint32_t hash = 2166136261;
    for (char *byte = data; byte < (data + len); byte++) {
      hash ^= *byte;
>     hash *= 16777619;
    }
    return hash;
  }
hash:  0100 1101 0010 0101 0000 0101 1100 1010
 
*byte:                               0110 0001

Shootout

Goals

  • Fast
  • Well distributed output

Fast

Distribution

Input: words


A
a
aa
aal
aalii
aam
Aani
aardvark

Input: numbers


0
1
2
3
4
5
6
7

Input: Holmes

FNV-1a

FNV-1a

Corpus CPU time (ms) Collisions
Numbers 55.40 0
Words 68.12 5 (0.002%)
Holmes 3.13 0

FNV-1a

CRC32

CRC32


static const uint32_t crc32tab[256] = { /* ... */ };

uint32_t crc32(const char *data, size_t len) {
  uint32_t crc = 0xffffffff;
  const char *ptr;

  for (ptr = data; ptr < (data + len); ptr++) {
    crc = (crc >> 8) ^ crc32tab[(crc ^ (*ptr)) & 0xff];
  }

  return crc;
}

CRC32

Corpus CPU time (ms) % FNV-1a Collisions
Numbers 61.42 111% 0
Words 76.82 113% 8 (0.003%)
Holmes 6.23 199% 0

CRC32

MurmurHash3

MurmurHash3


uint32_t murmurhash3_32(const char *data, size_t len, uint32_t seed) {
  static const uint32_t c1 = 0xcc9e2d51;
  static const uint32_t c2 = 0x1b873593;
  static const uint32_t r1 = 15;
  static const uint32_t r2 = 13;
  static const uint32_t m = 5;
  static const uint32_t n = 0xe6546b64;

  uint32_t hash = seed;

  const int nblocks = len / 4;
  const uint32_t *blocks = (const uint32_t *) data;
  for (int i = 0; i < nblocks; i++) {
    uint32_t k = blocks[i];
    k *= c1;
    k = (k << r1) | (k >> (32 - r1));
    k *= c2;

    hash ^= k;
    hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
  }

  const uint8_t *tail = (const uint8_t *) (data + nblocks * 4);
  uint32_t k1 = 0;

  switch (len & 3) {
  case 3:
    k1 ^= tail[2] << 16;
  case 2:
    k1 ^= tail[1] << 8;
  case 1:
    k1 ^= tail[0];

    k1 *= c1;
    k1 = (k1 << r1) | (k1 >> (32 - r1));
    k1 *= c2;
    hash ^= k1;
  }

  hash ^= len;
  hash ^= (hash >> 16);
  hash *= 0x85ebca6b;
  hash ^= (hash >> 13);
  hash *= 0xc2b2ae35;
  hash ^= (hash >> 16);

  return hash;
}

MurmurHash3


uint32_t murmurhash3_32(const char *data,
                        size_t      len,
                        uint32_t    seed);

MurmurHash3


static const uint32_t c1 = 0xcc9e2d51;
static const uint32_t c2 = 0x1b873593;
static const uint32_t r1 = 15;
static const uint32_t r2 = 13;
static const uint32_t m = 5;
static const uint32_t n = 0xe6546b64;

uint32_t hash = seed;

MurmurHash3


const size_t nblocks = len / 4;
const uint32_t *blocks = (const uint32_t *) data;

for (size_t i = 0; i < nblocks; i++) {
  uint32_t k = blocks[i];

  k *= c1;
  k = (k << r1) | (k >> (32 - r1));
  k *= c2;

  hash ^= k;
  hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
}

MurmurHash3


const uint8_t *tail;
tail = (const uint8_t *) (data + nblocks * 4);

MurmurHash3


uint32_t k1 = 0;
switch (len & 3) {
  case 3:
    k1 ^= tail[2] << 16;
  case 2:
    k1 ^= tail[1] << 8;
  case 1:
    k1 ^= tail[0];

    k1 *= c1;
    k1 = (k1 << r1) | (k1 >> (32 - r1));
    k1 *= c2;
    hash ^= k1;
}

MurmurHash3


hash ^= len;
hash ^= (hash >> 16);
hash *= 0x85ebca6b;
hash ^= (hash >> 13);
hash *= 0xc2b2ae35;
hash ^= (hash >> 16);

return hash;

MurmurHash3

Corpus CPU time (ms) % FNV-1a Collisions
Numbers 69.10 125% 4 (0.002%)
Words 69.23 102% 6 (0.003%)
Holmes 0.95 30% 0

MurmurHash3

xxHash

xxHash


const uint32_t xxhash32_prime1 = 2654435761U;
const uint32_t xxhash32_prime2 = 2246822519U;
const uint32_t xxhash32_prime3 = 3266489917U;
const uint32_t xxhash32_prime4 = 668265263U;
const uint32_t xxhash32_prime5 = 374761393U;

inline uint32_t xxhash32_rotl(uint32_t x, int r) {
  return (x << r) | (x >> (32 - r));
}

inline uint32_t xxhash32_mix(uint32_t v, uint32_t chunk) {
  v += chunk * xxhash32_prime2;
  v = xxhash32_rotl(v, 13);
  return v * xxhash32_prime1;
}

uint32_t xxhash32(const char *data, size_t len, uint32_t seed) {
  const char *p = data;
  const char *end = data + len;

  uint32_t hash = 0;

  if (len >= 16) {
    uint32_t v1 = seed + xxhash32_prime1 + xxhash32_prime2;
    uint32_t v2 = seed + xxhash32_prime2;
    uint32_t v3 = seed;
    uint32_t v4 = seed - xxhash32_prime1;

    for (; p <= (end - 16); p += 16) {
      const uint32_t *chunk = (const uint32_t *) p;

      v1 = xxhash32_mix(v1, chunk[0]);
      v2 = xxhash32_mix(v2, chunk[1]);
      v3 = xxhash32_mix(v3, chunk[2]);
      v4 = xxhash32_mix(v4, chunk[3]);
    }

    hash = xxhash32_rotl(v1, 1) +
           xxhash32_rotl(v2, 7) +
           xxhash32_rotl(v3, 12) +
           xxhash32_rotl(v4, 18);
  } else {
    hash = seed + xxhash32_prime5;
  }

  for (; (p + 4) <= end; p += 4) {
    hash += *((const uint32_t *) p) * xxhash32_prime3;
    hash = xxhash32_rotl(hash, 17) * xxhash32_prime4;
  }

  for (; p < end; p++) {
    hash += ((uint8_t) *p) * xxhash32_prime5;
    hash = xxhash32_rotl(hash, 11) * xxhash32_prime1;
  }

  hash ^= hash >> 15;
  hash *= xxhash32_prime2;
  hash ^= hash >> 13;
  hash *= xxhash32_prime3;
  hash ^= hash >> 16;

  return hash;
}

xxHash


uint32_t v1 = seed + xxhash32_prime1 + xxhash32_prime2;
uint32_t v2 = seed + xxhash32_prime2;
uint32_t v3 = seed;
uint32_t v4 = seed - xxhash32_prime1;

xxHash


for (; p <= (end - 16); p += 16) {
  const uint32_t *chunk = (const uint32_t *) p;

  v1 = xxhash32_mix(v1, chunk[0]);
  v2 = xxhash32_mix(v2, chunk[1]);
  v3 = xxhash32_mix(v3, chunk[2]);
  v4 = xxhash32_mix(v4, chunk[3]);
}

xxHash


inline uint32_t xxhash32_rotl(uint32_t x, int r) {
  return (x << r) | (x >> (32 - r));
}

inline uint32_t xxhash32_mix(uint32_t v, uint32_t in) {
  v += in * xxhash32_prime2;
  v = xxhash32_rotl(v, 13);
  return v * xxhash32_prime1;
}

xxHash


hash = xxhash32_rotl(v1, 1) +
       xxhash32_rotl(v2, 7) +
       xxhash32_rotl(v3, 12) +
       xxhash32_rotl(v4, 18);

xxHash


if (len >= 16) {
  /* what you just saw */
} else {
  hash = seed + xxhash32_prime5;
}

xxHash


for (; (p + 4) <= end; p += 4) {
  hash += *((const uint32_t *) p) * xxhash32_prime3;
  hash = xxhash32_rotl(hash, 17) * xxhash32_prime4;
}

for (; p < end; p++) {
  hash += ((uint8_t) *p) * xxhash32_prime5;
  hash = xxhash32_rotl(hash, 11) * xxhash32_prime1;
}

xxHash


hash ^= hash >> 15;
hash *= xxhash32_prime2;
hash ^= hash >> 13;
hash *= xxhash32_prime3;
hash ^= hash >> 16;

return hash;

xxHash

Corpus CPU time (ms) % FNV-1a Collisions
Numbers 69.41 125% 2 (0.001%)
Words 73.97 109% 6 (0.003%)
Holmes 0.396 12.6% 0

xxHash

CityHash

CityHash32

CityHash64

CityHash128

CityHash32

20 byte blocks

More per block work compared to MurmurHash32

7 rotations and 2 swaps per block

CityHash32

Corpus CPU time (ms) % FNV-1a Collisions
Numbers 74.23 134% 5 (0.002%)
Words 68.92 101% 7 (0.003%)
Holmes 0.68 22% 0

CityHash32

SuperFastHash

SuperFastHash


inline uint16_t get16bits(const char *p) {
  return *(const uint16_t*)p;
}

uint32_t superfasthash(const char *data, size_t len) {
  uint32_t hash = 0;
  uint32_t tmp;
  size_t rem;

  rem = len & 3;
  len >>= 2;

  for (; len > 0; len--) {
    hash  += get16bits (data);
    tmp    = (get16bits (data+2) << 11) ^ hash;
    hash   = (hash << 16) ^ tmp;
    data  += 2*sizeof (uint16_t);
    hash  += hash >> 11;
  }

  switch (rem) {
    case 3:	hash += get16bits (data);
        hash ^= hash << 16;
        hash ^= data[sizeof (uint16_t)] << 18;
        hash += hash >> 11;
        break;
    case 2:	hash += get16bits (data);
        hash ^= hash << 11;
        hash += hash >> 17;
        break;
    case 1: hash += *data;
        hash ^= hash << 10;
        hash += hash >> 1;
  }

  hash ^= hash << 3;
  hash += hash >> 5;
  hash ^= hash << 4;
  hash += hash >> 17;
  hash ^= hash << 25;
  hash += hash >> 6;

  return hash;
}

SuperFastHash


for (; len > 0; len--) {
  hash  += get16bits(data);
  tmp    = (get16bits(data + 2) << 11) ^ hash;
  hash   = (hash << 16) ^ tmp;
  data  += 2 * sizeof(uint16_t);
  hash  += hash >> 11;
}

SuperFastHash


if (rem == 3) {
  hash += get16bits(data);
  hash ^= hash << 16;
  hash ^= data[sizeof(uint16_t)] << 18;
  hash += hash >> 11;
} else if (rem == 2) {
  hash += get16bits(data);
  hash ^= hash << 11;
  hash += hash >> 17;
} else if (rem == 1) {
  hash += *data;
  hash ^= hash << 10;
  hash += hash >> 1;
}

SuperFastHash


hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;

return hash;

SuperFastHash

Corpus CPU time (ms) % FNV-1a Collisions
Numbers 66.13 119% 23946 (10.152%)
Words 82.01 120% 54 (0.023%)
Holmes 9.68 310% 0

SuperFastHash

JSHash

Conclusions

Know your environment

Respect your standard library

Know your inputs

Small inputs

Large inputs

Know your requirements

Questions?

@LGnome

Resources