diff options
author | Eric Wong <normalperson@yhbt.net> | 2010-11-26 02:27:17 +0000 |
---|---|---|
committer | Eric Wong <normalperson@yhbt.net> | 2010-12-01 09:45:32 +0000 |
commit | 58938c980f38a4581b4a0e8a780fffe7ac95bc93 (patch) | |
tree | ece822520cf8cbabe23f4559361afaf8346aa729 /Hash_Functions | |
download | ruby-tdb-58938c980f38a4581b4a0e8a780fffe7ac95bc93.tar.gz |
Diffstat (limited to 'Hash_Functions')
-rw-r--r-- | Hash_Functions | 67 |
1 files changed, 67 insertions, 0 deletions
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: + <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> + +== 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] |