How does a hash table / associative array work on fingers?

Question

PHP

I really can’t understand, even though I read the articles on the wiki, on Google and here.
Let's say we have an array:

$arr = [
   'a' => 111,
   'b' => 222,
   'c' => 444,
   5 => 555,
]

How is O(1) achieved when accessing $arr['c']? I understand correctly that when compiling a php script, the interpreter creates a flat array from count($arr) pointers. Next, a certain hash function is performed for each key, returning an index ( by the way, what kind of hash function is this? After all, usually functions like md5, sha return a long string). Then, at this index, we store a pointer to value (having previously allocated memory for this)?
And where are the keys themselves stored (if you need to get array_keys, for example)? Does $arr = [1, 2, 3, 4] also work for flat arrays?

Answer 1

in this case, the hash function returns an int, not a string. The purpose of the hash function is to turn an object, using its contents, into an integer value - this will be the index for the array. This hash function must be written correctly so that there is a minimum of collisions, and for this there are several basic recommendations.
Internally, the hashmap is designed to have an array of lists. That is, according to the index that we calculated using the hash code, we take the list from the array at this index (here it is, O (1)) (the list is just those very collisions and the fewer there are, the shorter it will be list) in which the values ​​​​are stored and pick up / add the desired value.
And here there are remarks: if the hashcode always returns the same number to us, then the hashmap degenerates into a list - all values ​​for any of the keys will be stored in a list accessible by a single index.
Ideally the hashcode should return a unique number for each object (but always the same for an object with the same content, key)
General understanding and great explanation:
https://en.wikipedia.org/wiki/Hash_function
Function for PHP:
https ://php.ru/manual/function.spl-object-hash.html
An explanation of why you need to use prime numbers using the recommendations from the book "Effective Java" as an example (there is an explanation on Wikipedia):
https://computinglife.wordpress. com/2008/11/20/why...
https://stackoverflow.com/questions/3613102/why-us...
https://medium.com/@biratkirat/learning-effective-...