about summary refs log tree commit homepage
path: root/Hash_Functions
diff options
authorEric Wong <normalperson@yhbt.net>2010-11-26 02:27:17 +0000
committerEric Wong <normalperson@yhbt.net>2010-12-01 09:45:32 +0000
commit58938c980f38a4581b4a0e8a780fffe7ac95bc93 (patch)
treeece822520cf8cbabe23f4559361afaf8346aa729 /Hash_Functions
Diffstat (limited to 'Hash_Functions')
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
+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]