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

Я реально не могу понять, хоть и прочитал статьи на вики, в гугле и ещё тут.
Вот, допустим, есть массив:
$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] тоже также всё работает?
  • Вопрос задан
  • 657 просмотров
Решения вопроса 2
samodum
@samodum
в данном случае хэш-функция возвращает 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-...
Ответ написан
Kurku
@Kurku
Погромист
Не знаю как именно в 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]

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
SegmentStream Москва
от 250 000 до 350 000 руб.
Aurora Infinity Москва
от 60 000 до 120 000 руб.
HTML Academy Санкт-Петербург
от 150 000 до 180 000 руб.
24 июн. 2019, в 17:46
5000 руб./за проект
24 июн. 2019, в 17:44
700 руб./за проект
24 июн. 2019, в 16:55
5000 руб./за проект