Мы все знаем о прекрасных внутренностях HashMap в Java 8, но его значение по умолчанию в виде дерева заставляет меня задуматься.
LinkedList предпочтительнее, чем массив для корзины, так как массиву нужен заранее определенный размер и вероятностьстолкновений очень мало.Амортизированная вставка не становится O (1) до тех пор, пока не будут изменены первые несколько размеров, поэтому LinkedList имеет смысл для низких значений N в этом случае.
Однако, почему структура данных корзины изменилась на Красно-черныйдерево после 8 объектов были добавлены?Это потому, что именно в этот момент время поиска O (logn) становится быстрее, чем O (n) для Java HashMap?
:: edit ::
Стивен С. определил, что существует компромисс между скоростью поиска и использованием пространства, и что TreeNode занимает вдвое больше пространства узла, согласно javadoc.
Исходя из этого, мой вопрос:затраты на использование пространства становятся менее важными, чем прирост скорости доступа O (logN) по сравнению с O (N) после добавления 8 объектов?Есть ли способ отобразить сложность времени и использование пространства для разных значений N, чтобы визуализировать этот компромисс?