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

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

0

IGPIGP, Постановка задачи предполагает что данные случайны. Не уверен что приведу хороший пример, но я больше думую в сторону транспортных задач (всякие хеши сессий, скрытые за NATом).
Коллизии приемлемы тогда, когда ситуация управляемая, но как управлять ситуацией не имея представления и содержимом ?
Интерфейс unordered_map/unordered_set даже не даёт средств для поиска коллизий. Эти структуры данных могут быть частью какого нибудь сервера, работающего в режиме 24/7.

Добавлено через 11 минут
Подмешивание псевдослучайных данных как средство от коллапса, когда стало много одинаковых данных, или мы пришли в подмножество данных где коллизии вероятны.

0

Сообщение от Pechkin80 Постановка задачи предполагает что данные случайны.

В каком смысле они случайны? Pechkin80, для выбора способа хранения и поиска нужно знать какими характеристиками описываются данные. Каждое поле это степень свободы.
То есть, порядок поступления (если в этом заключается случайность) не имеет тут значения. Для map/set - бинарных деревьев - имеет.

0

IGPIGP, Случайны по размеру, по содержимому, по порядку поступления. По природе своей случайны, например пакеты в сетевом трафике (плохой пример, но это первое что пришло в голову). Я не рассматриваю тут деревья, только un_ordered_map, unordered_set.

0

Сообщение от Pechkin80 Подмешивание псевдослучайных

Подмешать не проблема. Как доставать обратно будете?

Сообщение от Pechkin80 когда стало много одинаковых данных,

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

0

IGPIGP, Данные случайны. Нельзя их изучить. Зато надо управлять ситуаций. "Горе" это не инженерный термин.
Сами по себе структуры unordered_map/set данных без инструментов работы с ними, вызывают опаску. Както нужно вовремя бяку обнаружить или предотвращать. Подмешивание в общем случае может быть трёхкомпонентным. Первый компонент - постоянная случайная константа, второй компонент периодическая константа из масссива констант (изменяемая циклически по модулю) и третья компонента это случайное число для конкретного элемента, которое хранится вместе с хешем. Также нужен инструментарий обнаружения коллизий. Третья компонента конечно делает ненужным первые две компоненты.

0

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

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

Тогда по какому условию эти данные различаются, и кто будет заниматься высвобождением таблицы от них?

Так-то предположу что это должно быть что-то наподобие хэш-таблицы списков.

А вообще в этом случае нужно изменять алгоритм построения ключа.

0

Сообщение от TRam_ То есть предполагается, что мало того, что есть коллизии собственно по хэш-таблице, но ещё и одному и тому же ключу соответствует несколько наборов данных? Тогда по какому условию эти данные различаются, и кто будет заниматься высвобождением таблицы от них? Так-то предположу что это должно быть что-то наподобие хэш-таблицы списков. А вообще в этом случае нужно изменять алгоритм построения ключа.

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

0

Сообщение от Pechkin80 Данные случайны. Нельзя их изучить.

Постановка, - "хранить что угодно" далека от специфики вопроса. В идеале, предикаты сравнения, это не менее ценные данные класса, чем его прямые свойства. Если хватит терпения, попробуйте взглянуть в мой блог. Там есть статейка о поиске и хранении.

Сообщение от Pechkin80 Подмешивание в общем случае может быть

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

0

Pechkin80, а запрашивать данные тогда как собираетесь? Наподобие
"найти машину белого цвета "Лада Калина" " - и вываливается список из нескольких десятков тысяч "лад калин" с данными о них. Что со списком-то делать будете?

0

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

0

TRam_, Если программа заточена под конкретный тип данных, то это уже минус. Я не спорю, что никакая структура данных не является универсальной и надо выбирать структуру данных в зависимости от природы данных, но давайте не уводить обсуждение в сторону. Мне интересно знать есть ли готовый инструментарий работы с unordered_map/unordered_set а не философски разговоры о смысли жизни ?

0

Сообщение от Pechkin80 Мне интересно знать есть ли готовый инструментарий работы с unordered_map

Естественно. В шаблоне http://www.cplusplus.com/refer... dered_map/ имеется третьим параметром шаблона class Hash, который создаёшь и в котором нужно только переопределить

