I wrote: I will attempt to give a "short" answer to your "why not?" question. There may be some slight technical inaccuracies in pursuit of brevity. Also I will need some "C lingo" to explain what a Perl hash table actually "is", "under the covers". Underlining added for emphasis.

I am actually surprised that there weren't more: "hey, you got detail X wrong" posts!

My goal was to explain the basic idea and then show things like the scalar value of %hash which the user can access (added to my post using actual Perl code). Perl is very much a "live language" and updates are on-going. Its been maybe 5+ years since I looked seriously "at the guts".

Update:
I see the posts with various links to "Perl Guts". Whether the OP needs that level of detail is up to him. I tried to answer this basic question: is there a perlVar or function that is the TRUE array of hash key and one of values that,when changed, changes the keys or values?

Perl is like an onion. To use an onion, first you have to take the thin skin off. Then you start slicing the onion. There are many layers. That is fundamental to what an onion is! So, how come some onion slices have a green thing in the middle? That is a level of detail that I didn't address and probably the OP doesn't need to know about in order to use an onion effectively. That is the best analogy that I can come up with at the moment. I hope that my post can be understood in time measured in minutes. To understand exactly everything about how Perl makes hashes, requires time measured in days, not minutes.

> when changed, changes the keys ...

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.

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

°) 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)