Unordered_map правильное применение

Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по этой теме.
Кто нибудь может ответить на простые вопросы:
1)Имеют ли данные контейнеры практический смысл в сравнение с вектором у которого свой аллокатор ?
2)Я так понимаю что контейнер малопригоден в готовом виде с параметрами по умолчанию ?
3)Если его использовать не в готовом, то хеши надо солить. а солить можно по разному и есть ли какая нибудь удачная реализация (так как чувствую что создам велосипед, если буду делать сам) ?
4)Чем отличается реализация boost unordered_map от std::unordered_map?

0

Сообщение от TRam_ чем больше элементов в таблице, тем больше должен быть её размер

Строго говоря нет, с использованием bucket'ов (как это сделано в С++) размер таблицы может быть 1 при этом я могу туда засунуть миллион объектов. От маленького размера пострадает скорость доступа по ключу, поэтому задача разработчиков stdlib найти компромис между размером таблицы и скоростью доступа.

Добавлено через 1 минуту

Сообщение от Pechkin80 Суть в то что пространство ключей меньше пространства данных.

Так и есть, а в чем тогда вопрос?

0

Kastaneda, Вопрос в том что вот мы имеем для примера такой случай: Нам надо работать с плохими данными, от которых хеш-ключ вызывают коллизии, и другого варианта для ключа, кроме как брать хеш от данных мы не имеем (Для меня загадка почему это 1% процент всех случаев, но не хочу уходить от сути), суть в том что нужно солить, чтобы избежать коллизии. Нездорово будет, если делать велосипед, так как это показывает узкий кругозор. интересно узнать есть ли чтото готовое. Я так понимаю стандартная функция std::hash ничего не солит.

0

Сообщение от Pechkin80 Я так понимаю стандартная функция std::hash ничего не солит.

Соль хэшей нам нужна тогда, когда для одинаковых данных нужны разные хэши. В случае хэш таблиц - для одинаковых данных нужны одинаковые хэши. Вот вы ищете в таблице строку "Вася Пупкин". Посчитали от нее хэш. А в таблице хэши соленые. Ну и толку от них? Коллизии будут. В этом ничего страшного нет.

1

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

0

0

TRam_, А соление как часть "нового" алгоритма не вариант ?

0

Сообщение от Pechkin80 А соление как часть "нового" алгоритма не вариант ?

"Соль" должна быть одинаковой для всех данных, что не позволяет называть ее солью.

0

Сообщение от Pechkin80 "нового"

Ну а как себе это представляешь? Был у тебя некий уникальный ключ, а к нему приписал случайное число, и пытаешься по этой сумме (которая стала случайной) определить, куда указывал ключ. Естественно сумма каждый раз будет разной, и найти ничего не удастся.

Добавлено через 1 минуту
Вот сами ключи, если их изначально нет, можно сгенерировать случайным образом (хотя тогда уж лучше просто построить таблицу указателей/индексов). Но если ключи УЖЕ есть, то тут нужно возиться с ними и исключительно с ними, без какого-либо рандома.

0

avgoor, Не хочу спорить о терминах. Суть в том что хеш короткий, а данные очень похожи одни на другие и имеют много тривиальных значений (мнооого нулей). Для всех алгоритмов хеширования это "некомфортная" ситуация. Алгоритмы любят, когда хеши длинные, а данные сильно отличаются. Так как хеш - индекс массива, то длинным его делать неразумно. STL контейнеры, насколько я вычитал вообще берут модуль от него чтоб получить индекс.

0

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

Нет.

Сообщение от Pechkin80 Алгоритмы любят, когда хеши длинные, а данные сильно отличаются. Так как хеш - индекс массива, то длинным его делать неразумно.

Нет.

Сообщение от Pechkin80 STL контейнеры, насколько я вычитал вообще берут модуль от него.

Bingo. (Если вы имеете ввиду остаток от деления).

Хэш должен обладать (и стандартная реализация обладает) такими свойствами:
1) Равномерное распределение.
2) Малое изменение в данных должно обеспечивать большое изменение в хэше. (Посчитайте md5 от соседних значений)
Из этих двух свойств, в частности, следует, что можно взять любой огрызок этого хэша - и он будет сам по себе удовлетворять этим свойствам.

0

Сообщение от avgoor Хэш должен обладать (и стандартная реализация обладает) такими свойствами: 1) Равномерное распределение. 2) Малое изменение в данных должно обеспечивать большое изменение в хэше. (Посчитайте md5 от соседних значений) Из этих двух свойств, в частности, следует, что можно взять любой огрызок этого хэша - и он будет сам по себе удовлетворять этим свойствам.

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

0

Сообщение от Pechkin80 то важным становится коеффициент заполнения этих таблиц и тут хеш-функции никому нечего не обещают

Ну как же не обещают то?
Коллизии будут. В этом нет ничего страшного...( Где то я это говорил. Дежавю наверное...)
Главное, чтоб все данные не свалились в одну строку таблицы. Если же вам это удастся - вы на пути к тому, чтобы на*бнуть всю современную криптографию.

0

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

0

Сообщение от Pechkin80 защитой от коллизий

Где вы видели такое требование? Еще раз коллизия в хэш таблице - штатная ситуация.

0

avgoor, думаю он имел в виду уменьшение количества коллизий.

0

Сообщение от Pechkin80 Нам надо работать с плохими данными, от которых хеш-ключ вызывают коллизии

Pechkin80, плохих данных не бывает. Бывают плохие постановки задачи. Фактически одинаковость, это, будничным языком выраженная, эквивалентность. То есть, если ученики в классе сравниваются по массе, то девочки и мальчики с разными оценками, волосами, велосипедами, но одинаковыми массами будут "одинаковы". Это я к тому, что данные для внятного анализа должны быть хорошо различимы. Для этого имеет смысл выбирать характеристики, по которым "степень уникальности" объектов наиболее высока. Если же объекты ею по своей природе не обладают (бильярдные шары и все белого цвета), то тогда придётся нумеровать. Беда такой задачи в том, что сами объекты не имеют такого качества как номер и если их нельзя пометить (как клеймят лошадей), то потом жизнь не принесёт радости . То есть, если предметы плохо изучены или описаны, то анализировать просто нечего.
Расскажите о данных и задаче. Именно природой данных и задачей определяется тип контейнера.
Поиск в контексте unordered_map и массивов, это в принципе разные вещи. Для хеш-массива в идеальном варианте (где он неотличим от map) поиск вообще отсутствует, как таковой.

1

std::unordered_map спроектирован учитывая коллизии, и их может быть миллионы. От части в этом и роль комитета стандартизации - придумать безупречно надежный контейнер. Поэтому дискуссия о коллизиях в std::unordered_map просто бессмысленна, т.к. они там предусмотрены в бесконечном колличестве.

0

Сообщение от Kastaneda std::unordered_map спроектирован учитывая коллизии

это его свойство, конечно, но

Сообщение от Kastaneda их может быть миллионы

это вполне нормально, если данных, скажем - триллионы.

Сообщение от Kastaneda Поэтому дискуссия о коллизиях в std::unordered_map просто бессмысленна

почему? Тема достаточно сложна и интересна. Значит есть о чём и поговорить. Лишь бы не без толку, конечно.

0

Сообщение от IGPIGP Тема достаточно сложна и интересна.

Только по сути больше имеет отношение к алгоритмам чем к С++.

0

Сообщение от Новичок Только по сути больше имеет отношение к алгоритмам чем к С++.

В этом есть правда. Но не вся. Хеш-массив, как массив указателей (по сути), интересен и с точки зрения возможных реализаций и тут плюсы как раз в тему.

0