Well I think this is the easiest to answer, the basic mechanism is a hash-function mapping a key to an array-index for a lookup mechanism. °

And this means a stored key must be immutable , because that calculated array-index would change too.

Consequently there can't be a faster way than replacing the whole key-value pair with "delete OLD" + "store NEW".

All the other implementation details we discussed are about various other features and performance.

°) That's why Perl's associative arrays are called "hashes" in the first place.

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++;
[download]

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.

Read more... (2 kB)

> but the calculated array-index for the linked list containing that particular key can change based upon the size of the hash

Well yes, but in the case when the hash-table is doubled, the whole internal data is overhauled anyway and effectively a new hash is created.

The old linked lists can't be reused. (At least I don't see how this could be done, the collisions need to be reduced by using the new slots)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Regarding your update:

Thanks, very interesting! :)

Please pardon my C ignorance, but AFAIS is the second hashing version operating on the pointer to the key's string not the string itself.

Right?

This would have 3 consequences

• the randomization to avoid DoS attacks is based on the assumption that these pointers are not deterministic
• the keys are indeed mutable, as long as the new key fits into the allocated space of the old one -I. E. is shorter.
• memory management guarantees that those pointers are constant.° Last time I worked "close to the metal" MMUs were only an exotic feature allowing virtual addresses.

  I suppose all Perl ports control this issue?

  Like integrity of the hash after being swapped?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

°) or the function is stable modulo memory page boundaries. But this might make then predictable again