std::map

а исходники твоей реализации STL посмотреть тебе религия запрещает?

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

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

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

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

Может я анестезиолог вам то откуда знать какая у меня работа?

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.

Очевидно же что ты студент! И судя по всему еще и двоечник!

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

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

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

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

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

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

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

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

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

хеш чтобы преодразовать как то текст в число... хотите сказать что сравнение идет по strcmp() ?

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

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

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

В конечном счёте да.

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

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

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

>В конечном счёте да.
В индексах бах данных по текстовому полю так же?

>В индексах бах данных по текстовому полю так же?

бах данных

std::map

Нет, не так же.

>Но ведь сравнение чисел (хешей) будет быстрее чем 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)

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

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

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

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

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

вот кстати 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;
}

>Нет, не так же.
можно подробней?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Может Кнута почитаешь?

давно хочу. ты имел ввиду что то другое? не индекс?

какой том?

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

3'й

>3'й
спасибо, куплю, почитаю

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

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

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

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

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

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

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

вообще говоря, существуют методы уменьшения коллизий, например,

http://en.wikipedia.org/wiki/Open_addressing

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

Жесть...