CC
И в поиске. Но быстрее в среднем не значит, что быстрее всегда
Хм... А как может O(n) быть быстрее O(log n)?
Size: a a a
2020 August 13
CC
Поиск же у него O(n)?
/¯
Быстре во вставке и удалении?
А в поиске?
А в поиске?
Погоди, ты сейчас list и unordered_map в одну кучу свалил
CC
Ну раз unordered
VK
Поиск же у него O(n)?
Смотря что понимать под поиском
CC
Смотря что понимать под поиском
У найти элемент с данным ключом
VK
По ключу (first) — O(1), по значению (second) — O(n)
/¯
Хм... А как может O(n) быть быстрее O(log n)?
Потому что там не O большое, а среднее
/¯
Худший случай у хешмапы хуже красно-чёрных деревьев
CC
По ключу (first) — O(1), по значению (second) — O(n)
А как это по ключу O(1)?
VK
А как это по ключу O(1)?
Берётся от ключа хеш, по кусочку этого хеша выбирается ячейка
CC
Худший случай у хешмапы хуже красно-чёрных деревьев
Красно-чёрных деревьев?
VK
У разных ключей хорошая хеш-функция будет достаточно разные хеши выдавать, чтобы не свалить всё в одну кучу
/¯
Красно-чёрных деревьев?
Да, красно-чёрных деревьев
CC
Берётся от ключа хеш, по кусочку этого хеша выбирается ячейка
Аааа
Так это ж сколько памяти зря тратится для хранения?
Так это ж сколько памяти зря тратится для хранения?
/¯
Аааа
Так это ж сколько памяти зря тратится для хранения?
Так это ж сколько памяти зря тратится для хранения?
Что значит зря?)
VK
Аааа
Так это ж сколько памяти зря тратится для хранения?
Так это ж сколько памяти зря тратится для хранения?
Примерно того же порядка, что и количество элементов
AB
Хм... А как может O(n) быть быстрее O(log n)?
Может быть быстрее для конкретного N
CC
Что значит зря?)
Ну значит, что память выделена, а в ней пусто (или мусор)
VK
Ну и потом в ячейке (bucket) если оказалось несколько элементов с одинаковым хешем, то уже строго через == линейно выбирается из них искомый элемент