From 58938c980f38a4581b4a0e8a780fffe7ac95bc93 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Fri, 26 Nov 2010 02:27:17 +0000 Subject: initial --- Hash_Functions | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 67 insertions(+) create mode 100644 Hash_Functions (limited to 'Hash_Functions') diff --git a/Hash_Functions b/Hash_Functions new file mode 100644 index 0000000..5289086 --- /dev/null +++ b/Hash_Functions @@ -0,0 +1,67 @@ += 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: + :hash => :default + +* the new default (available via TDB::INCOMPATIBLE_HASH) is the Jenkins + {lookup3 hash}[http://www.burtleburtle.net/bob/c/lookup3.c]. + :hash => :jenkins_lookup3 + +== Murmur family + +The {Murmur}[https://sites.google.com/site/murmurhash/] family of hashes +are supported by Ruby TDB. MurmurHash3 will be supported as soon as it +becomes finalized. 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). + +* :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 - The hash currently favored by Bernstein. + See [http://www.cse.yorku.ca/~oz/hash.html] + +* :djb2 - See [http://www.cse.yorku.ca/~oz/hash.html] -- cgit v1.2.3-24-ge0c7