Ищете качество производства Хэш-таблицы / реализации неупорядоченной карты, чтобы узнать?

Question

1. Ищите хороший исходный код на C или C ++ или Python, чтобы понять, как реализована хеш-функция, а также как реализована хеш-таблица с ее использованием.
2. Очень хороший материал о том, как хэш-функцияи реализация хеш-таблицы работает.

Заранее спасибо.

Answer 1

Хеш-таблицы являются центральными для Python, как в качестве типа 'dict', так и для реализации классов и пространств имен, поэтому реализация была усовершенствована и оптимизирована за эти годы.Вы можете увидеть источник C для объекта dict здесь .

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

Answer 2

Возникла проблема с вашим вопросом: существует столько типов хэш-карт, сколько есть вариантов использования.

Существует множество стратегий для решения проблемы коллизии и перераспределения хешей, в зависимости от имеющихся у вас ограничений. Конечно, вы можете найти среднее решение, которое в основном подойдет, но на вашем месте я бы посмотрел википедию (как предложил Деннис), чтобы понять различные тонкости реализации.

Как я уже сказал, вы в основном можете думать о стратегиях двумя способами:

• Обработка Hash Collision: Bucket, какого рода? Открытая адресация? Двойной хэш? ...
• Перераспределение: заморозить карту или линейную амортизацию?

Кроме того, вы хотите запекать в поддержку многопоточности? Используя операции atomic, можно получить многопоточные хеш-карты без блокировки, как это было доказано в Java Клиффом Кликом ( Google Tech Talk )

Как видите, не существует одного размера, который бы подходил им всем. Сначала я хотел бы изучить принципы, а затем перейти к деталям реализации.

• C ++ std::unordered_map использовать корзину связанных списков и заморозить стратегии карт, не уделяя должного внимания правильной синхронизации, как обычно, с STL.
• Python dict является основой языка, я не знаю стратегии, которые они выбрали

Answer 3

Когда вы хотите узнать, я предлагаю вам взглянуть на реализацию Java java.util.HashMap. Это понятный код, хорошо документированный и сравнительно короткий. Признается, что это ни C, ни C ++, ни Python, но вы, вероятно, не хотите читать предстоящую реализацию GNU libc ++ хеш-таблицы, которая прежде всего состоит из сложности стандартной библиотеки шаблонов C ++.

Для начала вам следует прочитать определение интерфейса java.util.Map. Тогда вы можете сразу перейти к деталям java.util.HashMap. И все, чего не хватает, вы найдете в java.util.AbstractMap.

Реализация хорошей хеш-функции не зависит от языка программирования. Основная задача этого состоит в том, чтобы отобразить произвольно большой набор значений в небольшой набор значений (обычно это какой-то целочисленный тип), чтобы результирующие значения были равномерно распределены.