ПФ
Size: a a a
2021 May 14
ПФ
contains в сете работает через .get в мапе
ПФ
This class offers constant time performance for the basic operations (add, remove, contains and size),
ПФ
Прямо в документации
AN
Сравнить все равно нужно с каждым. Константа равна размеру. Не один же
AN
Мапа использует хэшкод, так что сравнение быстрое и теоретически хэшкод может быть упорядоченным. Но все равно какая-то модифицированная линейность по размеру
ПФ
Нет, тебе не надо сравнивать с каждым, тебе достаточно узнать что такого нет.
ПФ
Слушай, ну давай не будем. Если у меня объектов коллизия хэшкодов внезапно то да, будет медленно. Если же её нет - то работает примерно за единицу, но в плохих случаях можно быть за, например, О(4) или даже О(6), что в О-нотации всё равно О(1)
AN
Если хэш сортированный то вполне может быть.
ПФ
Это что такое сортированный хэш? И видел ли ты что хэшмэп ищет не по хэшу объекта как таковому?
AN
На изучение хэшмапа можно жизнь положить. Я представляю как хранение сделано. Но не особо глубоко. Я кстати тут напоролся на этом. В js перформанс мамы далеко не такой приятный
ПФ
Нет, если мы не говорим про Concurrent - то там всё сравнительно просто. Я разобрался сам по исходникам и документации после того как спросили первый раз на собесе.
ПФ
Так вот, чтобы у тебя поиск был долгим - надо специальные усилия применить или быть экстремально невезучим
ПФ
А в js ты прямо Мап смотрел или дикт?
AN
Kotlin hashmap
AN
Да, увидел уже, там доп индекс. Ну тогда понятно. Я про него не помнил
ПФ
А он во что превращается? Если очень захотеть - есть https://adrianmejia.com/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#DecentHashMap, например
AN
Без понятия. Надо в код слазить. Но там дорогой хэш и дорогой поиск
ПФ
В джаваскрипте есть нативный Set, под него можно подстроиться
ПФ
Это вот то, почему я считаю что нельзя программировать на котлине не зная низлежащего языка