LINUX.ORG.RU

std::map


0

0

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

★★★★

Ответ на: комментарий от jtootf

так же интересует что представляет собой индекс базе данных по текстовому полю, по полю int ?

quest ★★★★ ()
Ответ на: комментарий от quest

> подозреваю что там черт ногу сломит в исходниках этих

Подозревать не твоя работа, а твоя работа уметь разбираться в чужих исходниках.

anonymous ()

std::map — это упорядоченное хранилище, так что никакими хешами там и близко не пахнет. На практике это обычно красно-черное деревце. http://www.sgi.com/tech/stl/Map.html

Map is a Sorted Associative Container that associates objects of type Key with objects of type Data. Map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have the same key.

Хэш-таблица — это tr1::unordered_map ну ли компилятороспецифичные hash_map.

linuxfan ()

std::map это красно-черное дерево. std::unordered_map это хеш, хеш функцию можно задавать руками.

Reset ★★★★★ ()
Ответ на: комментарий от linuxfan

>никакими хешами там и близко не пахнет. На практике это обычно красно-черное деревце

ага, а что-же как не хеш пихать в это дерево в случае если ключ текст?

quest ★★★★ ()
Ответ на: комментарий от anonymous

>Очевидно же что ты студент! И судя по всему еще и двоечник!
нет двойки это слишком круто для такого дурня как я!

quest ★★★★ ()
Ответ на: комментарий от quest

>ага, а что-же как не хеш пихать в это дерево в случае если ключ текст?

Даю два намека: 1) я сильно сомневаюсь, что существует хорошая хеш-функция, сохраняющее отношение порядка; 2) std::map (как и std::set) требует задания функции сравнения элементов и по умолчанию использует operator<.

Все еще сомневаешься, что в узлах RB-tree лежат значения? Тогда ответь на вопрос: на кой черт нужно хранить там хеши, когда сбалансированное дерево дает логарифмическую сложность поиска, а хеш-таблица в идеале что-то вроде O(1)? Это же как-то взаимоисключающе звучит.

linuxfan ()
Ответ на: комментарий от quest

ага, а что-же как не хеш пихать в это дерево в случае если ключ текст?

Тебеж сказали нет в std :: map никаких хеш-функций. Сортировка идет по ключу.

najar ()
Ответ на: комментарий от quest

> ага, а что-же как не хеш пихать в это дерево в случае если ключ текст?

Отсыпь. Зачем тебе хеш ? Для построения map тебе нужно лишь чтобы к типу ключа были применимы операторы типа <, а также должно выполняться условние (A<B)&(B<C)->(A<C);

runtime ★★★★ ()
Ответ на: комментарий от quest

>хотите сказать что сравнение идет по strcmp()

Естественно! Более того, даже в настоящей хеш-таблице хеш используется только для обращения к нужной ячейке, после чего происходит честное сравнение ключей.

linuxfan ()
Ответ на: комментарий от quest

>Но ведь сравнение чисел (хешей) будет быстрее чем strcmp() ?

Верное выражение: (AAAA < BBBB )&&(BBBB < CCCC)&&(AAAA<CCCC)

Теперь посчитаем хеши от строк стандартной утилитой:

[root@localhost ~]# echo -n AAAA | md5sum 
098890dde069e9abad63f19a0d9e1f32  -
[root@localhost ~]# echo -n BBBB | md5sum 
f50881ced34c7d9e6bce100bf33dec60  -
[root@localhost ~]# echo -n CCCC | md5sum 
b41c1949bef0cb7c83998d0a5d83bcc2  -

Получаем неверное выражение: (098890dde069e9abad63f19a0d9e1f32 < f50881ced34c7d9e6bce100bf33dec60 )&&(f50881ced34c7d9e6bce100bf33dec60 < b41c1949bef0cb7c83998d0a5d83bcc2)&&(098890dde069e9abad63f19a0d9e1f32<b41c1949bef0cb7c83998d0a5d83bcc2)

legolegs ★★★★★ ()
Ответ на: комментарий от legolegs

