Какая хеш-функция используется в словаре (hash_table)?
Я пишу переводчик языка.
Есть проблема: я хочу создать словарь типов, где вы можете поместить значение любого типа по индексу, это значение любого типа (простой [int, float, string] или сложный [список, массив, словарь] простых типов или комплекса простых типов …). Это так же, как в Python-Lang.
Какой алгоритм хэш-функции я должен использовать?
Для строк есть много примеров хэшей — самый простой: сумма всех символов, умноженная на 31, деленная на HASH_SIZE, то есть это простое число.
Но для РАЗНЫХ ТИПОВ, я думаю, это должен быть более сложный алгоритм.
Я нахожу SHA256, но не знаю, как использовать тип результата «unsigned char [32]» для адресации в хэш-таблице — это намного больше, чем ОЗУ в компьютере.
благодарю вас.
Решение
В C ++ 11 есть хеш-таблицы, новейший стандарт C ++ — std :: unordered_map, std :: unordered_set.
РЕДАКТИРОВАТЬ:
Поскольку каждый тип имеет свое распределение, обычно у каждого типа есть своя хеш-функция. Вот как это делается в Java (метод .hashCode (), унаследованный от Object), C #, C ++ 11 и многих других реализациях.
EDIT2:
Типичная хеш-функция делает две вещи:
1.) Создать представление объекта в натуральном числе. (это то, что делает .hashCode () в Java)
Например — строка «CAT» может быть преобразована в:
67 * 256^2 + 65 * 256^1 + 84 = 4407636
2.) Сопоставьте это число с позицией в массиве.
Один из способов сделать это:
integer_part(fractional_part(k*4407636)*m)
Где k — это константа (Дональд Кнут в своей книге «Искусство программирования» рекомендует (sqrt (5) +1) / 2), m — размер вашей хеш-таблицы, а дробные_части и целые_части (очевидно) вычисляют дробную часть и целую часть действительного числа). ,
В вашей реализации хеш-таблицы вам нужно обрабатывать коллизии, особенно когда существует гораздо больше возможных ключей, чем размер вашей хеш-таблицы.
EDIT3:
Я читаю больше на эту тему, и это выглядит как
67 * 256 ^ 2 + 65 * 256 ^ 1 + 84 = 4407636
действительно плохой способ сделать hash_code. Это связано с тем, что «someAAAAAABC» и «AAAAAABC» дают одинаковый хэш-код.
Другие решения
Хорошо, общий подход состоит в том, чтобы определить хеш-функцию как метод, принадлежащий типу.
Таким образом, вы можете вызывать разные алгоритмы для разных типов через общий API.
Это, конечно, влечет за собой то, что вы определяете классы-обертки для каждого типа «c», который вы хотите использовать в интерпретаторе.