@Pechkin80

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

0

@Kastaneda

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

Добавлено через 1 минуту
Так и есть, а в чем тогда вопрос?

0

@Pechkin80

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

0

@avgoor

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

1

@TRam_

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

0

@Kastaneda

0

@Pechkin80

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

0

@avgoor

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

0

@TRam_

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

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

0

@Pechkin80

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

0

@avgoor

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

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

0

@Pechkin80

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

0

@avgoor

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

0

@Pechkin80

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

0

@avgoor

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

0

Новичок

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

0

IGPIGP

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

1

@Kastaneda

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

0

IGPIGP

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

0

Новичок

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

0

IGPIGP

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

0