Ответы пользователя по тегу Алгоритмы
  • Как работает хеш-таблица / ассоциативный массив на пальцах?

    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]

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