about summary refs log tree commit homepage
path: root/Hash_Functions
blob: e285120665bf2cee7e2e2f1c109fb83b65fb1d24 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
= Brief overview of hash functions supported by Ruby TDB

Ruby TDB supports several alternative hash functions in addition to the
defaults supported by TDB upstream.  Hash functions behave and perform
differently depending on the key and type of keys you use.  We support
several popular hash functions (and will accept patches to support
more).

Changing hash functions on an already-created database will cause
corruption, so don't do it.

== TDB Upstream Defaults

* the default hash use by TDB is based on the hash algorithm from gdbm.
  You may specify this by passing explicitly to TDB.new:
  <code>:hash => :default</code>

* the new default (available via TDB::INCOMPATIBLE_HASH) is the Jenkins
  {lookup3 hash}[http://www.burtleburtle.net/bob/c/lookup3.c].
  <code>:hash => :jenkins_lookup3</code>

== SipHash

https://en.wikipedia.org/wiki/Sip_Hash
https://131002.net/siphash/

Currently (as of Ruby 2.1) the favored hash in Ruby for hash-flooding
protection.

* :siphash24 - the reference implementation

== Murmur family

The {Murmur}[https://sites.google.com/site/murmurhash/] family of hashes
are supported by Ruby TDB.  Most of these are not endian-neutral so
databases are no compatible between machines of different endianness and
were designed with x86 and x86_64 in mind (they may crash or not work on
other architectures).

* :murmur3a - The latest 32-bit version optimized for x86
   https://code.google.com/p/smhasher/wiki/MurmurHash3

* :murmur2 - the simple and fast implementation

* :murmur2a - words of the author:

      This is a variant of MurmurHash2 modified to use the
      Merkle-Damgard construction. Bulk speed should be identical to
      Murmur2, small-key speed will be 10%-20% slower due to the added
      overhead at the end of the hash.

      This variant fixes a minor issue where null keys were more likely to
      collide with each other than expected, and also makes the algorithm
      more amenable to incremental implementations. All other caveats from
      MurmurHash2 still apply.

* :murmur2_aligned - a safer, but slower variant of :murmur2 designed
  for platforms where unaligned 4-byte reads can crash the machine.

* :murmur2_neutral - endian/alignment-neutral version of the simple
  implementation, half as fast according to the author.

* :murmur1 - simple and fast historical version

* :murmur1_aligned - according to the author, the performance of this
  one should be as good or better than the simple version.

== FNV family

* :fnv1a - the recommended variant of the popular
  {Fowler-Noll-Vo}[http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash_function]
  hash function

== Bernstein hashes

* :djb3 - See http://www.cse.yorku.ca/~oz/hash.html

* :djb2 - See http://www.cse.yorku.ca/~oz/hash.html