R
у иммутабельного хэшсета везде константы
Size: a a a
2020 December 13
λ
eC != C
R
и. или эта как раз та структура, которая при больше чем 5 элементах (иди другом кол-ве) меняет хэш на дерево?
R
eC != C
ну так и в классической хэштаблице не чистая константа))0))
R
eC != C
мы этот момент как-бы автоматически опускаем
Oℕ
RAFIZ
тут коллега выше кинул ссылку на стандартные документ (который я 100 раз видел, но почему-то в этот раз решил написать сюда) и вот что в нём нарисовано
λ
λ
eС в том случаем это O(log32(n))
Oℕ
ну т.е. это такая дурная практика, т.к. мы ограничены интами, давайте считать всё константой
Oℕ
а обычный хештейбл со связными списками в бакетах - линейным
R
некоторые вообще говорят, что он O(1), это спорный момент, просто там константный множитель 32 / 5 = log (bitlen(Int)) / log(329
да, всё. понял. спасибо
λ
а обычный хештейбл со связными списками в бакетах - линейным
до какого-то момента там связный список, а потом дерево
Oℕ
до какого-то момента там связный список, а потом дерево
не понял, там просто связный список, есть у тебя 2^32 * X элементов, поиск будет C * X сравнений делать, так что класс сложности O(1 + n/ 2^32) = O(n)
λ
не понял, там просто связный список, есть у тебя 2^32 * X элементов, поиск будет C * X сравнений делать, так что класс сложности O(1 + n/ 2^32) = O(n)
я про j.u.HashMap
Oℕ
я про j.u.HashMap
так и там то же самое
Oℕ
или не то же самое?
λ
в джава хэшмепе есть оптимизация, которая превращает бакет потом в дерево
Oℕ
в джава хэшмепе есть оптимизация, которая превращает бакет потом в дерево
что за дерево
λ
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
Oℕ
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
ну так сравнений всё равно линейное количество