Комментарии 43
В нормальных ассоциативных массивах используются хеш-таблицы, а не деревья.
Хорошо, изменю формулировку, если эта не нравится.
Хеш-таблицы работают быстрее деревьев, а потому для ассоциативных массивов предпочтительнее использовать именно их.
Скажем, если вам требуется держать много небольших ассоциативных массивов, то хэш-таблицы возможно не особо хороший вариант, т.к. потребляют относительно много памяти.
const int COUNT = 1000;
const int LENGTH = 100 * 1000;
const int QUERIES = 10;
string ss[COUNT];
for (int i = 0; i < COUNT; ++i) {
ss[i] = "";
for (int j = 0; j < LENGTH; ++j) {
ss[i] += (char)('a' + rand() % 10);
}
}
double start = clock();
unordered_map<string, char> um;
for (int q = 0; q < QUERIES; ++q) {
for (int i = 0; i < COUNT; ++i) {
um[ss[i]] = ss[i][0];
}
}
cout << (clock() - start) / CLOCKS_PER_SEC << endl;
start = clock();
map<string, char> m;
for (int q = 0; q < QUERIES; ++q) {
for (int i = 0; i < COUNT; ++i) {
m[ss[i]] = ss[i][0];
}
}
cout << (clock() - start) / CLOCKS_PER_SEC << endl;
На моей машине в зависимости от соотношения операций поиск/вставка (регулирующегося константой QUERIES в коде) std::map быстрее, чем std::unordered_map в 5-6 раз.
Собственно, думаю, понятно, почему именно в этом крайнем случае дерево работает быстрее, чем хеш-таблица.
А некоторые неосторожные хештаблицы умудряются сами себе устроить такой collision attack. Совсем недавно так облажались:
1. Swift
2. Rust
3. Delphi
Для защиты от такой атаки достаточно выбирать случайную хеш-функцию. Или можно использовать деревья уже внутри корзин хеш-таблицы, как делает стандартная библиотека Java
Проблему collision attack такой подход именно что решает.
Надеюсь у вас будет еще время сделать более подробную статью.
Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.
Т.е. самое важное, благодаря чему используется это дерево фактически везде в STL, не рассматривается?
Имхо, эту статью можно просто заменить ссылкой на википедию.
Отличное объяснение от автора красно-черных деревьев Р. Седжвика на портале Принстонского университета.
Для полноты статьи добавьте алгоритм удаления ячейки. Это самая захватывающая часть.
Ан нет…
Если поставить на паузу и идти по шагам, там будет коротки пояснительный текст.
ключи всех левых потомков <= k < ключи всех правых потомковРаспространённая ошибка. Рассмотрите дерево из миллиона одинаковых элементов и попытайтесь его сбалансировать. Хорошо получится?
Либо <= дважды, либо < дважды (а одинаковые элементы запрещены), пожалуйста.
Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.
А можно подтверждающую статистику? Ну, в STL map по умолчанию такой. В python, ruby, perl и lua по умолчанию hash map'ы. В java "по умолчанию" варианта нет, но присутствуют и hash map и tree map.
Только в тяжёлых бинах, большая же часть останется нормальной человеческой hash-таблицей с поиском/вставкой за O(1) с худшим вариантом на уровне O(log N).
И то, это детали имплементации, позволяющие иметь нормальную производительность при сильно неудачном сочетании данных и хэш-функции, когда много данных (или все) попадают в один бин.
Ведь там у кварков мало того, что цвет, так ещё и аромат есть. Откуда же у студентов с собой на лекции несколько флаконов духов возьмутся? Мы что, в парфюмерном магазине?
Если БЫ в алгоритме наравне с «красными/черными» вершинами присутствовали еще «белые» и «отмеченные крестиком» вершины, то ваша аналогия была бы уместана.
А так мы имееи ровно ДВА типа вершин, к которым применить краткую удобную систему условносных обозначений не составит труда.
Ни для записи, ни для понимания.
Красно-черные деревья: коротко и ясно