Gabenskiy Jan 19 at 20:10

HashMap под микроскопом

Easy

6 min

10K

Java*

Comments 22

LeshaRB Jan 19 at 21:03

Мне в свое время зашли такие статьи
https://habr.com/ru/articles/128017/

У автора ещё немного есть

Gabenskiy Jan 20 at 00:10

Согласен, для своего времени статья замечательная

dph Jan 20 at 02:56

А чем она хуже этой статьи?

dersoverflow Jan 19 at 21:34

а бывает HashMap с транзакциями. но на Жабе у вас не получится.

https://ders.by/cpp/memdb/memdb.html

Politura Jan 20 at 06:49

В Джаве для этого есть ConcurrentHashMap из коробки, и никакие велосипеды изобретать не надо.

dersoverflow Jan 20 at 14:18

смиялсо.

ну покажите мне еще один "велосипед", где копирование объекта HashMap со всеми ее элементами - это просто memcpy()? джависты даже не поймут суть вопроса.

avost Jan 20 at 01:26

Шо, опять?!?

Удивительно, что вы не написали стандартную в таких случаях фразу, - я не нашёл на хабре ничего про устройство хэшмапы... Просто интересно, что могло побудить вас написать ещё одну однотипную статью к доброму десятку уже имеющихся?

Gabenskiy Jan 20 at 19:37

А какие темы были бы вам интересны?

dph Jan 20 at 02:54

А когда это получение значения из hashmap имеет сложность o(n)?
Или что значит фраза " Вставка и получение элементов имеют имеют сложность O(1) или О(n), или O(logN)"?

kulity Jan 20 at 03:17

Если у добавленных значений совпадает хэш, они попадут в один бакет в формате связного списка. Работа со списком как раз и даёт O(N). Но, при достижении определенного размера, список будет преобразован в дерево, где сложность уже O(logN), в целях оптимизации.

Такая ситуация возможна, если функция хэширования реализована плохо и, как следствие, имеет много коллизий

dph Jan 20 at 03:24

Это не совсем верное утверждение. Список в бакете не превышает 8 элементов, так что O(N) получить никак не получится.

rexer Jan 20 at 16:57

Все так, если количество элементов в бакете превышает TREEIFY_THRESHOLD (который как раз и равен 8), то будет вызван метод treeifyBin и бакет преобразуется в красно-черное дерево.

Благодаря этому, начиная с Java 8+ производительность java.util.HashMap в худшем случае не O(n), а O(log n).

dph Jan 20 at 17:19

Я, скорее, хотел показать, что автор статьей не совсем понял тот код, который комментирует. Иначе не сказал бы про O(n) для HashMap.
Впрочем, статья изначально бесполезная.

kulity Jan 20 at 03:07

В случае отсутствия ключа в мапе возвращается null, поэтому стоит предварительно проверять наличие пары через containsKey(Object key), иначе можем получить NullPointerException в дальнейшем.

Вредительский совет. Зачем для получения значения 2 раза осуществлять его поиск? Просто результат получения значения на null проверять и всё

PrinceKorwin Jan 20 at 08:37

Более того. В многопотоке (если кто-то накосячил), то можно от if xxx.containsKey() получить истину, а далее получить null при вычитывании сущности.

jbourne Jan 20 at 10:46

Добавлю, что в ConcurrentHashMap null ложить нельзя. Но проблема может возникнуть в синхронайзед оббертках типа Collections.synchronizedMap().

jbourne Jan 20 at 10:51

Согласен. Лишнего вызова стоит избегать всегда по дефолту.

В целом проблему с null можно решить так:
- не ложить null
- ложить "специальное" пустое значение
- проверять через .containsXXX()
- перестроить логику, что бы было не важно "нет или null"

jbourne Jan 20 at 11:02

Хорошо. + я бы добавил сюда еще инфу по памяти потребляемой. Ведь это всегда конфликт - память/скорость.

Грубо говоря например, тюнингом я могу больше приблизить скорость к О(1), если буду увеличивать число бакетов (уменьшая лоад фактор и число потенциальных коллизий для "нехорошего" хеша). Но тогда взлетит память. И в том "на сколько", и будет заключаться дилемма, которую нужно будет решать оптимизатору.

Поэтому я бы не разделял скорость и память.

rexer Jan 20 at 17:02

Вы не упомянули важную вещь, а именно - это то, как список будет преобразовываться в дерево (и в какое дерево именно), а также вклад в таком случае Comparable.
Вот тут я разбирал как это будет происходить: JBook/HashMap#коллизии

Ну и вообще, сама заметка про HashMap, может будет кому полезно: JBook

Antiever Jan 22 at 02:26

Подскажите как|чем в таком интересном виде "доки" в коде выводить?

rexer Jan 22 at 13:42

В новых версиях intellij idea это по умолчанию так, скриншот скорее всего оттуда.

Gabenskiy Jan 22 at 14:27

Inteleji Idea автоматически так отображает текст, обрамленный комментариями:

/**
*
*/