无序词典：重散列与HashMap

"《无序词典-交互设计那些事儿》摘录，主要涉及数据结构中的无序词典，特别是其在映射结构中的应用，以及重散列方法的原理和时间复杂度分析。" 在计算机科学中，无序词典是一种数据结构，用于存储键值对，它不要求键的唯一性，类似于现实生活中多义词的处理。无序词典允许同一个键有多个值，这在某些场景下非常实用，比如在存储词汇的多种解释时。无序词典与映射结构的主要区别在于后者要求键的唯一性。 映射结构的一个典型实现是Java的`java.util.HashMap`类，它允许用户自定义装填因子上限，默认为0.75。当装填因子超过这个阈值时，`HashMap`会执行重散列（Rehashing），即将所有元素重新插入到新的、更大的桶数组中，以保持较低的冲突概率。重散列的基本策略是将桶数组的大小翻倍，这样可以确保平均每个桶中的元素数量减少，从而提高查找效率。尽管每次重散列操作本身的复杂度是O(N)，但通过容量翻倍，可以使得平均下来每次查找的复杂度保持在O(1)。 重散列过程中，选择桶数组容量通常要求为素数，因为素数可以更有效地避免哈希冲突。不过，判断一个大数是否为素数需要O(n)的时间复杂度，这可能成为性能瓶颈。为了优化，可以预先生成素数表或者使用更高效的素数检测算法，如米勒-拉宾素性检验。 无序词典的抽象数据类型（ADT）描述包括基本操作，如`getSize()`，它返回词典中元素的数量。这些操作为用户提供了一种与数据结构交互的接口，允许他们查询词典的规模，但不涉及具体的顺序或排序功能。无序词典与有序词典的主要区别在于，有序词典在条目间定义了全序关系，提供了如`first()`、`last()`、`prev()`和`succ()`等方法，而无序词典只提供平等比较。 无序词典的实现可以基于各种数据结构，如哈希表、开放寻址法或者链地址法等，每种实现都有其优点和缺点。在实际应用中，选择合适的实现方式取决于具体的需求，如查找效率、内存占用和动态扩展性等。 无序词典是数据结构中的一个重要组成部分，它在存储和管理非唯一键的数据时发挥着关键作用。理解其工作原理和优化策略对于设计高效、可靠的软件系统至关重要。在实际编程中，合理地使用无序词典可以极大地提升程序的性能和可维护性。