Зачем нужны хэши

Здравствуйте, мне иногда приходится указывать различные типы данных в других типах данных, которые его не поддерживают то, что я в ней пишу. Пример: set<set<int>>. Для этого приходится писать 2 структуры - hash и equal (set<set<int>, hash, equal>). С equal все понятно - она нужна для того, чтобы c++ понял как сравнивать данный тип, но hash зачем? Что будет если я напишу плохую hash функцию? Допустим она будет выдавать всегда одно значение. И вообще зачем она нужна и где используется?

Заранее спасибо)

0

Сообщение от Алексей1153 первые 2 байта длины + 6 первых байтов содержимого

если я правильно понял (если нет - пример, пожалуйста), то будут коллизии, поэтому так не годится

0

Royal_X, коллизии обязательно будут, не нужно их бояться

0

Алексей1153, выше я уже писал, почему вектор интов тоже не вишенка и не годится для серьезного движка, равно как уже писал, как нужно это сделать правильно.
Но в рамках обсуждения вычисления хеша для вектора интов, полагаю, что разумнее будет посмотреть как это реализовано в boost, ибо вроде там это всё есть. В boost хеши лучше разработаны, чем в стандартной библиотеке. По крайней мере, еще давно искал функцию для комбинирования хешей, но не нашел в стандартной библиотеке, хотя в boost она есть (hash_combine) и реализация довольно простая. Не понимаю, почему не добавят в стандартную библиотеку...

0

Сообщение от 2010142118 Пример: set<set<int>>

Ну и загнул. И как это упорядочить контейнеры std::set? Хотя это вполне допустимо, но ответы выше - самый лучший совет.
С++11
РЕАЛИЗАЦИЯ ХЕШ-НАБОРА БИБЛИОТЕКИ STL - КЛАССЫ STD::UNORDERED_SET И UNORDERED_MULTISET
Конетйнеры UNORDERED_SET И UNORDERED_MULTISET сортируют элементы (которые одновременно являются ключами) на основании предиката std::less<T> или предиката, предоставленного пользователем. Поиск в отсортированном контейнере быстрее, чем в неотсортированном, таком, как вектор, а метод sort() обеспечпвает логарифмическую сложность. Это означает, что время, потраченное на поиск элементов в наборе, не прямо пропорционально количеству элементов в нем, а скорее его логарифму. Таким образом, поиск среди 100 000 элементов осуществляется вдвое дольше, чем среди 100 элементов ((так, 100^2 = 10 000 или log₁₀₀(10 000) = 2хlog₁₀₀(100)).
Однако даже этого существенного увеличения производительности по сравнению с неотсортированным контейнером (где продолжительность поиска прямо пропорциональна количеству элементов) иногда недостаточно. Программисты и математики упорно ищут способ сортировки и вставки за постоянное время, и одним из них является реализация на базе хеша, где хеш-функция используется для определения индекса сортировки. Добавляемые в хеш-набор элементы сначала обрабатываются хеш-функцией, которая создает уникальный индекс ячейки, в которой они размещаются. Библиотека STL предоставляет свой вариант хеш-набора в виде класса контейнера std::unordered_set.
СОВЕТ Чтобы использовать КЛАССЫ STD::UNORDERED_SET И UNORDERED_MULTISET включите в код заголовок:
#include <unordered_set>
Пименение этого класса не слишком отличается от применения класса std::set:
// создание экземпляра
unordered_set <int> userInt
// вставка элемента
userInt.insert(1000);
// find():
auto iPairThousand = userInt.find(1000);

if (iPairThousand != userInt.end())
cout << *iPairThousand << endl;

Но все же важнейшей из особенностей контейнера unordered_set является доступность хеш функции, отвечающей за решение о порядке сортировки:
unordered_set <int>::hasher HFn = userInt.hash_function();

0

Сообщение от Royal_X Во-первых, в стандартной библиотеке hash поддерживает только вектор булок, но не другие векторы.

Это снимает мой вопрос. Спасибо, теперь буду знать. Почитав ваш ответ, а потом инфу в сети и подумав, я понял, что вы правы. Хеш вектора целых найти можно, но без гарантий. Вот тут например:
https://stackoverflow.com/ques... r-a-vector
Но нужно же ещё массив интов (из нулей и единиц) запаковать в массив интов где каждый из 32 битов (скажем) это ноль или единица - элемент исходного массива. Несложно но муторно. Вы правы. Не знал я что вектора целых типов не поддерживаются стандартной хеш-библиотекой.

0