Как выглядит Bucket при ключах с одинаковым hashCode в HashMap
Предположим, у нас есть несколько ключей с одинаковым hashCode, например, key1, key2 и key3. В этом случае, все ключи будут храниться в виде связного списка в одном ведре.
HashMap Bucket:
+-------------------------------------------------+
| Bucket [hashCode=42] |
| |
| +-------------------+ |
| | Entry | |
| | key1 -> Value1 | |
| +-------------------+ |
| | |
| v |
| +-------------------+ |
| | Entry | |
| | key2 -> Value2 | |
| +-------------------+ |
| | |
| v |
| +-------------------+ |
| | Entry | |
| | key3 -> Value3 | |
| +-------------------+ |
+-------------------------------------------------+
Связный список: Каждый элемент в ведре представляет собой узел (Entry) связного списка, содержащий ключ, значение и ссылку на следующий элемент.
HashMap Bucket:
+-------------------------------------------------+
| Bucket [hashCode=42] |
| |
| +------------------------+ |
| | TreeNode | |
| | | |
| | key2 -> Value2 | |
| | / \ |
| | key1 -> Value1 key3 -> Value3 |
| +------------------------+ |
+-------------------------------------------------+
Если ведро превращается в сбалансированное дерево, элементы организуются в структуру дерева, что позволяет выполнять операции поиска, вставки и удаления быстрее по сравнению со списком.