data-structures - 单独的链散列有序与无序
问题描述
您可以通过保持链表有序来改进单独的链散列吗？
它如何影响对数组的操作，时间复杂度（主要是插入、删除和搜索）？
起初我认为这可能是微不足道的，但我越想越想不明白你为什么不把它整理好？当然，插入和删除节点的少数操作比每次尝试查找某个值时都必须遍历整个列表所花费的时间要少得多？
我不是在寻找任何代码解决方案，只是在寻找概念背后的理解。出于某种原因，我找不到任何讨论这个问题的消息来源。
解决方案
起初我认为这可能是微不足道的，但我越想越想不明白你为什么不把它整理好？
我可以想到为什么哈希表链的元素没有排序的原因：
哈希表中的键并不总是像整数、浮点数、双精度或字符串这样的原始数据类型。它可以是任何东西 - 任何复杂的对象/类实例，它们不容易被排序。因此，在这种情况下，每次您都必须为作为键的对象实施比较策略（实现
<、=C++ 中的运算符、Comparable<T>Java 中的实现等）。另一个原因是哈希表中的链基本上是双重链表。因此，例如，如果您想搜索链中的元素，则无法利用二分搜索在对数时间内进行搜索，因为在链表类型结构（查找中间）上应用二分搜索并不简单。
如果明智地选择散列表的负载因子，散列表的桶/链将不会太密集或太稀疏。在这种情况下，每条链都会有合理数量的条目，并且在链上运行线性搜索并确保摊销恒定时间复杂度将是可接受的快速。
编辑
如果假设密钥是整数，那么对链进行排序仍然没有好处。对于哈希表上的两个主要操作 - 插入和搜索，您仍然不能利用二进制搜索或对数计时，因为链不是数组或向量，它的双向链表。并且链表上的二进制搜索不是对数的（在链表中查找中间不是 O(1) 像数组）。