hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate
Здравствуйте, Alex Alexandrov, Вы писали:
AA>Здравствуйте, _DAle_, Вы писали:
_DA>>Здравствуйте, Alex Alexandrov, Вы писали:
AA>>>Здравствуйте, SkyDance, Вы писали:
SD>>>>Всегда интересовала область применения hash_map & hash_set для простых ключей с быстрой операцией сравнения (int, float и т.п.).
AA>>>Навскидку: B-деревья, которые в общем-то тоже являются отчасти хэш-таблицами, применяются для простых ключей сплошь и рядом. Таблица страниц в твоем процессоре, внутренние структуры данных в ОС на твоем компьютере, СУБД и многое другое.
_DA>>Немного не в тему, но хочется отметить, что B-деревья все же не имеют практически никакого отношения к hash_map, да и к хэш-таблицам в целом.
AA>М-м-м... Может быть, я подтормаживаю, но мне показалось, аналогия есть. Например, таблица страниц в x86. Берем старшие 10 бит — получаем индекс каталога страниц, берем следующие 10 бит — получаем индекс описателя страницы внутри каталога. Понятно, что не совсем то, но аналогия, ИМХО, есть — замена чистого поиска отображением на индекс. Хотя, чувствую, я не совсем прав, и это не совсем B-дерево. Так?
Это не совсем B-дерево. В двух словах на всякий случай напомню:
— В-дерево представляет собой древовидную структуру данных.
— Каждый узел дерева, не являющийся листом, имеет от a до b дочерних узлов.
— Структура хранит элементы упорядоченными, обеспечивает амортизированную логарифмическую сложность вставки и удаления элемента.
— Используется в основном в случаях, когда в памяти хранится только небольшая часть информации, и необходимо минимизировать количество обращений к внешнему носителю при поиске. Достигается это с помощью выбора достаточно больших констант, ограничивающих количество дочерних узлов, таким образом уменьшая глубину дерева (а следовательно и количество обращений к "диску").
А хэш-таблицы, например, в отличие от B-trees
-не являются древовидной структурой
-не хранят элементы упорядоченными
-сложность добавления/удаления/поиска в среднем константные
-использует хэш-функцию, удовлетворяющую определенным требованиям
Ну и в целом служат для других целей.
Здравствуйте, ssm, Вы писали:
ssm>hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate
Хм, вот оно как... Верно меня "Stores and retrieves data quickly from a collection in which each element is a pair that has a sort key whose value is unique and an associated data value." ввело в заблуждение...
Спасибо!
SD>Всегда интересовала область применения hash_map & hash_set для простых ключей с быстрой операцией сравнения (int, float и т.п.).
Лично я — для поиска по некотому признаку в больших объемах изменяющейся информации за константное время.
Здравствуйте, SkyDance, Вы писали:
SD>Всегда интересовала область применения hash_map & hash_set для простых ключей с быстрой операцией сравнения (int, float и т.п.).
Навскидку: B-деревья, которые в общем-то тоже являются отчасти хэш-таблицами, применяются для простых ключей сплошь и рядом. Таблица страниц в твоем процессоре, внутренние структуры данных в ОС на твоем компьютере, СУБД и многое другое.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
It's kind of fun to do the impossible (Walt Disney)
Здравствуйте, Alex Alexandrov, Вы писали:
AA>Здравствуйте, SkyDance, Вы писали:
SD>>Всегда интересовала область применения hash_map & hash_set для простых ключей с быстрой операцией сравнения (int, float и т.п.).
AA>Навскидку: B-деревья, которые в общем-то тоже являются отчасти хэш-таблицами, применяются для простых ключей сплошь и рядом. Таблица страниц в твоем процессоре, внутренние структуры данных в ОС на твоем компьютере, СУБД и многое другое.
Немного не в тему, но хочется отметить, что B-деревья все же не имеют практически никакого отношения к hash_map, да и к хэш-таблицам в целом.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, Alex Alexandrov, Вы писали:
AA>>Здравствуйте, SkyDance, Вы писали:
SD>>>Всегда интересовала область применения hash_map & hash_set для простых ключей с быстрой операцией сравнения (int, float и т.п.).
AA>>Навскидку: B-деревья, которые в общем-то тоже являются отчасти хэш-таблицами, применяются для простых ключей сплошь и рядом. Таблица страниц в твоем процессоре, внутренние структуры данных в ОС на твоем компьютере, СУБД и многое другое.
_DA>Немного не в тему, но хочется отметить, что B-деревья все же не имеют практически никакого отношения к hash_map, да и к хэш-таблицам в целом.
М-м-м... Может быть, я подтормаживаю, но мне показалось, аналогия есть. Например, таблица страниц в x86. Берем старшие 10 бит — получаем индекс каталога страниц, берем следующие 10 бит — получаем индекс описателя страницы внутри каталога. Понятно, что не совсем то, но аналогия, ИМХО, есть — замена чистого поиска отображением на индекс. Хотя, чувствую, я не совсем прав, и это не совсем B-дерево. Так?
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
It's kind of fun to do the impossible (Walt Disney)
"Alex Alexandrov" <20458@users.rsdn.ru> wrote in message news:1420613@news.rsdn.ru... > Навскидку: B-деревья, которые в общем-то тоже являются > отчасти хэш-таблицами
Эээ, с этим я не совсем согласен, это разные структуры данных.
Меня интересует область применения структур вроде hash_map<int, some_type>, hash_set<float, some_type>. На какой конкретной задаче вычисление хэша и поддержание bucket'ов при изменении таблицы будет дешевле, чем поиск в AVL / RB tree?
Здравствуйте, SkyDance, Вы писали:
SD>"Alex Alexandrov" <20458@users.rsdn.ru> wrote in message news:1420613@news.rsdn.ru... >> Навскидку: B-деревья, которые в общем-то тоже являются >> отчасти хэш-таблицами
SD>Эээ, с этим я не совсем согласен, это разные структуры данных. SD>Меня интересует область применения структур вроде hash_map<int, some_type>, hash_set<float, some_type>. На какой конкретной задаче вычисление хэша и поддержание bucket'ов при изменении таблицы будет дешевле, чем поиск в AVL / RB tree?
Если хэш-функция достаточно быстро вычисляется, то при больших объемах данных операции с hash_map будут производиться быстрее. А вообще надо рассматривать конкретный набор и частоту операций.
