我遇到了一个问题，我有数百万个键值对，我需要使用键随机访问(而不是使用迭代器)。
编译时不知道键的范围，但键值对的总数已知。
我研究了HashMap和Hashset数据结构，但它们并不是真正的O(1)，就像哈希冲突的情况一样-将它们编码为 LinkedLists 数组，在最坏的情况下具有线性搜索复杂性。
我还考虑过增加HashMap中存储桶的数量，但这并不能确保每个元素都存储在单独的存储桶中。
有没有办法以 O(1) 复杂度存储和访问数百万个键值对？
理想情况下，我希望每个键都像一个变量，并且相应的值应该是分配给该键的值
提前致谢。
最佳答案
我认为您混淆了大 O 表示法所代表的含义。它定义了函数的限制行为，不一定是实际行为。
HashMap 的插入、删除和搜索操作的平均复杂度为 O(1)。这是什么意思？也就是说，平均而言，无论 HashMap 的大小如何，这些操作都将在恒定时间内完成。因此，根据映射的实现，查找可能不会精确地执行一步，但相对于 HashMap 的大小，它很可能不会涉及多个步骤。
HashMap 对于这些操作的实际表现如何取决于几个因素。最明显的是用于存储键的哈希函数。优选在散列范围内更均匀地分布计算出的散列并限制冲突次数的散列函数。这些区域的哈希函数越好， HashMap 就越接近在恒定时间内实际运行。
影响实际 HashMap 行为的另一个因素是存储的管理方式。添加和删除项目时映射如何调整条目大小和重新定位条目有助于通过使用最佳数量的存储桶来控制哈希冲突。有效地管理 HashMap 存储将允许 HashMap 以接近恒定的时间运行。
综上所述，有一些方法可以构造具有 O(1) 最坏情况查找行为的 HashMap 。这是使用 perfect hash function 完成的。完美的哈希函数是键和哈希值之间可逆的 1-1 函数。通过完美的哈希函数和适当的 HashMap 存储，可以实现 O(1) 查找。使用这种方法的前提是提前知道所有的键值，这样就可以开发出完美的哈希函数。遗憾的是，您的案例不涉及已知的 key ，因此无法构建完美的哈希函数，但是，可用的研究可能会帮助您为您的案例构建近乎完美的哈希函数。
关于Java 键值集合，数百万个随机无序键的复杂度为 O(1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21756574/