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

Я реально не могу понять, хоть и прочитал статьи на вики, в гугле и ещё тут.
Вот, допустим, есть массив:
$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] тоже также всё работает?
  • Вопрос задан
  • 2619 просмотров
Решения вопроса 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]

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

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

Войти через центр авторизации
Похожие вопросы