SB
Size: a a a
2020 October 19
SB
Илья Билаш
Да, коллизия идёт по бакету, который вычисляется на основании hashcode, этот момент я тут упростил. Но суть остаётся - даже в случае одинаковых hashcode ничего страшного не произойдет - они определятся в один бакет и там уже разруливаем на основании equals.
И по бакету идёт не только коллизий, не путай сам себя.
ИБ
ИБ
А как дерево помогает? Дерево чего?
Вот че нагуглил
Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных "связанный список" и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).
Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).
Я в эти дебри уже не вникал
Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных "связанный список" и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).
Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).
Я в эти дебри уже не вникал
SB
Илья Билаш
Вот че нагуглил
Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных "связанный список" и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).
Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).
Я в эти дебри уже не вникал
Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных "связанный список" и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).
Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).
Я в эти дебри уже не вникал
Это к бакетам вообще никак.
ИБ
Помню, что переход на 8 Яву дал нам неплохой буст к производительности, и я тогда нашел это изменение в ченджлогах
SB
Илья Билаш
Помню, что переход на 8 Яву дал нам неплохой буст к производительности, и я тогда нашел это изменение в ченджлогах
А это как раз к тому, что @ogurchinskiy хештаблица из коробки работает далеко неидеально и заточена под среднее на рынке.
ИБ
Вот не готов сейчас даже сказать в какую сторону