это в случае если длина строки ключа меньше длины строки хеша

quest ★★★★ ()
Ответ на: комментарий от legolegs

а ты про то что число хеша строки BBBB может быть больше числа хеша строки CCCC? ну и что? главное что однозначное преобразование строка->хеш строки

quest ★★★★ ()
Ответ на: комментарий от quest

>число хеша строки BBBB может быть больше числа хеша строки CCCC? ну и что?

А, хм. Действительно, такая реализация может работать. Но зачем? Во-первых, в качестве ключа у std::map что только не используют. Во-вторых, если програмёр считает, что на его задачах оверхед по памяти и процу компенсируется скоростью сравнения хеш-сумм, то он сам может вместо строки сделать ключом хеш какой захочет. Например, const char* - отличный хеш, гарантированно без коллизий :)

legolegs ★★★★★ ()
Ответ на: комментарий от legolegs

>Например, const char* - отличный хеш вообщем да)

quest ★★★★ ()

вот кстати strcmp из glibc-2.7

int
strcmp (p1, p2)
     const char *p1;
     const char *p2;
{
  register const unsigned char *s1 = (const unsigned char *) p1;
  register const unsigned char *s2 = (const unsigned char *) p2;
  unsigned reg_char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
          return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}

quest ★★★★ ()
Ответ на: комментарий от quest

БД лежат на диске, на диске проще использовать хеширование и двоичный поиск. Построение дерева а диске не очень удобно.

legolegs ★★★★★ ()
Ответ на: комментарий от quest

> Но ведь сравнение чисел (хешей) будет быстрее чем strcmp() ?

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

runtime ★★★★ ()
Ответ на: комментарий от legolegs

> Верное выражение: (AAAA < BBBB )&&(BBBB < CCCC)&&(AAAA<CCCC)

Нет, в данном случае надо сравнивать хеши, для них по понятным причинам всё ок:

(098890 < f50881) & (f50881 < b41c19) -> (098890 < b41c19)

runtime ★★★★ ()
Ответ на: комментарий от quest

> Но ведь сравнение чисел (хешей) будет быстрее чем strcmp() ?

Совсем не обязательно. При сравнении хэшей надо прочитать исходную строку + посчитать хэш + сравнить хэши. При strcmp для несовпадающих ключей надо будет прочитать по несколько байт от обеих строк, что гораздо быстрее.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

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

Reset ★★★★★ ()
Ответ на: комментарий от Reset

> Если коллизий нет или их мало, то хеш таблица всегда будет быстрее дерева.

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

kemm ()
Ответ на: комментарий от slovazap

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

quest ★★★★ ()
Ответ на: комментарий от Reset

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

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

quest ★★★★ ()
Ответ на: комментарий от quest

Индекс. Обычно считают 32х битный хеш, а потом берут его по модулю. Если подобрать хороший хеш, то коллизий получается не так много на самом деле. Можешь сам сравнить производительность std::map и std::unordered_map на строках и убедиться в этом.

Reset ★★★★★ ()
Ответ на: комментарий от Reset

>Обычно считают 32х битный хеш, а потом берут его по модулю.
Что значит берут хеш по модулю?
Что делать если есть коллизии? Использовать хеш как индекс, выбирать указатель на список возможных вариантов ключа и в них уже разбираться?

quest ★★★★ ()
Ответ на: комментарий от quest

Что значит берут хеш по модулю?

Остаток от деления на размер таблицы

Что делать если есть коллизии? Использовать хеш как индекс, выбирать указатель на список возможных вариантов ключа и в них уже разбираться?

Есть по крайней мере два популярных способа. Один из них это действительно хранить в каждой ячейке указатель на список.

Reset ★★★★★ ()
Ответ на: комментарий от Reset

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

quest ★★★★ ()
Ответ на: комментарий от quest

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

Reset ★★★★★ ()
Ответ на: комментарий от quest

> ну и что? главное что однозначное преобразование строка->хеш строки

Жесть...

LamerOk ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.