operator() Returns a hash value for its argument, as a value of type size_t. size_t is an unsigned integral type.

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

Обработка коллизий будет сделана автоматически. Но останется условие, что задав один ключ найдётся один набор данных. Или вставится/обновится один набор данных.


Случай 2, что нам надо для одного и того же ключа набирать много наборов данных. Тогда для unordered_map аргументом class T должен быть list<DataType>, т.е. по ключу получаете ссылку на список, и далее с этим списком поэлементно работаете. Роясь в данных, которые насобирали для этого ключа.

Добавлено через 7 минут
Если данные имеют неизвестный размер и каждый раз разное содержимое, внутри у DataType должен быть некий идентификатор содержимого (ведь нужно же знать, как и в каком порядке обрабатывать), указатель на содержимое (которое динамически выделено) и, если нужно, размер этого выделенного содержимого.

Всё. Можно заполнять и радоваться. Но не забыть сделать систему очистки от вышеупомянутого динамически выделенного содержимого, а остальное, в основном, контейнеры сгенерируют за вас. И удаление по ключу, и удаление по ключу и собственно итератору к контейнеру данных, и добавление/удаление "пустого"/"не пустого" списка или элемента списка.

0

TRam_, Спасибо, но мало, хотя использовать свой хеш тоже важно. Вот есть уже готовый unordered_map, который стоит себе в программе. Может даже его какой то разработчик ошибочно поставил и он нахрен не нужен, а программа тормозит. Вот задача провести диагностику и выявить действительно ли unordered_map был использован не по назначению или ключ выбран неудачно и что появилось много коллизий. А что касается кастомной хеш-функции, то её неплохо бы сделать дружественной (если уже не сделали). Чтобы она могла подмешивать, в зависимости от индекса массива по модулю Х.

0

Pechkin80, Создается впечатление, что вы вообще не понисаете, как работает хэш таблица.

Задача: Найти в таблице по ключу (ключ - строка "Вася Пупкин") данные о нем.

У вас есть только строка "Вася Пупкин". Откуда вы возьмете свои случайные подмешанные данные?

1

avgoor, Ну это не центральный вопрос про подмешивание. Потом подробно объясню и наверно даже скетч какойнить накатаю чтобы лучше было понятно, что я имею ввиду.

0

Pechkin80, по поводу диагностики - http://www.cplusplus.com/refer... ad_factor/

Чем меньше будет этот коэффициент, тем больше будет места хэш-таблицы приходиться на 1 пару элементов, тем меньше будет вероятность коллизий. Попробуйте поставить что-то наподобие 0.5 или вовсе 0.1 (на 1 добавляемый элемент будет приходиться 10 свободных мест, т.е. очень мала вероятность коллизий). Но это повлечёт увеличение расходов памяти на собственно таблицу. Значительно.

Проверять "степень заполнения" с помощью http://www.cplusplus.com/refer... ad_factor/

Сообщение от Pechkin80 А что касается кастомной хеш-функции, то её неплохо бы сделать дружественной

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

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

Сообщение от Pechkin80 задача провести диагностику

есть такое понятие как "трассировка программы". Погуглите что это такое.

0

Сообщение от Pechkin80 Потом подробно объясню и наверно даже скетч какойнить накатаю чтобы лучше было понятно, что я имею ввиду

Лучше прочитайте, что такое хэш таблица.
Пока что вы хотите улучшить что-то, непонимая как оно работает.

2

TRam_, max_load_factor, load_factor это я видел, но как найти коллизию в конкретном месте. Неужили только трассировка в отладчике ? Както иначе можно ? Есть же фичи для поиска утечек в памяти, может и для коллизий есть чтото подобное.

0

Сообщение от Pechkin80 но как найти коллизию в конкретном месте

http://www.cplusplus.com/refer... cket_size/ - пожалуйста. С примером вывода на экран.

Добавлено через 49 секунд
Просто я абсолютно не уверен, что тормоза программы связаны именно с коллизиями.

1

Сообщение от Pechkin80 но как найти коллизию в конкретном месте

Зачем? Есть коллизия. Что вы будете делать с этой информацией? Нет коллизии - что дальше? Зачем вообще это нужно?
При любой адекватной хэш функции (при равномерном распределении) вероятность коллизий одна и та же.

0