in the worst case your hash map will degenerate into a linked list and you will suffer an O(N) penalty for lookups, as well as inserts and deletions
Примечание: можно улучшить до O(log(n)), но надо, чтобы key тип имплементировал Comparable
There are some ways of mitigating the worst-case behavior, such as by using a self-balancing tree instead of a linked list for the bucket overflow - this reduces the worst-case behavior to O(logn)
in the worst case your hash map will degenerate into a linked list and you will suffer an O(N) penalty for lookups, as well as inserts and deletions
Примечание: можно улучшить до O(log(n)), но надо, чтобы key тип имплементировал Comparable
There are some ways of mitigating the worst-case behavior, such as by using a self-balancing tree instead of a linked list for the bucket overflow - this reduces the worst-case behavior to O(logn)
В чем ценность Хэшмэпа с одинаковыми хэшами? Если такое случается, то либо вы не правильно подобрали структуру данных для вашей задачи, либо ваш способ генерации ключей далёк от оптимального
valchkou wrote: 05 Feb 2022 21:19
... насколько я помню из дошкольного курса природоведения, arrayList.set(10, "here-here") создаст новый массив и скопирует в него старый.
Хотя в последних версиях возможно и это оптимизировано уровнем ниже так что попросту расширяется старый, а новый даже не создается.
...
Имхо, все-таки создается новый (расширить массив нельзя, fixed size) но с достаточным capacity "на вырост", чтобы хватило на добавление еще нескольких элементов.
Наверное если добавлять в ArrayList 1000000 элементов по одному, то внутри него придется создавать новый массив довольно часто, и это скажется на производительности. Не уверен, не пробовал.
Херовимчик wrote: 05 Feb 2022 21:39
В чем ценность Хэшмэпа с одинаковыми хэшами? Если такое случается, то либо вы не правильно подобрали структуру данных для вашей задачи, либо ваш способ генерации ключей далёк от оптимального
Разумеется никакого, вопрос был чисто теоретический относительно worst case scenario.
Херовимчик wrote: 05 Feb 2022 21:39
В чем ценность Хэшмэпа с одинаковыми хэшами? Если такое случается, то либо вы не правильно подобрали структуру данных для вашей задачи, либо ваш способ генерации ключей далёк от оптимального
Разумеется никакого, вопрос был чисто теоретический относительно worst case scenario.
Ну все же когда обсуждают эффективность (Big O notation) подразумевают либо теоретическое значение, либо оценка конкретной имплементации. В теории, доступ для хэшмэп О(1), на практике - нет предела криворукости
Херовимчик wrote: 05 Feb 2022 21:39
В чем ценность Хэшмэпа с одинаковыми хэшами? Если такое случается, то либо вы не правильно подобрали структуру данных для вашей задачи, либо ваш способ генерации ключей далёк от оптимального
Разумеется никакого, вопрос был чисто теоретический относительно worst case scenario.
Ну все же когда обсуждают эффективность (Big O notation) подразумевают либо теоретическое значение, либо оценка конкретной имплементации. В теории, доступ для хэшмэп О(1), на практике - нет предела криворукости
Теоретическое значение обычно подразделяют на несколько типов - Best, Average, Worst, см. например https://www.bigocheatsheet.com/
Херовимчик wrote: 05 Feb 2022 21:39
В чем ценность Хэшмэпа с одинаковыми хэшами? Если такое случается, то либо вы не правильно подобрали структуру данных для вашей задачи, либо ваш способ генерации ключей далёк от оптимального
Разумеется никакого, вопрос был чисто теоретический относительно worst case scenario.
Ну все же когда обсуждают эффективность (Big O notation) подразумевают либо теоретическое значение, либо оценка конкретной имплементации. В теории, доступ для хэшмэп О(1), на практике - нет предела криворукости
Теоретическое значение обычно подразделяют на несколько типов - Best, Average, Worst, см. например https://www.bigocheatsheet.com/
Безусловно даже в теории есть оценка для всех сценариев. Главное выяснить что от вас нужно конкретному интервьюеру
ну во, все хорошо. на самом деле интересен не какой то правильный ответ, а как человек начнет рассуждать и какие доводы приводить. при этом не так уж важно в какую сторону его занесет. хотя, если уж переходим на личности, конкретно Вам я б поставила жирный плюс, если б вы мне про concurrent map/set ответили, что вопрос смешной), он действительно несколько потешный.
Херовимчик wrote: 05 Feb 2022 22:00
...
В теории, доступ для хэшмэп О(1), на практике - нет предела криворукости
йеп.
на самом деле, если говорить не про беседы с недавними студентами, то все эти достаточно простые разговоры про базовые структуры и их конкретные имплементации дают прощупать почву сможем ли мы с этим человеком сработаться. насколько кандидат уперто гнет свою линию и сколько он прилагает усилий для того, чтоб вообще понять о чем разговор. ну и какие доводы он приводит чтоб, например, меня убедить в его точке зрения. потому что тех, кто 20 лет перекладывает поля из одного джавабина в другой отсеивают раньше, а если человек больше 10 лет в индустрии, то уж как то он поднатаскался худо бедно... но может случиться так, что мы с ним не сработаемся. или что он с нами не сработается. вот хочется сэкономить друг другу время и ресурсы.
Я иногда спрашиваю про epsilon GC. Я обьясняю что это тем кто не знает и спрашиваю зачем такое может быть нужно
JEP 318 explains that “[Epsilon] … handles memory allocation but does not implement any actual memory reclamation mechanism. Once the available Java heap is exhausted, the JVM will shut down.”
So, this explains why our application terminated with an OutOfMemoryError.
But, it raises the question: Why do we need to have a garbage collector, that doesn't collect any garbage?
in the worst case your hash map will degenerate into a linked list and you will suffer an O(N) penalty for lookups, as well as inserts and deletions
Примечание: можно улучшить до O(log(n)), но надо, чтобы key тип имплементировал Comparable
There are some ways of mitigating the worst-case behavior, such as by using a self-balancing tree instead of a linked list for the bucket overflow - this reduces the worst-case behavior to O(logn)
Коль уж тема про ДевОпсов, какие вообще от них ожидания? Скажем так, какой процент времени ДевОпсы тратят на написание кода и какого уровня задачи решают на повседневной основе?
Херовимчик wrote: 05 Feb 2022 23:51
Коль уж тема про ДевОпсов, какие вообще от них ожидания? Скажем так, какой процент времени ДевОпсы тратят на написание кода и какого уровня задачи решают на повседневной основе?
А у вас на фирме таковых вообще не имеется? Мне кажется надо понимать в рамках конкретной компании. У нас такие занимаются автоматизацией и управлением ci/cd pipeline. Плюс написание скриптов за наблюдением за серверами. Ну и наблюдение за разного рода серверами. Если что то летит, то перенаправлять трафик, поднимать. Выяснять причины и где возможно автоматизировать.
Очень странно звучит вопрос, менеджер хочет нанять ресурс. Но не знает, зачем такой ресурс нужен вообще. Ну или может я не слежу за ситуацией. И что то пропустил.
В моем (возможно неправильном) понимании девопсов они вообще код не пишут, в основном пишут всякие конфигурации на yaml и гоняют команды в linux терминале.
Вот, кстати, у этой женщины хорошие видео на тему инфраструктуры и пр., как раз свежее видео "What is DevOps? REALLY understand it | DevOps vs SRE" (надо бы и самому посмотреть)
