哈希表（HashMap）内部结构必须基于数组吗？有无非数组实现？

哈希表并非必须基于数组实现，但绝大多数主流实现选择数组作为底层存储，这和数组的随机访问特性直接相关——正是数组的O(1)索引访问，才让哈希表能实现平均O(1)的查询、插入、删除效率。

不过确实存在不依赖数组的哈希表实现，常见的场景和例子包括：

• 纯链表哈希表：在嵌入式系统这类内存资源受限的场景中，会出现纯链表实现的哈希表。哈希函数将键映射到不同的链表分组，操作时遍历对应分组的链表完成查找或修改。这种实现无需预分配内存，但代价是平均访问时间退化为O(k)（k为分组内元素数量），失去了哈希表的核心高效性。

• 分布式哈希表（DHT）的非数组实现：像Chord、Kademlia这类分布式系统中的哈希表，用环形链表或树状结构组织网络节点，通过哈希函数定位存储节点，底层并没有使用单一的内存数组，而是依赖分布式节点的存储能力。这类实现更关注分布式环境下的扩展性和容错性，而非单机的极致性能。

• 基于平衡二叉树的键值存储替代：比如Java的TreeMap，它基于红黑树（平衡BST）实现，虽然属于有序映射而非传统哈希表，但可以作为无需数组的键值存储方案。不过它的访问时间是O(log n)，无法达到哈希表的O(1)平均性能。

为什么主流哈希表都用数组？核心原因是数组的随机访问特性是实现哈希表高效性的关键。当通过哈希函数计算出索引后，能直接定位到目标位置，即使处理哈希冲突（比如链地址法、开放地址法），也是在数组的基础上扩展，保证绝大多数场景下的O(1)平均性能。如果脱离数组，很难找到另一种能做到O(1)随机访问的通用存储结构，这也是数组成为哈希表主流底层实现的根本原因。

内容的提问来源于stack exchange，提问作者Jae