Ruby tdb 0.6.4
[ruby-tdb.git] / Hash_Functions
blobe285120665bf2cee7e2e2f1c109fb83b65fb1d24
1 = Brief overview of hash functions supported by Ruby TDB
3 Ruby TDB supports several alternative hash functions in addition to the
4 defaults supported by TDB upstream.  Hash functions behave and perform
5 differently depending on the key and type of keys you use.  We support
6 several popular hash functions (and will accept patches to support
7 more).
9 Changing hash functions on an already-created database will cause
10 corruption, so don't do it.
12 == TDB Upstream Defaults
14 * the default hash use by TDB is based on the hash algorithm from gdbm.
15   You may specify this by passing explicitly to TDB.new:
16   <code>:hash => :default</code>
18 * the new default (available via TDB::INCOMPATIBLE_HASH) is the Jenkins
19   {lookup3 hash}[http://www.burtleburtle.net/bob/c/lookup3.c].
20   <code>:hash => :jenkins_lookup3</code>
22 == SipHash
24 https://en.wikipedia.org/wiki/Sip_Hash
25 https://131002.net/siphash/
27 Currently (as of Ruby 2.1) the favored hash in Ruby for hash-flooding
28 protection.
30 * :siphash24 - the reference implementation
32 == Murmur family
34 The {Murmur}[https://sites.google.com/site/murmurhash/] family of hashes
35 are supported by Ruby TDB.  Most of these are not endian-neutral so
36 databases are no compatible between machines of different endianness and
37 were designed with x86 and x86_64 in mind (they may crash or not work on
38 other architectures).
40 * :murmur3a - The latest 32-bit version optimized for x86
41    https://code.google.com/p/smhasher/wiki/MurmurHash3
43 * :murmur2 - the simple and fast implementation
45 * :murmur2a - words of the author:
47       This is a variant of MurmurHash2 modified to use the
48       Merkle-Damgard construction. Bulk speed should be identical to
49       Murmur2, small-key speed will be 10%-20% slower due to the added
50       overhead at the end of the hash.
52       This variant fixes a minor issue where null keys were more likely to
53       collide with each other than expected, and also makes the algorithm
54       more amenable to incremental implementations. All other caveats from
55       MurmurHash2 still apply.
57 * :murmur2_aligned - a safer, but slower variant of :murmur2 designed
58   for platforms where unaligned 4-byte reads can crash the machine.
60 * :murmur2_neutral - endian/alignment-neutral version of the simple
61   implementation, half as fast according to the author.
63 * :murmur1 - simple and fast historical version
65 * :murmur1_aligned - according to the author, the performance of this
66   one should be as good or better than the simple version.
68 == FNV family
70 * :fnv1a - the recommended variant of the popular
71   {Fowler-Noll-Vo}[http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash_function]
72   hash function
74 == Bernstein hashes
76 * :djb3 - See http://www.cse.yorku.ca/~oz/hash.html
78 * :djb2 - See http://www.cse.yorku.ca/~oz/hash.html