Почему? ... Недочет только в том, что на хранение этого дерева на больших строках уйдет много памяти.

Вот поэтому. А накладные расходы сильно зависят, в том числе, и от используемого алфавита. И насчет сложность O(len(word)) ты как следует приврал. Почему-то ты считаешь, что выбор нужного узла, соответствующего заданной букве, осуществляется за константное время. Это так только в том случае, если ты используешь индексацию по символам алфавита, что дает гигантский оверхед по памяти.

Во-первых, n_k << N — это твоя нездоровая фантазия.

n_k - число хэш значений, N - число элементов в таблице. Если НЕ выполняется n_k<<N то бинарный поиск в букете вообще бессмысленное действо. Если выполняется, и таблица хорошо сбалансирована - то тем более бессмысленное, потому что эффективный бинарный поиск в букете это готовое дерево, и нафига тогда тут хэш таблица?

И как тут ведется первичный поиск?

O(logN) в худшем случае для вставки, удаления, поиска элемента

Забыл добавить, что «в худшем» совпадает со «в среднем».

а также поиск следующего и предыдущего

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

В дереве нет свободных ячеек

Уж что-что, а накладные расходы на поддержание древовидной структуры очень некислые: 3 * sizeof(pointer_type), что обычно выливается в 24 байта в современном 64-битном мире. Это эквивалентно 12-символьному русскому слову в utf-8.

Данные, лежащие в бинарном дереве, отсортированы.

А толку-то? Все равно последовательного (с точки зрения адресации памяти) доступа к ним нет.

чесно говоря фиг знает - такая вот библиотеке для С в одном .h файле
http://uthash.sourceforge.net/

Да я видел... ну опять таки, какой размер хэша (сколько допустимо значений)? Если MAX_INT... значит опять бинарный поиск (по тесту похоже).

n_k - число хэш значений

Число допустимых значений хэш-функции? Тогда у тебя «меньше» с «больше» перепутано. Или имеется в виду «количество различных значений хэш-функции, попадающих в одну ячейку хэш-таблицы»?

Если выполняется, и таблица хорошо сбалансирована

Понятие «сбалансированности» к хэш-таблице неприменимо.

И опять таки, malloc(sizeof(elem))... и в чем профит? Та же динамическая структура в памяти висит.

Число допустимых значений хэш-функции?

да. И нет, не перепутано. В среднем, по одному хэш значению N/n_k элементов. Под «сбалансированностью» я имел ввиду такую хэш ф-ю, которая равномерно распределяет элементы по хэшам ключей.

а твоя не делает элемент разве ?

Делает видимо... ну так и выходит то на то, просто вместо less от ключей less от хэшей? Хотя для интов можно че та более эффективное сделать, наверное это в unordered_map и сделано, не зря же она на порядок шустрее.

надо было сказать TRIE :)

чо уж мелочиться, поехали - hash array trie

ps на самом деле зависит от задачи, у trie свои недостатки

Но и профиты от дерева очевидны.

ну тут как раз у хеша свои преимущества, у дерева свои - в хеше удобнее lookup делать, в дереве search

За то время, по дереву будем идти можно из хэша несколько ключей достать.

ну-ну, посмотрим как ты сделаешь аналог перебора всех веток поддерева с использованием хеша и с какой скоростью это всё у тебя будет работать :)

в файловых системах и СУБД применяют B-деревья, которые являются дальнейшим развитием идеи бинарных деревьев поиска

не развитием, а частным случаем

а вовсе не потому, что по деревьям поиск быстрее.

поиск (понимаем здесь процесс перебора ключей по заданному критерию) по дереву быстрее

не быстрее - перебор это неправильное слово

если память нежалко, можно пробовать trie http://en.wikipedia.org/wiki/Trie

B-деревья, которые являются дальнейшим развитием идеи бинарных деревьев поиска

не развитием, а частным случаем

Именно развитием (B-деревья появились позже), и, поскольку двоичные деревья могут быть получены из B-деревьев, именно двоичные являются частным случаем B :)

Анонимус-то прав :)

#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>

using namespace std;

int main() {
        unordered_map<long,int> table;
        for(int i=0; i<1e7; i++ ) table[random()] = table.size();
        printf("%i\n", table.size() );
        return 0;
}

$ g++ -O3 map_test.cpp && time ./a.out
9976930

real    0m13.342s
user    0m12.833s
sys     0m0.351s
$ g++ -O3 -std=c++0x unordered_map_test.cpp && time ./a.out
9976930

real    0m6.135s
user    0m5.832s
sys     0m0.235s

