Как работает хеш-таблица / ассоциативный массив на пальцах?

Question

[l4m3r]

Я реально не могу понять, хоть и прочитал статьи на вики, в гугле и ещё тут.
Вот, допустим, есть массив:

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

Как достигается O(1) при обращении к $arr['c']? Я правильно понимаю, что при компиляции php-скрипта, интерпретатор создает flat-массив из count($arr) указателей. Далее, выполняется некая хеш-функция к каждому ключу возвращающая индекс (кстати, что это за хеш-функция такая? Ведь обычно же функции вроде md5, sha возвращают длинную строку). Потом по этому индексу мы храним указатель на value (предварительно выделив память под это)?
А сами ключи где хранятся (если надо получить array_keys, например)? Для плоских массивов $arr = [1, 2, 3, 4] тоже также всё работает?

Comments

[0ffff0]

Алексей Тен, не знаете значит, сами?

[Дмитрий]

l4m3r, https://habr.com/ru/company/oleg-bunin/blog/445512/

[Сергей Горностаев]

Дмитрий, человек не понимает базовую структуру данных, а вы ему статью про оптимизацию байткода.

[Сергей Горностаев]

Бхаргава - "Грокаем Алгоритмы", глава 5. Крайне просто и с картинками расписано, как работают хеш-таблицы.

[Дмитрий]

Сергей Горностаев, пусть читает

[Дмитрий]

Сергей Горностаев, мне другое непонятно, зачем это ему?

[Сергей Горностаев]

Дмитрий, стремление к знаниям, желание заглянуть в суть вещей - это хорошо.

[l4m3r]

Дмитрий, в смысле - "зачем". Странный вопрос.

[Roman]

l4m3r, Хотите познать дзен?

Я реально не могу понять, хоть и прочитал статьи на вики, в гугле и ещё тут.

Что бы по-честному разобраться https://habr.com/ru/company/mailru/blog/308240/
php-src/ext/standard/array.c
php-src/ext/hash/hash.c

Answer 1

[Developer]

в данном случае хэш-функция возвращает 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-...

Comments

[l4m3r]

А какая хеш-функция используется в php тут?

[Developer]

l4m3r, это не суть важно. Но если очень надо - гугл

[Ryabos]

Цель хэш-функции превратить объект, используя его содержимое, в целочисленное значение

Великолепно сказано, серьезно! Одна фраза все ставит на места

Answer 2

[Иван]

Не знаю как именно в 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]

Ну это в самом примитивном варианте. Естественно нужно решать коллизии. Но это не так страшно, как искать обычным поиском в большом не отсортированном массиве или списке.