Comments 40
Основных вариантов 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 тем же методом в поисках значения.
О блин, пока набирал, уже ответили.
Если не трудно, поменяйте, пожалуйста, «ложим» на «кладем».
Если делать больше — слишком высока вероятность коллизии и, как следствие, низкая производительность.
При этом проблема, как мне кажется, исключительно в этом.
Вот здесь есть интересная статья про реализацию HashMap в Rust. Там, кстати, есть некоторое обоснование того, что открытая адресация (правильно сделанная) лучше цепочек.
Хеш-мапы в Rust это горе от ума. Ну ладно, SipHash хотя бы уже выпилили, слава богу. Осталось сделать человеческий load factor и выкинуть robin hood.
Или при Rehash меняется размер основного массива bucket'ов?
Ну, значит, вообще не калька, а самостоятельно возникший термин.
(А может, всё наоборот было? Дональд Кнут начитался Ершова в оригинале, сделал кальку «корзина» — «basket», а потом кто-то при перепечатках-цитированиях опечатался?)
А можно к русскому языку прикопаться?… а склонять «bucket-ы» — вообще порнография!Конечно можно. Может быть кто-нибудь прочтет ваш комментарий, и возможно даже перестанет заниматься словесной порнографией.
В частности, у TDictionary есть конструктор Create(capacity: Integer).
Кстати, удивительно, что — в отличие от C++ных коллекций, нет возможности публично увеличить ёмкость.
Поэтому, если предполагается копировать далеко не всё подряд, то нужно сперва зарезервировать по максимуму, скопировать, а в конце пожадничать и усушить TrimExcess.
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);
Delphi. Что таит в себе TDictionary