通过按排序顺序保存列表来改进哈希表操作的运行时间
Improve the runtime of hashtable operations by keeping lists in sorted order
下面是课本算法导论的一道题，但是没有给出题解...
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
对于这个问题，我认为如果列表已排序，搜索的 运行 时间将是相同的，因为它们是链表，仍然需要遍历整个列表才能找到一个值.
然而，对于插入，它会花费更长的时间，因为不能只将一个值插入到列表的头部，因为现在必须保留顺序。我相信它不再是 O(1)。
删除我不知道。
事实上，我不太确定我的回答是否正确，有人可以帮我吗？
您可以通过对同一槽中的元素进行排序来提高性能，但不能使用链表。
相反，可能使用平衡树 （而且通常是 red-black tree）.
但是，有一个权衡，只有当同一个槽中的元素超过一定数量时，它才会真正提高性能。
示例 - Java 的 HashMap
在 Java 8 中，HashMap 被重写为同时使用 linked list 和 red-black tree 来表示槽中的元素。
有 treeify() 和 untreeify() 操作在 2 个结构之间转换，由预定义的阈值触发。
下面是课本算法导论的一道题，但是没有给出题解...
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
对于这个问题，我认为如果列表已排序，搜索的 运行 时间将是相同的，因为它们是链表，仍然需要遍历整个列表才能找到一个值.
然而，对于插入，它会花费更长的时间，因为不能只将一个值插入到列表的头部，因为现在必须保留顺序。我相信它不再是 O(1)。
删除我不知道。
事实上，我不太确定我的回答是否正确，有人可以帮我吗？
您可以通过对同一槽中的元素进行排序来提高性能，但不能使用链表。
相反，可能使用平衡树 （而且通常是 red-black tree）.
但是，有一个权衡，只有当同一个槽中的元素超过一定数量时，它才会真正提高性能。
示例 - Java 的 HashMap
在 Java 8 中，HashMap 被重写为同时使用 linked list 和 red-black tree 来表示槽中的元素。
有 treeify() 和 untreeify() 操作在 2 个结构之间转换，由预定义的阈值触发。