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

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

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

0

Сообщение от 2010142118 И вообще зачем она нужна и где используется?

В алгоритмах поиска.

Сообщение от 2010142118 Допустим она будет выдавать всегда одно значение.

Поиск будет медленный (относительно поиска с правильно организованной хеш-функцией)
Т.е. с хорошей хеш функцией должно искаться по теории за O(1), а если хеш всех элементов одинаков - то будет искаться за O(n)

1

Сообщение от 2010142118 но hash зачем?

Ну так надо почитать литературу по азам хэшированных структур данных. Там все будет описано.

А уж затем приходить в форум с конкретными вопросами по непонятным местам.

Сообщение от 2010142118 Что будет если я напишу плохую hash функцию?

Если хэш-функция корректна, но плоха, хэшированная структура данных будет работать корректно, но неэффективно.

Сообщение от 2010142118 Допустим она будет выдавать всегда одно значение.

Получится экстремальный пример корректной, но неэффективной работы. Фактически структура данных выродится в линейный список с линейным поиском по нему.

Сообщение от 2010142118 И вообще зачем она нужна и где используется?

Почитать литературу по азам хэшированных структур данных. Там все будет описано.

2

Сообщение от TheCalligrapher А уж затем приходить в форум

Зачем злой такой?

0

hash нужен для быстрого поиска бакета с коллизиями, а equal - для поиска внутри бакета

Сообщение от 2010142118 set<set<int>>

если речь про std::set, то мимо, он не использует хеш. std::unordered_set - использует

1

2010142118, хеширование, это способ (не однозначной, в общем случае) нумерации объектов. То есть, это отображение объектов класса, являющихся с точки зрения данных, матрицами, состоящими в свою очередь, из различных объектов на множество целых неотрицательных чисел. Такая операция позволяет хранить данные в массивах и обращаться к ним по индексу где индекс и есть хеш данного элемента. Хеширующая структура сама заботится о правильном размещении используя хеш-функцию, которую предоставляет пользователь. При поиске, эта же функция используется для определения требуемого индекса. Среди проблем нужно отметить две противостоящие задачи: - создание такой функции, которая более равномерно "размазывает" данные по массиву ("hesh" - размазывать), то есть, имеющей высокую разрешающую (различающую) способность и задача создания быстрой функции хеширования. Полная разрешающая способность, соответствует полной однозначности, но применяется редко. Например, задача хеширования строк приводит к компромиссному решению, как и многие другие. Ведь если выбрать для представления номера числа в системе счисления с основанием равным алфавиту, то можно и в множество unsigned long не поместиться, не говоря уже о том, что быстрой хеш-функция не будет. Отсюда и необходимость неоднозначности отображения. В способе основанном на "цепочках", например, элементы с одинаковым хешем формируются в группы (цепочки), а массив содержит указатели на эти цепочки. Чем меньше , в среднем размер цепочки, по массиву, тем лучше. Быстрые хеш-функции дают размер больше. При поиске, индекс даёт адрес группы моментально O(n). Но потом, нужно пройти по группе последовательно, для определения содержится ли тот элемет, что мы ищем, в массиве. Вот тут можно увидеть гибридное решение для структуры использующей сортированный массив адресных выражений на цепочки в сортированном списке содержащем адресные выражения на элементы списка, который не сортирован и хранит сами значения как некая куча. Всего - три уровня доступа, два из которых не прямые, в терминах контейнеров) Это не хеширование и не дерево. Но есть общие черты) Остальное почитайте, если найдется время и желание:
https://www.cyberforum.ru/blog... g4772.html

0

IGPIGP
Вы меня извините, но если бы я не знал что такое хэш - я бы хрен что понял.
Зачем люди так непонятно пишут??

Сообщение от IGPIGP это отображение объектов класса, являющихся с точки зрения данных, матрицами, состоящими в свою очередь, из различных объектов

что это?? зачем это нагромождение текста в этом месте?

0

