Я понимаю, что, начиная с Java 8, HashMap преобразует сегменты с высоким уровнем коллизий в красно-черные деревья для улучшения производительности в худшем случае от O(n) до O(log n).
Однако, когда я намеренно создаю коллизии хэшей (путем возврата постоянного значения в hashCode()), я по-прежнему наблюдаю производительность, которая масштабируется почти линейно по мере увеличения количества элементов.
Мой вопрос: какие внутренние условия или ограничения приводят к тому, что HashMap все равно ведет себя ближе к O(n) вместо O(log n) даже после древовидизации?
