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