Как сделать создание Hashmap в C с нуля? Каковы будут параметры, которые будут приняты во внимание, и как вы проверите хэш-карту относительно того, насколько она хороша? Как и в том, что было бы тестовыми примерами, которые вам нужно выполнить, прежде чем вы скажете, что ваша хэш-карта завершена.Реализация HashMap
Ну, если вы знаете основы позади них, это не должно быть слишком трудно.
Обычно вы создаете массив под названием «ведра», который содержит ключ и значение, с необязательным указателем для создания связанного списка.
Когда вы обращаетесь к хеш-таблице с ключом, вы обрабатываете ключ с помощью специальной хэш-функции, которая возвращает целое число. Затем вы принимаете модуль результата, и это местоположение вашего индекса массива или «ведра». Затем вы проверяете непроверенный ключ с сохраненным ключом, и если он соответствует, то вы нашли нужное место.
В противном случае у вас было «столкновение», и он должен просканировать через связанный список и сравнить ключи, пока вы не сравните их. (обратите внимание, что некоторые реализации используют двоичное дерево вместо связанного списка для коллизий).
Заканчивать эту реализацию быстро хэш-таблицы:
Наилучший подход зависит от ожидаемого распределения ключей и числа столкновений . Если ожидается небольшое количество столкновений, то действительно не имеет значения, какой метод используется. Если ожидается много коллизий, то ожидается , что будет зависеть от стоимости повторной обработки или зондирования против манипулирования структурой данных расширяемого ковша.
Но вот исходный код пример An Hashmap Implementation in C
Как позднее пост говорит, что нам нужно обрабатывать столкновения также. Кроме того, реализация хэша имеет table_size, который подобен фиксированному. Если мы хотим динамически увеличивать размер хэш-карты, без программирования, зная, как это делается. Не могли бы вы что-нибудь предложить? – Thunderboltz
Изменение размера пространства ключа означает изменение хеш-функции или по крайней мере параметров функции и переименование всех записей. Для каждой карты разного размера требуется другой набор хеш-функций для поддержания желаемого распределения ключей. – TStamper
Ссылка была разбита –
Существует и другие механизмы для обработки переполнения, чем простой склонного связанного списка записей переполнения, которые, например, тратит много памяти.
Какой механизм для использования зависит, помимо прочего, от выбора хеш-функции и возможного выбора более одного (для реализации, например, двойного хэширования для обработки столкновений); если вы ожидаете часто добавлять предметы или если карта статична после заполнения; если вы намерены удалить предметы или нет; ...
Лучший способ реализовать это - сначала подумать обо всех этих параметрах, а затем не закодировать его самостоятельно, а выбрать зрелую существующую реализацию. В Google есть несколько хороших реализаций - например, http://code.google.com/p/google-sparsehash/
Имея значение для алгоритмов, sparsehash является реализацией хэш-карты на C++. Если вы ищете чистые преграды с чистым C, смотрите в другом месте. –
Основная цель хэш-карты - хранить набор данных и обеспечивать постоянный поиск по времени с помощью уникального ключа. Есть два общих стилей реализации Hashmap:
Отдельное соединение предпочтительнее, если хешмап может иметь плохую хеш-функцию, нежелательно предварительно распределять память для потенциально неиспользуемых слотов, или записи могут иметь переменный размер. Этот тип hashmap может продолжать функционировать относительно эффективно, даже если коэффициент загрузки превышает 1,0.Очевидно, что в каждой записи требуется дополнительная память для хранения указателей связанных списков.
Хэш-карты, использующие открытую адресацию, обладают потенциальными преимуществами производительности, когда коэффициент нагрузки поддерживается ниже определенного порога (обычно около 0,7) и используется разумно хорошая хеш-функция. Это связано с тем, что они избегают потенциальных промахов в кэше и многих небольших распределений памяти, связанных со связанным списком, и выполняют все операции в смежном массиве, предварительно выделенном. Итерация через все элементы также дешевле. Улавливание hashmaps с использованием открытой адресации должно быть перераспределено до более крупного размера и перефразировано для поддержания идеального коэффициента загрузки, или они сталкиваются со значительным снижением производительности. Коэффициент их загрузки не может превышать 1,0.
Некоторые ключевые показатели эффективности для оценки при создании HashMap будет включать в себя:
Вот гибкая реализация хэш-карты, которую я сделал. Я использовал открытую адресацию и линейное зондирование для разрешения конфликтов.
Помимо LL и деревьев, вы можете иметь хеш-карту для каждого ведра, которая использует другой хеш для обработки столкновений. – sudo