Зачем нужны хэш контейнеры?

Привет всем) Собственно такой вопрос: зачем нужны хэш контейнеры? В чем разница между стандартными контейнерами STL? Эффективность и тд?
Никогда не пользовался ими в коде, поэтому прошу по-подробней)

0

Сообщение от Bretbas зачем нужны хэш контейнеры?

За горами, за лесами, За широкими морями, Не на небе -- на земле Жил старик в одном селе. У старинушки три сына: Старший умный был детина, Средний сын и так и сяк, Младший вовсе был дурак. (с) П. Ершов. Конек-Горбунок

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

0

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

1

Bretbas, я в хэше тополь, но попробую объяснить как понимаю, поэтому не серчайте:

Есть std::vector, доступ к элементу через индекс - это взяли начало и прибавили к нему индекс - всё просто. Адрес + число = адрес.
Если std::map доступ к нему по ключу, к примеру это структура Student ( std::string name, std::string surname, int age) - поиск по std::map это сравнение строк между собой - если имена одинаковые, сравниваем фамилии, если имя и фамилия одинаковые - сравниваем возраст. Сравнение строк это трудоемкий процесс - и как-то не очень получается.

Есть хэш-контейнеры, ты знаешь, что студентов может быть не больше 700 в университет к примеру, следовательно вставляя в контейнер студента при предоставляешь контейнеру число от 0 до 700. Который называется хэш.

Берём какуе-то логику: к примеру, длину имени и фамилии + его возраст.
Сама hash функция
Теперь у нас есть у каждого ключа число получено магическим способом. Запихиваем в хэш-контейнер по индексу 49 и 34 наших студентов. Но ведь могу быть несколько студентов с hash 34 ? Да, всё верно. По индексу 34 там наверно будет std::list. И что получается: Поиск студента теперь сводится к:
1) std::vector.begin() + 34
2) std::find list Student seach == iterator ( итераций G )

А без hash`a:
1) std::find map Student seach == iterator ( итераций log(N) )


Если мы распределим наших 100 студентов в хэш-контейнере так, чтобы у всех был свой hash номер ( уникальный ), то и std find list будет равен 1.

ИТОГО:
И получаем если храним в std map нужно log(N) сравнений объектов, где есть сравнение строк, что трудоёмкое.
А если в хэш-контейнере, смешение по hash-числу от начала за 1 скачёк, и если в std list 1 элемент , так же 1 скачёк.

Минусы?
1) Чтобы определить hash код нужно его вычислить при вставке и поиске.
2) Написать качественную hash функцию для своего типа с своими переменными надо иметь опыт и бошку

2

Сообщение от Bretbas разница между стандартными ассоциативным контейнерами и хэш-контейнерами в чем? Нужно ли их использовать в реальных проектах?

Как всегда, "дьявол в деталях" (c).

Реализация через дерево дозволяет сортировку и неограниченный рост, в обмен на относительно низкую (логарифмическую) скорость доступа. Реализация через хэш-таблицы не допускает ни того, ни другого, зато имеет предельную (практически, по индексу) скорость доступа. Реальные контейнеры, обычно, комбинируют то и другое (Ex: Hashed array tree).

Используются, почти, повсеместно - например, для построения Symbol tables в компиляторах.

2

Спасибо, примерно понял)

0

Bretbas, хеш таблицы используются в STL, в ассоциативных контейнерах с приставкой unordered.
Зачем они нужны? Иногда это ускоряет поиск по сравнению с упорядоченными контейнерами

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

Сообщение от rikimaru2013 C++ 1 2 3 4 size_t hash (const Student& current) { return current.name.size() + current.surname.size() + current.age; }

Тут можно немножко подкрутить, используя стандартные средства

2