Как работает хеш-таблица / ассоциативный массив на пальцах?
в данном случае хэш-функция возвращает int, а не строку. Цель хэш-функции превратить объект, используя его содержимое, в целочисленное значение - это и будет индекс для массива. Эту хэш-функцию надо грамотно написать, чтобы было минимум коллизий и для этого есть несколько базовых рекомендаций.
Внутри хэшмэп устроен так, что у него есть массив списков. То есть, по индексу, который мы вычислили с помощью хэш-кода, мы из массива по этому индексу (вот он, О(1)) забираем список (список - как раз и есть те самые коллизии и чем их меньше, тем короче будет список), в котором хранятся значения и забираем/добавляем нужное значение.
И тут есть замечания: если хэшкод всегда возвращает нам одно и то же число, то хэшмэп вырождается в список - все значения по любому из ключей будут храниться в списке, доступном по одному-единственному индексу.
В идеале хэшкод должен возвращать уникальное число для каждого объекта (но всегда одно и то же для объекта с таким же содержимым, ключом)
Общее понимание и прекрасное объяснение:
https://en.wikipedia.org/wiki/Hash_function
Функция для PHP:
https://php.ru/manual/function.spl-object-hash.html
Объяснение, почему нужно использовать простые числа на примере рекомендаций из книги "Effective Java" (объяснение есть и в википедии):
https://computinglife.wordpress.com/2008/11/20/why...
https://stackoverflow.com/questions/3613102/why-us...
https://medium.com/@biratkirat/learning-effective-...
Не знаю как именно в php реализована эта структура данных, но наверное вы можете прочитать об этом в официальной документации.
В md5 и sha возвращается не длинная строка, а поток битов, в случае md5 битов 128. Это просто их шестнадцатеричное представление. Смею предположить, что array_keys просто хранятся в списке, или в array list, это не так важно.
Откуда O(1)? От того, что при обращении, берется хеш от ключа, и по хешу получается индекс. А через индекс в массиве прямым доступом достается значение. Берешь хеш функцию, получаешь результат, а дальше делишь с остатком по размеру хеш таблицы. 
То есть вставка: i = hash(key) % hash_table_len
hash_table[i] = value
Выгрузка:i = hash(key) % hash_table_len
value = hash_table[i]
Ну это в самом примитивном варианте. Естественно нужно решать коллизии. Но это не так страшно, как искать обычным поиском в большом не отсортированном  массиве или списке.