Почему java.util.HashMap использовать связанный список внутри

Question

Моего концептуальное понимания java.util.HashMap выглядит следующим образом:

1. Ее основной актив по сравнению с другими реализациями Карты является постоянным время поиска, предполагая, что не являются столкновениями. По этой причине базовая реализация использует массив фиксированной длины - единственную структуру данных в информатике, которая имеет O (1) поиск.

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

3. Когда значение помещается в карту, пара значений ключа помещается во внутреннюю связанную реализацию списка для данного ключа. Когда есть столкновение, последующие пары значений ключа добавляются к списку.

4. При получении с карты hashCode() ключа используется для получения индекса массива реализации внутреннего связанного списка, и вы либо имеете свое значение, если список имеет размер 1, либо вы перебираете по списку вызывая equals() по ключу каждого элемента, пока не найдете свои значения.

Основанный на точке 2, HashMap должен расширять массив, операция, которая, несомненно, линейна. Почему он использует реализацию внутреннего связанного списка (O (n) поиск) для разрешения конфликтов? Почему он не использует структуру данных с поиском O (log n), как двоичное или красное черное дерево, для повышения производительности?

Answer 1

http://openjdk.java.net/jeps/180

На Java 8, HashMap делает откат к бинарному дереву, если имеется достаточное количество столкновений.

Answer 2

Хотя он не гарантирует O (1) время вставки, оно имеет амортизировано O (1) время вставки, то есть если вы вставляете большое количество элементов по одному, общее время чтобы их вставить, будет пропорционально количеству вставленных вами элементов.

Это не улучшит это, чтобы изменить структуру данных, используемую для ковшей. Точка расширения массива должна гарантировать, что ожидаемое количество записей в каждом ковше равно константа; это означает, что есть еще постоянная вставка и поиск, даже со связанным списком.

Числа очень тщательно разработаны, с точки зрения расширения и расширения (удвоение размера массива). Это очень похожая техника, используемая в ArrayList, чтобы гарантировать добавление амортизации O (1) в список.