|
63 | 63 | + [Каково максимальное число значений `hashCode()`?](#Каково-максимальное-число-значений-hashcode) |
64 | 64 | + [Какое худшее время работы метода get(key) для ключа, которого нет в `HashMap`?](#Какое-худшее-время-работы-метода-getkey-для-ключа-которого-нет-в-hashmap) |
65 | 65 | + [Какое худшее время работы метода get(key) для ключа, который есть в `HashMap`?](#Какое-худшее-время-работы-метода-getkey-для-ключа-который-есть-в-hashmap) |
| 66 | ++ [Почему несмотря на то, что ключ в `HashMap` не обязан реализовывать интерфейс `Comparable`, двусвязный список всегда удается преобразовать в красно-черное-дерево?](#Почему-несмотря-на-то-что-ключ-в-HashMap-не-обязан-реализовывать-интерфейс-Comparable-двусвязный-список-всегда-удается-преобразовать-в-красно-черное-дерево) |
66 | 67 | + [Сколько переходов происходит в момент вызова `HashMap.get(key)` по ключу, который есть в таблице?](#Сколько-переходов-происходит-в-момент-вызова-hashmapgetkey-по-ключу-который-есть-в-таблице) |
67 | 68 | + [Сколько создается новых объектов, когда вы добавляете новый элемент в `HashMap`?](#Сколько-создается-новых-объектов-когда-вы-добавляете-новый-элемент-в-hashmap) |
68 | 69 | + [Как и когда происходит увеличение количества корзин в `HashMap`?](#Как-и-когда-происходит-увеличение-количества-корзин-в-hashmap) |
@@ -832,6 +833,20 @@ ___O(N)___. Худший случай - это поиск ключа в `HashMap |
832 | 833 |
|
833 | 834 | [к оглавлению](#java-collections-framework) |
834 | 835 |
|
| 836 | +## Почему несмотря на то, что ключ в `HashMap` не обязан реализовывать интерфейс `Comparable`, двусвязный список всегда удается преобразовать в красно-черное дерево? |
| 837 | +Красно-черное дерево - это самобалансирующееся бинарное дерево поиска. Это означает, что для его построения нужно уметь сравнивать элементы между собой. |
| 838 | + |
| 839 | +В Java обычно сравнение объектов происходит с помощью метода `compareTo()`, который определен в интерфейсе `Comparable`. На первый взгляд кажется логичным, если бы после Java 8 у ключа в `HashMap` появилось дополнительное требование - реализовывать `Comparable`. |
| 840 | + |
| 841 | +Чтобы избежать этого, используется следующий алгоритм при сравнении ключей: |
| 842 | +1. Сначала делается попытка сравнить хэши ключей |
| 843 | +2. Если хэши равны и оба ключа реализуют `Comparable`, то для сравнения вызывается метод `compareTo()` |
| 844 | +3. Если ключи не реализуют `Comparable`, то сравнение происходит с помощью метода `tieBreakOrder()`, в котором |
| 845 | + + сначала будет совершена попытка сравнить ключи через названия их классов (`getClass().getName()`) |
| 846 | + + если ключи являются экземплярами одного класса, то сравниваться будут результаты метода `System.identityHashCode()` |
| 847 | + |
| 848 | +[к оглавлению](#java-collections-framework) |
| 849 | + |
835 | 850 | ## Сколько переходов происходит в момент вызова `HashMap.get(key)` по ключу, который есть в таблице? |
836 | 851 | + ключ равен `null`: __1__ - выполняется единственный метод `getForNullKey()`. |
837 | 852 | + любой ключ отличный от `null`: __4__ - вычисление хэш-кода ключа; определение номера корзины; поиск значения; возврат значения. |
|
0 commit comments