http://developer.gnome.org/glib/2.30/glib-data-types.html
иль кучку всякого из глиба
ну тут нужен сам глиб

В чем прав? Ваш тест показывает, что время набивки unordered_map вдвое меньше, чем map. Так мы во первых про поиск, во вторых ничего, что в unordered_map первичный поиск по хэшу идет половинным делением?;-)

Таки развитием.

В общем вот http://a-iv.ru/trash/map-vs-hash.png

Во первых, поведение map и hash (которая unordered_map) совпадают с точностью до множителя, hash на порядок быстрее - лучше реализован бинарный поиск, поскольку заранее известно что ключ uint64_t.

Во вторых, если ограничивать число хэш-значений чиселкой H (кривые вида hash=H) то за счет коллизий сложность алгоритма меняется с O(log(N)) на O(N), как и положено по теории, и ес-но при больших N хэш мапу сливает, ну и чем шире хэш тем быстрее поиск.

В третьих, все кривые делают скачОк при N~10^6. Смотрим:

aiv@node-01:~> less /proc/cpuinfo
...
model name      : Intel(R) Core(TM)2 Quad  CPU   Q9450  @ 2.66GHz
...
cache size      : 6144 KB

ЗЫ точнее скачок начинается при N~2e5, кэш 6МБ, т.е. 32 байта на ячейку, а в ячейке должно быть long key, int value, long hash + указатель (28 байт в сумме), ну и выравнивание ес-но... картинку можно вставлять в учебник;-)

кстати - мерить надо не в тактах - а скорее в колличествах доступа к памяти
один доступ к памяти это 50ns например

алгоритмической сложности то нету - расчитывать особо нечего - одно только общение с памятью

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

алгоритмической сложности то нету - расчитывать особо нечего - одно только общение с памятью

В смысле О_О? Про общение с памятью можно мне не рассказывать - мы как раз занимаемся алгоритмами для числодробилок, оптимальных с т.з. общения с памятью;-)

А зачем мне _перебирать_ ветки? Хэш вообще-то для того, чтобы быстро искать.

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

Тогда как для хэша выбираем 1к начальных ключей, а на следующем уровне идут любимые бинарные деревья.

Сорри за К.О.

идут любимые бинарные деревья

Но куда лучше без них

нене - тут определенная подмена понятий

2ггрц и 4 ггрц интел - сидя на одной и тойже памяти - в случае больших массивах примерно одно и тоже время покажем - по транзакциям в секунду

а в тактах - будет странная картина - что более быстрый тормазнее более медленного

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

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

Так Кнута и не прочел? Балансировка как раз для таких задач и придумана, корень дерева будет в середине словаря, и пофик скока записей имеют совпадающее начало. А вот хэш таблица, с хэшем по первым буквам...

ну как - заюзал чегонить ? :)

не быстрее - перебор это неправильное слово

ну, тогда поясните суть слова «поиск» плиз

B-деревья, которые являются дальнейшим развитием идеи бинарных деревьев поиска

не развитием, а частным случаем

Именно развитием (B-деревья появились позже), и, поскольку двоичные деревья могут быть получены из B-деревьев, именно двоичные являются частным случаем B :)

с логической цепочкой и хронологией полностью согласен, но насчёт развития... можно, конечно, говорить, что бранч является развитием транка, но майнлайн от этого не стопается

Таки развитием.

я бы всё же это назвал веткой эволюции

А зачем мне _перебирать_ ветки? Хэш вообще-то для того, чтобы быстро искать.

ну и теперь, для полноты картины, поясни что есть поиск

Посмотрим, как ты бинарным поиском будешь искать по словарю, где 10^6 (любимое местное число) записей и 80% из них начинаются с одинаковой последовательности, допустим, 6 символов. Что там кто балансировать собрался?

а в чём проблема? и почему именно бинарный поиск?

перебор - это самый плохой вариант поиска
это когда тупо перебирают компоненты

а поиск - это хочу вот это -> так вот оно !
хеши и по комбинации параметров могут быть

а поиск - это хочу вот это -> так вот оно !

ок, вот пример - хочу достать все строки из словаря соответствующие шаблону «сам***н», как будем решать?

хочу достать [...] «сам***н», как будем решать?

Сначала достанем самогон, а потом будем решать :)

:)))

ноно
ты попробуй достань с шаблоном «*сам*»

этот пример кардинально не отличается от того примера, что я привёл

атличаеться

в твоей - будет выигрыш если отсортированы по возрастанию значения - хотябы по возрастанию букв
и выборка легче

в моей - сортировка по возрастанию непомогет

да суть не в этом, а суть в том что хэш на обоих задачах сольёт