структура типа хеш-таблицы не STL

Question

Есть ли способ написать простую хеш-таблицу с ключом в виде «строк» ​​и значением в качестве частоты, чтобы не было коллизий? Не будет удаления из хеш-таблицы, и если объект уже существует в хеш-таблице, просто обновите его частоту (сложите их вместе).

Я думал, что мог бы быть алгоритм, который может вычислить уникальное число из строки, которая будет использоваться в качестве индекса.

Да, я избегаю использования всех конструкций STL, включая unordered_map.

Answer 1

Вы можете использовать любой идеальный генератор хешей, например, gperf

Список можно посмотреть здесь: http://en.wikipedia.org/wiki/Perfect_hash_function

PS.Возможно, вы все равно захотите использовать карту вместо плоского массива / вектора в случае, если отображаемый домен станет слишком большим / разреженным

Answer 2

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

Теперь возможно снизить вероятность коллизий, используя хорошую хэш-функцию и убедившись, что ваша таблица огромна. По сути, вам нужен достаточно большой стол, чтобы вероятность вызова Дня Рождения была достаточно низкой, чтобы удовлетворить вас. Тогда вы просто используете n битов вывода SHA-1, и 2 ^ n будет вашим размером таблицы.

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

Answer 3

Это действительно зависит от того, что вы подразумеваете под «простым».

Std :: map - довольно простой класс. Тем не менее, он использует красно-черное дерево со всеми скрытыми вставками, удалениями и балансировкой, и он настроен на обработку любого заказываемого типа в качестве ключа и любого типа в качестве значения. Большинство классов карт используют аналогичную реализацию и избегают каких-либо функций хеширования.

Хеширование без коллизий не является тривиальным вопросом. Пожалуй, самый простой способ - Pearson Hashing .

Похоже, у вас есть 3 варианта:

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

2. Загрузите и используйте отличную библиотеку хеширования, которая уже существует. Конечно, вам нужно беспокоиться о возможности развертывания.

3. Использовать класс карты STL. Он встроен, хорошо документирован, прост в использовании, гибок в использовании и полностью кроссплатформенен. Это кажется «самым простым» решением.

Если я могу спросить, почему вы избегаете STL?