Какие хэш-функции по умолчанию используются языками программирования для словарей / ассоциативных массивов? - PullRequest
Новая
       33

Какие хэш-функции по умолчанию используются языками программирования для словарей / ассоциативных массивов?

0 голосов
/ 27 августа 2018

Поэтому мне было любопытно, когда я узнал, что словари или ассоциативные массивы обычно реализуются с помощью хеш-таблиц.Прочитав о хеш-таблицах, я наткнулся на хеш-функции, я узнал, что существуют различные хеш-функции, такие как md5, md6, sha-1 и т. Д. Я не смог найти, какая хеш-функция используется такими языками программирования, как python, C ++, ява?

1 Ответ

0 голосов
/ 27 августа 2018

Это ... не тот же тип хеш-функции D:

Для хеш-функций , код должен вычислять соответствующий хеш на основе объектных данных такой, что соответствует требованиям равенства.Он также должен быть «хорошо распределенным» и «быстрым».Таким образом, большинство хеш-таблиц часто представляют собой 32-битные значения, использующие те или иные вычисления.В конце дня этот хеш используется для выбора из гораздо меньшего пула блоков .

Хеш-таблицы обычно вычисляются непосредственно (или со знанием) объектовбыть добавленным в хеш-таблицу - то есть, как правило, криптографические хеш-функции не участвуют в хеш-таблицах.Типичная функция Java hashCode () , определенная для объекта, добавляемого в хеш-таблицу, например может выглядеть следующим образом: 

int hash = 7;
hash = 31 * hash + (int) int_field;
hash = 31 * hash + (str_field == null ? 0 : str_field.hashCode());
// etc.
return hash;

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

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

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

Криптографические хеши обычно работают с произвольным фрагментом данных или потоком байтов.

Желаемые характеристики хеш-таблицы:

  • Детерминистический
  • Равномерное распределение / предотвращение кластеризации
  • Скорость, скорость, скорость

Криптографические хеши имеют дополнительные характеристики, помимо хеш-таблицы:

  • Невозможно создать сообщение из его хеш-значения
  • Невозможно найти два разных сообщения с одинаковым хеш-значением
  • (Хотя криптографические хеши должны также Быть быстрым, скорость во многом вторична дополнительным требованиям.)

Языки программирования поддерживают широкий спектр различных криптографических функций.графические хеш-функции через их стандартные библиотеки и / или сторонние библиотеки .Более известный хеш (например, MD5 / SHA-x), как правило, будет иметь универсальную поддержку, в то время как для чего-то более специализированного (например, MD6) может потребоваться дополнительное усилие для поиска реализации для.

С другой стороны,как показано выше, многие «функции» хеш-таблицы реализуются непосредственно в объекте (ах), участвующих в хеш-таблице, следуя стандартному шаблону, при этом некоторые языки (и IDE) предоставляют помощь для сокращения ручного кодирования.В качестве примера, C # предоставляет стандартную реализацию GetHashCode, основанную на отражении, для структурных типов.

...