sdbm Algorithm
The SDBM (Sedgewick's Dynamic Bit Manipulation) algorithm is a non-cryptographic, hash function primarily used in database and file management systems for generating unique hash values. It was originally used in the NDBM (New Database Manager) library, and later became popular as the default hashing function in various programming languages and libraries, such as Perl, Ruby, and Unix. The algorithm operates on a per-character basis, iteratively applying a simple transformation to a running hash value while processing each character in the input string. This results in a relatively fast and efficient hashing process that minimizes the likelihood of hash collisions while maintaining a simple and easy-to-implement design.
The core principle of the SDBM algorithm is to generate a hash value by multiplying the previous hash value by a constant (65599) and adding the ASCII value of the current character, modulo 2^32. This process is applied iteratively for each character in the input string, starting with an initial hash value of 0. The constant 65599 is chosen as it is a large prime number, which helps in distributing the hash values more evenly across the possible output range. The SDBM algorithm's simplicity makes it suitable for scenarios where a fast and efficient hashing function is needed, without the need for strong cryptographic properties. Despite its age and simplicity, the SDBM algorithm is still widely used in various applications due to its reasonable performance and ease of implementation.
% sdbm: implements the sdbm-hash algorithm
% argument: str of type string
% returns: double
function ans = sdbm(str)
hash = 0;
for ch = str
hash = double(ch) + bitshift(hash,6) + bitshift(hash,16) - hash;
endfor
ans = hash;
endfunction