KSergey9, это же IGPIGP. Всё стандартно.

0

KSergey9, я пишу так как считаю нужным. Когда люди ищут информацию о непонятном, они перелопачивают много разных источников, а картина складывается из фрагментов понятного в каждом из них. Хороший текст, как мне кажется, рассчитан как на разных читателей, так и на перспективу для одного. Кто-то поймёт сразу, кто-то позже.
Что касается отображения, то тут все немного математики, как однажды мудро отметил, любимый мною Байт. Если отображение множества X на множество Y (однозначное), не дошло в 6-м классе, туда и нужно возвращаться.

Сообщение от Croessmah это же IGPIGP. Всё стандартно

Croessmah, да. Это я. Но "стандартно", здесь применимо только с вашей точки зрения. А это, действительно, стандартно.

Сообщение от KSergey9 IGPIGP Вы меня извините, но

Не могу себе позволить такую роскошь. Я написал о хеш-структурах, несколько не так, как о них обычно пишут. И дал ссылку на структуру поиска совмещающую лучшие качества массива и списка. Такой штуковины не было до того. Это о стандартном и не стандартном. Я не хочу стучать копытом в грудь, но когда приходится, - ни чего не поделаешь. О критериях "неочевидность" и "новизна", я знаю, пожалуй поболее чем львиная доля присутствующих. Я изобретатель. Но некоторым недоступно, даже понятие "стандартность". Отсюда и возгласы. Но главное в данном диалоге заключается в критериях "полезность" и "практическая осуществимость". Я думаю, что любой взгляд полезен, если он не скушен или, по крайней мере, свеж. А уж то, осуществится ли понимание у конкретного читателя, зависит от читателя. Мы тут обсуждаем и вопросы, о которых просто не скажешь. А скажешь - упростишь и будут реплики похлеще вашей. Можно конечно послать всех спрашивающих в библиотеку. Но зачем мы тогда тут? Есть раздел C++ с названием без слов: "для новичков", но и там посылать учиться не этично. Если вопрос не соответствует уровню раздела, это дело модераторов.

0

2010142118, за всё время я только раз использовал хеши - при написании движка для крестиков-ноликов, когда реализовал хеш-таблицу. Причем, я не писал свою хеш функцию, а использовал из стандартной библиотеки std::hash<std::vector<bool>>. Свою хеш функцию люди пишут редко, как правило, функций стандартной библиотеки всегда хватает. Да и если написать плохую хеш функцию, то будут коллизии.

0

Сообщение от Royal_X Причем, я не писал свою хеш функцию, а использовал из стандартной библиотеки std::hash<std::vector<bool>>. Свою хеш функцию люди пишут редко, как правило, функций стандартной библиотеки всегда хватает.

Чисто чтобы придраться: std::hash - не функция, а класс.

(Быстро уходит.)

0

Сообщение от TheCalligrapher Чисто чтобы придраться

зачем?

Сообщение от TheCalligrapher не функция, а класс

Это если говорить о внутреннем представлении. Но даже в стандарте языка используется выражение hash function как синоним.

Сообщение от 2010142118 Что будет если я напишу плохую hash функцию? Допустим она будет выдавать всегда одно значение.

Будут коллизии. Как уже писал выше, лучше этого не делать, если вы не разбираетесь в алгоритмах вычисления хеша. Вместо этого использовать стандартную библиотеку.

Сообщение от 2010142118 И вообще зачем она нужна и где используется?

Выше уже писал, что я его использовал только один раз при написании движка для крестиков-ноликов (вообще, этот же движок можно переделать для любой другой антагонистической игры с нулевой суммой - шашки, шахматы и т.д., ведь, всего лишь меняется только эвристическая функция и при желании переделываются доп. оптимизации). Использовал там хеши в std::unordered_map, с помощью которого реализовал хеш-таблицу. Таким образом, я сокращал время поиска лучшего хода, т.к. поиск обращался к таблице.

