Улучшите время выполнения операций с хеш-таблицами, сохраняя списки в отсортированном порядке

Question

Ниже приведен вопрос из учебника Введение в алгоритмы , однако решение проблемы не дано ...

Профессор Марли выдвигает гипотезу о том, что он может получить существенный прирост производительности, изменив схему цепочки, чтобы сохранить каждый список в отсортированном порядке. Как модификация профессора влияет на время выполнения успешных поисков, неудачных поисков, вставок и удалений?

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

Однако для вставки это займет больше времени, поскольку нельзя просто вставить значение в начало списка, поскольку теперь порядок должен быть сохранен. Это больше не будет O (1) Я считаю.

Для удаления я понятия не имею.

На самом деле, я не совсем уверен, если какой-либо из моих ответов верен, может кто-нибудь, пожалуйста, помогите мне здесь?

Answer 1

Вы можете улучшить производительность, сортируя элементы в одном и том же слоте, но не в связанном списке.
Вместо этого, вероятно, используется сбалансированное дерево (и чаще всего это red-black tree) .

Но есть компромисс: только когда элементы в одном и том же слоте превышают определенное количество, это фактически улучшит производительность.

---

Пример - Java HashMap

В Java 8 HashMap переписан для использования linked list и red-black tree для представления элементов в слоте.

Существуют операции treeify() и untreeify() для преобразования между двумя структурами, запускаемые по заранее заданным порогам.