Credits and References

DJB2 Hash Function

http://www.google.com/search?hl=en&lr=&q=djb2+hash&btnG=Search

http://www.cs.yorku.ca/~oz/hash.html

http://www.securityforest.com/downloads/bots/hash_login_2.c

This algorithm (k=33) was first reported by D. J. Bernstein many years ago in comp.lang.c. Another version of this algorithm (now favored by Bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.

Implemented in DWFCore::tDWFDJB2HashKernel.

FNV Hash Function

http://www.isthe.com/chongo/src/fnv

The basis of this hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by: Phong Vo (http://www.research.att.com/info/kpv) Glenn Fowler (http://www.research.att.com/~gsf/)

In a subsequent ballot round: Landon Curt Noll (http://www.isthe.com/chongo)

improved on their algorithm. Some people tried this hash and found that it worked rather well. In an EMail message to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.

FNV hashes are designed to be fast while maintaining a low collision rate. The FNV speed allows one to quickly hash lots of data while maintaining a reasonable collision rate. See: http://www.isthe.com/chongo/tech/comp/fnv/index.html for more details as well as other forms of the FNV hash. Comments, questions, bug fixes and suggestions welcome at the address given in the above URL.

Implemented in DWFCore::tDWFFNV1A32HashKernel, DWFCore::tDWFFNV1A64HashKernel.

Robert Jenkins Hash Function

http://burtleburtle.net/bob/hash/evahash.html

Implemented in DWFCore::tDWFJenk96CharHashKernel, DWFCore::tDWFJenk96WCharHashKernel.

Probabalistic Skip List Algorithm

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

The algorithm was developed by William Pugh (University of Maryland, College Park). This is a collection that maintains sort order using a highly efficient probabalistic distribution algorithm over a linked list using "skip links". The performance of this collection is excellent across search, insert, delete and linear-lookup.

Implemented in DWFCore::DWFSkipList.


Generated on Tue Jan 6 22:39:29 2009 for Autodesk DWF Core Library by  doxygen 1.4.5