Еще нечто похожее использовал при использовании алгоритма A*, когда писал головоломку "водопроводчик". Но тогда собсна никакая сложная хеш функция не понадобилась. У меня были объекты, которые имели координаты x и y, и нужно было каждой позиции дать уникальный id. Оказалось достаточно Cantor Pairing Function. Псевдокод такой:

0

Что бы не придраться.

Сообщение от Royal_X а использовал из стандартной библиотеки std::hash<std::vector<bool>>

Royal_X, а зачем вектор булок? Памяти не хватало?

0

Сообщение от IGPIGP Памяти не хватало?

это же хеш-таблица, она очень быстро заполняется, поэтому старался экономить память. По этой причине состояние доски представлялось в булках. Я еще резервировал память, чтобы сразу выделить память на корзинки (так намного экономнее). Более того, таблица так быстро заполняется, что должен быть лимит. Например, даже UCI - шахматные движки поддерживают выставление лимита, например, setoption name hash value 1024

0

Сообщение от Royal_X У меня были объекты, которые имели координаты x и y, и нужно было каждой позиции дать уникальный id. Оказалось достаточно Cantor Pairing Function.

Ценность в Cantor Pairing Function в абстрактной математике заключается в том, что она разработана с учетом того (и именно для того), что диапазон входных значений неограничен. Но в практическом программировании это обычно не так. Если вам нужно сформировать уникальный идентификатор из двух 16-битных значений - им можно просто конкатенировать 16+16 = 32 или, если вам нужна "близость близких", перемешать побитово (т.наз. "числа Мортона" https://graphics.stanford.edu/... bleObvious).

Вариантов много, но суть моего замечания в том, что всякие Cantor Pairing Functions - это следствие работы в тесных рамках того, что разрешается в абстрактной математике. В практическом программировании нам разрешается и дается намного больше и, соответственно, открывается масса более привлекательных вариантов.

0

Сообщение от Royal_X это же хеш-таблица, она очень быстро заполняется, поэтому старался экономить память.

Вектор с логическими переменными медленнее чем vector<unsigned>, потому что булки упакованы в машинное слово и на каждой операции с конкретным байтом распаковываются. То есть, такая фишка может пригодиться лишь если память, - бутылочное горлышко)

0

IGPIGP, я знаю, что вектор булок неидеален. На самом деле, vector<unsigned> тоже не вишенька. Правильнее будет через битовые строки, а для вычисления хеша вместо использования hash из стандартной библиотеки написать собственную функцию, реализовав Zobrist hashing. Именно так реализовано в сильнейшем шахматном движке - Stockfish. Я это к тому, что учить меня не надо, я всё отлично знаю, как делать правильно. Движок я написал за день и разумеется особо не углублялся и не всегда делал так, как правильно, а делал так, как мне было удобно. Собственно, первостепенная задача была создать работающий движок и эта задача была успешна выполнена. А дальше я просто потерял интерес и не стал улучшать движок. Но не думаю, что всё это интересно ТС. Он спрашивал, зачем нужна и где используется хеш-функция, я вот привел один пример из своего небогатого опыта программирования как хобби.

0

Сообщение от Royal_X Я это к тому, что учить меня не надо, я всё отлично знаю,

Я не учил, а просто, задал вопрос. Почему вектор целых, не вишенка, в контексте вопроса, я не понял. Он быстрее чем вектор булиней и именно это я имел ввиду. Моё разъяснение к не тому, что бы вас учить, а к тому зачем я задал вопрос. Хеш функция, в частности, не может обойти необходимость доступа к полям vector<bool>, а ведь мы говорим о скорости этой функции в данной теме. Смысл вопроса был в том, на какой системе вам не хватало памяти. Ну да ладно.

0

Сообщение от IGPIGP Почему вектор целых, не вишенка, в контексте вопроса, я не понял.

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

1

Royal_X, для вектора интов я бы взял в качестве хеша первые 2 байта длины + 6 первых байтов содержимого

0