Yes and No.
And this means a stored key must be immutable , because that calculated array-index would change too.
The stored key is immutable in this sense, but the calculated array-index for the linked list containing that particular key can change based upon the size of the hash.
This is true:
Consequently there can't be a faster way than replacing the whole key-value pair with "delete OLD" + "store NEW".
One hashing algorithm that has been used before in Perl is:
unsigned int hash = 0;
while (*s)
hash = hash * 33 + *s++;
s is a pointer to a null terminated ASCII string.
This runs "rocket fast".
On a modern processor, multiply by 33 is faster than left shift by 4 (times 32) and then an add.
--UPDATE ---
Just for fun, I attach actual C code from memtracker.h from 2010 and the 2013 update.
The program uses an integer as the "hash key". Some obvious performance enhancements mentioned in the comments to version 2 were not actually coded because it just didn't matter! The longer version is much, much faster. Shorter code does not equal faster code. The HTTP addresses in the code probably don't work anymore since they are more than a decade old! Also noteworthy: this code was only tested on a 32 bit machine.
/* MT_gen_hash_bits()
* Dan Bernstein's hash function - works great for short ASCII strin
+gs!
* This is an empirical thing that "just works" without mathematical
* proof. Noteworthy: this is algorithm used by Perl.
* http://burtleburtle.net/bob/hash/doobs.html
*/
unsigned int MT_gen_hash_bits (unsigned long int address)
{
char ascii[21]; // max 64 bit unsigned int is 20 decimal digits
sprintf (ascii, "%lu", address);
char *s = ascii;
unsigned int hash = 0;
while (*s)
hash = hash * 33 + *s++;
return hash;
}
/* MT_gen_hash_bits_version2()
* Thomas Wang's 64-bit hash function - works well for integers, and
+ is significantly
* faster than the DJB function since the key is not ASCII. It is a
+lso slightly
* better in distributing keys.
* http://www.concentric.net/~Ttwang/tech/inthash.htm
*/
unsigned int MT_gen_hash_bits (unsigned long int address)
{
address = (~address) + (address << 21); // address = (address << 21)
+ - address - 1;
address = address ^ (address >> 24);
address = (address + (address << 3)) + (address << 8); // address *
+265
address = address ^ (address >> 14);
address = (address + (address << 2)) + (address << 4); // address *
+21
address = address ^ (address >> 28);
address = address + (address << 31);
return (unsigned int)address;
}
