我看过很多例子或文章解释基于数组的哈希映射。
例如，所有数据都存储在一个数组中，您可以通过用其键调用散列函数来获得值的索引。
因此，在没有冲突的情况下，对哈希映射的任何访问都是O(1)。因为访问实际上是针对一个数组的，知道它的索引。
我的问题是，是否有任何特定语言或库的实现，哈希映射不是建立在数组上的
哈希映射必须建立在数组上吗？
虽然还有其他数据结构同时使用散列函数和数组以外的数据结构来提供键/值映射(您可以在https://en.wikipedia.org/wiki/Hash_trie)，我认为他们不是"；散列映射"；因为组合短语是一般意图和理解的。当人们谈论哈希图时，他们通常希望下面有一个哈希表，它将有一个bucket数组(或者偶尔有几个bucket，以允许逐渐调整大小以获得更一致的性能(。
对散列映射的一个普遍期望是，它们提供摊销的O(1(查找，只有在对密钥进行散列后，您才能使用散列值进行O(1。数组是具有该属性的明显数据结构。还有一些其他选项，比如有一个固定深度的数组树，上层保存指向下层的指针，最后一层是值或指向它们的指针。为了使整个容器支持任意大小，必须允许至少一个级别任意增长。在最大深度不变的情况下，查找步骤的数量与存储的键或元素的数量不相关，因此它仍然是O(1(查找。这提供了对更频繁地在大阵列之间复制/移动元素的成本的部分缓解，但代价是在查找期间要遍历的级别数量不断增加(但不变(。
C++std::deque利用这种结构来提供O(1(查找。请参阅通过索引访问的STL数据是否为O(1(？用于解释，图表。也就是说，我从未见过有人在实现哈希映射时选择使用deque。