map vs unordered map

Если обычная std::map построено на основе бинарного дерева поиска(красно черного дерева), то unordered map на основе обычного бинарного дерева?

0

На основе хэш-таблицы

0

S_el, почему тогда std::map не реализовать через hash-table?

0

Сообщение от ReYalp почему тогда std::map не реализовать через hash-table?

Вы же сами написали:

Сообщение от ReYalp std::map построено на основе бинарного дерева поиска

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

0

IGPIGP, где можно почитать о хеш-таблицах(только о них)?У меня только поверхностные знания о них есть.

0

Сообщение от ReYalp S_el, почему тогда std::map не реализовать через hash-table?

1) Уже упоминавшаяся неупорядоченность ключей.
2) Хеш может работать быстрее мапы. А может и не работать (хотя, адепты хеша скажут что вероятность этого крайне мала). Мап же дает гарантии логарифмического времени вставки и поиска.

0

Сообщение от ReYalp IGPIGP, где можно почитать о хеш-таблицах(только о них)?У меня только поверхностные знания о них есть.

Вы будете смеяться, но впервые мне пришлось прочесть более менее понятный текст в сборнике C/C++ Архив программ. Арт Фридман, Ларс Кландер, Марк Михаэлис, Херб Шильдт. М.; "ЗАО "Издательство Бином"" 2001. Глава 4 Смешанные таблицы и разреженные массивы. Там кстати, я впервые узнал что хешировать это значит подмешивать/смешивать. Размазывать в общем. Герб Шилдт (так мне больше нравится) неплохой автор, что бы о нём ни говорили. Но это дело вкуса и предпочтения. Посмотрите также и Сортировка, Двоичные деревья и пр.

1

Сообщение от ReYalp , почему тогда std::map не реализовать через hash-table?

Потому что они имеют абсолютно разные алгоритмы и как результат абсолютно разные свойства. Ассимтотика поиска ключа у хеша гораздо лучше чем у мапа - амортизированное O(1) против гарантированного Log(N).
Но при этом элементы мапа упорядочены - т.е. можно пройти от наибольшего к наименьшему, взять интервал от-до, выполнить поиск до частичного совпадения ключа (ну к примеру как в подсказках при вводе) и т.д.. А у хеша не упорядочены, соответсвенно все эти возможности возможность отсутсвуют.

1

Сообщение от IGPIGP Впринципе 2-дерево с повторами могло бы работать как карта с повторами, но время поиска не будет соответствовать хеш-таблице. Будет медленнее.

Про повторы зря написал. unordered и multy это ортогональные префиксы, но я иногда путаю (не в коде, а в речи)
ReYalp, есть "детская задачка" - подсчитать количества разных символов в заданном тексте. Одно из красивых решений - создать массив размером в количество разных символов (можно просто char_max). И изначально инициализировать нулями, предполагая что нет ни каких символов. Потом идём по тексту и каждый символ приводим к size_t (считая char беззнаковым) и полученное значение используем как значение индекса в массиве увеличивая значение по индексу на 1. Это похоже на хеширование (вернее это оно и есть) при хеше типа
Это если есть преобразование. Если нет то можно пнуть вплоть до reinterpret_cast<int> иной раз. Но такие простые хеши - редкость. Хотя в некоторых алгоритмах могут очень пригодиться.

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

0

IGPIGP, а как работают хеш функции в хеш таблицах? Она же должна как-то +- выравнивать хеш под количество места в выделенном куске памяти? И еще мне не совсем понятно почему хеш таблица? Если использовать списки в хеш таблице то время поиска в худшем случае может быть O(n) , функция вставки в худшем случае тоже О(n)(если массив меньше чем хеш)

0

Сообщение от ReYalp IGPIGP, а как работают хеш функции в хеш таблицах? Она же должна как-то +- выравнивать хеш под количество места в выделенном куске памяти? И еще мне не совсем понятно почему хеш таблица? Если использовать списки в хеш таблице то время поиска в худшем случае может быть O(n) , функция вставки в худшем случае тоже О(n)(если массив меньше чем хеш)

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

Добавлено через 52 секунды
Естественно, будут возникать коллизии - разные ключи будут указывать на одну ячейку

Добавлено через 1 минуту
Когда количество этих коллизий превысить какую-то величину - просто увеличиваем размер массива и пересчитываем индексы для каждого ключа

Добавлено через 1 минуту
Если используется хорошая хэш-функция, то количество коллизий в этом случае уменьшается и время поиска ключа приближается к O(1)

0

Сообщение от ReYalp IGPIGP, а как работают хеш функции в хеш таблицах? Она же должна как-то +- выравнивать хеш под количество места в выделенном куске памяти?

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

Сообщение от ReYalp Если использовать списки в хеш таблице то время поиска в худшем случае может быть O(n) , функция вставки в худшем случае тоже О(n)(если массив меньше чем хеш)

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

0

oleg-m1973,

Сообщение от oleg-m1973 Естественно, будут возникать коллизии - разные ключи будут указывать на одну ячейку

А что происходит когда я хочу получить значение по ключу?Как определяется какое значение какому ключу принадлежит?

0

Сообщение от ReYalp А что происходит когда я хочу получить значение по ключу?Как определяется какое значение какому ключу принадлежит?

Хеш считается и в массив смотрется по индексу. ReYalp, в вас чувствуется сильное желание получить знания с чьей-то лопаты непосредственно в голову. Так не пойдёт. Читайте, а направление можно получить тут.

1

IGPIGP, As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.
линейная хеш таблица, если хеш нового ключа уже есть ищем свободную ячейку, но при следующем использовании этого ключа откуда мне знать что данные лежат именно в той ячейке(кторую я раньше нашел как свободную)

0

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

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

1

Сообщение от ReYalp А что происходит когда я хочу получить значение по ключу?Как определяется какое значение какому ключу принадлежит?

Исходное значение ключа тоже хранится. Бежим по цепочке коллизий и ищем нужный ключ.

1

Сообщение от ReYalp Она же должна как-то +- выравнивать хеш под количество места в выделенном куске памяти?

В большинстве случаев используют кусок размером степень двойки. так удобнее. При этом обычный хеш с открытой адресацией юзает обыяно коэффициент заполнения 75%. Потом расширяется. Хотя опять же степень двойки - это просто для ускорения. Может любой размер юзать. Просто значение хеша берется как остаток от деления значения хеш функции на юзаемый размер. Со степенями дваойки просто нахождение этого остатка гораздо быстрее - вырезаются n младших бит.
Кукушкин хеш к примеру юзает не менее двух таблиц и коэффициен заполнения там около 50% - он расширяется при неразрешимой коллизии. Но зато у него поиск гарантированное O(1) а вставка аммортизированное O(1). Добавлением третьей хеш функции можно коэффициент заполнения повысить до примерно 80%.

0

Сообщение от ReYalp почему тогда std::map не реализовать через hash-table?

У каждого способа свои достоинства и недостатки потому что.

0