A
А с быстротой тут смотря что делать. Как я понимаю открытая индексация самая быстрая на выборку, но со вставкой и особенно удалением у нее есть проблемы
Size: a a a
2021 June 25
АО
Но правда это скорее про хеш было, чем про тип индексации.
A
Вообщем заинтриговали, надо детальнее посмотреть что там 🙂
АО
С удалением то почему?
АО
Там основная проблема была при ребалансе всего этого счастья.
АО
То есть нужно поддерживать определенный процентаж количества ключей и время от времени все приходится пересчитывать. В этот момент словарь конечно здорово тормозит.
АО
Там всё очень просто.
https://github.com/JuliaLang/julia/blob/master/base/dict.jl - вот исходник.
https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L78-L99 - это структура (там как раз видно
https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L372-L393 - функции, которые вставляют новый элемент, внутри они вызывают тот самый
https://github.com/JuliaLang/julia/blob/master/base/dict.jl - вот исходник.
https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L78-L99 - это структура (там как раз видно
keys и values заданные как вектора)https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L372-L393 - функции, которые вставляют новый элемент, внутри они вызывают тот самый
rehash.
АО
ht_keyindex2! - это та самая функция, которая считает хэш до тех пор пока не находит подходящую позицию.АО
Хаха, они красавцы.
https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L661-L667
При удалении, никакого пересчёта не производится.
https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L661-L667
При удалении, никакого пересчёта не производится.
АО
То есть если создать словарь размером в миллион ключей, а потом 99% удалить, то
getindex будет всё равно медленный.АО
С другой стороны, всегда можно руками
rehash вызвать.АО
Но да, это уже недокументированные возможности.
A
потому иначе это будет удаление из середины непрерывного массива
A
Мне интереснее - я пока не понял, как они так хитро помечают удаленные объекты что знают что они не просто пустые, а удаленные. Это вообщем одна из проблем такого подхода
АО
Там похоже сурово. Они NULL пишут.
A
т.е. там смысл в чем - мы когда ищем ключ мы сначала попадаем в какой-то элемент массива по хэш-индексу, если этот элемент не совпадает с ключом то идем последовательно с каким-то шагом пока не найдем совпадающий или пустой элемент. Нашли совпадающий - значит нашли. Нашли пустой - значит нет такого ключа в мапе
АО
Вообще это нечестно 😊
Простым смертным удалять элементы без изменения типа не разрешают 😊
Простым смертным удалять элементы без изменения типа не разрешают 😊
A
Соответвенно когда мы удаляем какой-то ключ, то нельзя его проставить в пустой потому что он тогда может порвать цепочку и все ключи с таким же хэшем которые в цепочке идут после него станут недоступны при выборке
A
а rehash скорее всего присходит когда кол-во ключей начинает превышать какую-то долю от выделенного под них массива (обычно 50%). В этом случае массив увеличивают в 2 раза и пересчитывают хэши