Comments 40
А что будет если в такую хеш таблицу положить 3 значения с одним хешем (с колизией), а потом 2 первых удалить из хеш таблицы? Получится так что 3-й элемент окажется не на «своем» месте, а ячейка по этому хешу будет пустая. Какой алгоритм применяется чтобы не потерять 3-й элемент?
Да, вы верно заметили. Удаление в open addressing это не совсем тривиальная задача. Я бы мог рассказать, но не в контексте этой статьи. Даже Д.Кнут в 3 томе описал реализацию с ошибкой.
Основных вариантов 2:
Надгробные камни (tombstone) — это место помечается специальным значением "Здесь был элемент, но он умер. Сюда можно помещать новый элемент, но при поиске это место нужно рассматривать как занятое — нужно продолжать поиск дальше". Плюсы: возможна простая реализация, быстрое удаление. Минусы: при большом количестве удалений вся хэш таблица будет засорена надгробиями, что будет замедлять поиск. Для повышения эффективности можно время от времени (например, после определённого числа удалений) компактировать хэш-таблицу.
- При удалении перемещать какой-нибудь элемент в дырку. Тут все зависит от алгоритма, по которому выбирать перемещаемые элементы. Минусы: сложнее реализация, удаление может вызвать довольно длинную цепочку перемещений.
Ну в вообще, линейный пробинг это изначально не лучший вариант для многих типов нагрузок. (А тем более с load factor 75%, даже странно что такой стоит в Delphi по умолчанию). Есть более современные варианты, такие как cuckoo или RobinHood.
Linear это лучший вариант, но не 0.75, это правда. лучше 0.5-0.6 где-то. Все как попугаи копируют этот 0.75. Даже "свеженький" Swift: https://twitter.com/leventov/status/672640987102117888
А вот Rust использует RobinHood, да еще и с невероятным load factor 0.9. Так жить нельзя.
Ставится флаг, говорящий что ячейка пустая, но была заполнена ранее. При поиске значения эта ячейка не проверяется, но и не прерывает поиск.
Есть отдельные значения ячеек-признаки, которые указывают на то, пуста ли ячейка, или удалена, но за ней что-то есть.
Условно говоря, если мы видим в ячейке 0, значит, значения нет, а если -1 — делаем probe тем же методом в поисках значения.
О блин, пока набирал, уже ответили.
Условно говоря, если мы видим в ячейке 0, значит, значения нет, а если -1 — делаем probe тем же методом в поисках значения.
О блин, пока набирал, уже ответили.
Delphi. Будто на 10 лет назад вернулся. )
Не по теме:
Если не трудно, поменяйте, пожалуйста, «ложим» на «кладем».
Если не трудно, поменяйте, пожалуйста, «ложим» на «кладем».
Посоветуйте пожалуйста замену стандартному TDictionaty, если такая существует. Вообще, вроде было несколько проектов STL для Delphi, но что-то все как-то заглохли.
Мне всегда казалось, что при open addressing значение load factor должно быть не больше 0.33 или 0.5.
Если делать больше — слишком высока вероятность коллизии и, как следствие, низкая производительность.
Если делать больше — слишком высока вероятность коллизии и, как следствие, низкая производительность.
Ну вот как мы только что выяснили — да, должно быть не больше 0.5
Правильно ли я понял, что проблема у вас возникала, когда вы вторую хэш таблицу, идентичную первой, заполняли в порядке, как «расположились ключи» в первой таблице? Если да, то это достаточно экзотическая ситуация на мой взгляд.
Это просто способ смоделировать плотную набивку таблицы.
Это не экзотическая ситуация, т.к. такую последовательность нам возвращает итератор по хеш таблице. Например мы сохранили данные словаря в stream, и потом читаем. Вряд ли вы будете перемешивать элементы перед сохранением, ведь так?
Спасибо, я вас понял. Просто мне никогда не требовалось сохранять хеш-таблицу, чтобы потом на основе этих данных снова построить эту же таблицу. Обычно исходный набор данных сохранялся сам по себе (в своем порядке), а уже над этим набором строились хэш-таблицы, которые сами никуда не сохранялись и не служили «хранилищем данных», т.е. всегда были вторичными по отношению к структуре, хранящей сами данные.
Сохранение — это лишь как пример. Вот другой пример. У вас может быть 2 разные «подсистемы», в каждой из которых есть своя хеш таблица по одному и тому же ключу. И когда одна из подсистем захочет, например, синхронизироваться с другой — она возьмет итератор, и заполнит свою хеш таблицу. И будет ровно тот же эффект.
Вот здесь есть интересная статья про реализацию HashMap в Rust. Там, кстати, есть некоторое обоснование того, что открытая адресация (правильно сделанная) лучше цепочек.
Там кстати сравнивается самая простая реализация на цепочках. Но никто не мешает построить гибрид, в котором bucket list хранит значения <key, value, pointer to linked list>, и такая реализация будет в большинстве случаев вести себя как open addressing, но при этом недостатки открытой адресации (как например в статье) уйдут.
Хеш-мапы в Rust это горе от ума. Ну ладно, SipHash хотя бы уже выпилили, слава богу. Осталось сделать человеческий load factor и выкинуть robin hood.
Правильно ли я понял, что в Separate chaining массив bucket'ов может ссылаться на массив bucket'ов? После того как связанный список превзойдет load factor и вместо linked list будет создан новый массив бакетов. И таким образом получим древовидный многоуровневый хеш.
Или при Rehash меняется размер основного массива bucket'ов?
Или при Rehash меняется размер основного массива bucket'ов?
А можно к русскому языку прикопаться? В русской традиции программирования bucket-ы называются корзинами. (Кстати, вот она, разница между калькой и заимствованием: «корзина» — это калька, «хеш» — заимствование, «bucket» — копипаст, а склонять «bucket-ы» — вообще порнография!)
Почему «корзина» это калька? Bucket — ведро, basket — корзина.
Вот такая кривая калька :) Две буковки разницы. (Пепел на мою голову)
Ну, значит, вообще не калька, а самостоятельно возникший термин.
(А может, всё наоборот было? Дональд Кнут начитался Ершова в оригинале, сделал кальку «корзина» — «basket», а потом кто-то при перепечатках-цитированиях опечатался?)
Ну, значит, вообще не калька, а самостоятельно возникший термин.
(А может, всё наоборот было? Дональд Кнут начитался Ершова в оригинале, сделал кальку «корзина» — «basket», а потом кто-то при перепечатках-цитированиях опечатался?)
А можно к русскому языку прикопаться?… а склонять «bucket-ы» — вообще порнография!Конечно можно. Может быть кто-нибудь прочтет ваш комментарий, и возможно даже перестанет заниматься словесной порнографией.
Если предполагается копирование из одной коллекции в другую, то есть смысл выставить этой другой коллекции ожидаемую ёмкость.
В частности, у TDictionary есть конструктор Create(capacity: Integer).
Кстати, удивительно, что — в отличие от C++ных коллекций, нет возможности публично увеличить ёмкость.
Поэтому, если предполагается копировать далеко не всё подряд, то нужно сперва зарезервировать по максимуму, скопировать, а в конце пожадничать и усушить TrimExcess.
В частности, у TDictionary есть конструктор Create(capacity: Integer).
Кстати, удивительно, что — в отличие от C++ных коллекций, нет возможности публично увеличить ёмкость.
Поэтому, если предполагается копировать далеко не всё подряд, то нужно сперва зарезервировать по максимуму, скопировать, а в конце пожадничать и усушить TrimExcess.
Тут копирование только как пример. Существует множество случаев, когда вы не знаете размер заранее. Так же существует куча случаев когда нельзя заранее «пожадничать». Статья о том, что можно очень легко и неожиданно получить «неудачную» последовательность элементов, которая приведет к куче коллизий.
Внезапно: в Rust наступили ровно на те же грабли: http://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
for i in Hash1.Keys do // а этот — неожиданно медленнее, в десятки раз!
Hash2.Add(i, i);
Может стоит вместо вычисляемой функции «Hash1.Keys» 1'280'000 раз, присвоить ее временной переменной а потом уже использовать ее?
count := Hash1.Keys;
for i in count do
Hash2.Add(i, i);
В цикле for, значения «от» и «до» вычисляются только один раз, так что вы написали абсолютно эквивалентный код.
Никакой разницы, потому что в for i in Hash1.Keys do функция Hash1.Keys вызывается ровно один раз в которой создается итератор, и дальше работа идет только с этим итератором. Если бы оно вызывалось каждый раз — то каждый вызов создавался бы новый итератор, который указывал бы на начало списка, и ничего бы не работало.
А никто не смотрел, что на этот счёт делает Перл?
Sign up to leave a comment.
Delphi. Что таит в себе TDictionary