我遇到了一个问题，我有数百万个键值对，我需要使用键随机访问（而不是使用迭代器）。
键的范围在编译时是未知的，但键值对的总数是已知的。
我已经研究过HashMap和Hashset数据结构，但它们并不是真正的O(1)，因为在哈希码发生冲突的情况下，它们会变成LinkedLists数组，在最坏的情况下具有线性搜索复杂性。
我还考虑过增加HashMap中的存储桶数量，但它不能确保每个元素都存储在单独的存储桶中。
有什么方法可以存储和访问数百万个O(1)复杂度的键值对吗？
理想情况下，我希望每个键都像一个变量，相应的值应该是分配给该键的值
提前致谢。
我认为您混淆了 Big O 表示法所代表的含义。它定义了函数的限制行为，不一定是实际行为。
对于插入、删除和搜索操作，哈希映射的平均复杂度为 O(1)。这是什么意思？平均而言，无论哈希映射的大小如何，这些操作都将在恒定时间内完成。因此，根据映射的实现，查找可能不会完全执行一个步骤，但相对于哈希映射的大小，它很可能不会涉及超过几个步骤。
哈希映射对这些操作的实际表现如何取决于几个因素。最明显的是用于存储键的散列函数。优先考虑在散列范围内更均匀地分布计算的散列并限制冲突次数的散列函数。这些区域中的散列函数越好，散列图实际上在恒定时间内运行的越接近。
影响实际哈希映射行为的另一个因素是如何管理存储。随着项目的添加和删除，映射如何调整大小和重新定位条目有助于通过使用最佳数量的桶来控制哈希冲突。有效地管理散列图存储将允许散列图以接近恒定的时间运行。
综上所述，有一些方法可以构建具有 O(1) 最坏情况的查找行为的哈希映射。这是使用完美的散列函数完成的。完美的散列函数是键和散列之间的可逆 1-1 函数。通过完美的哈希函数和适当的哈希映射存储，可以实现 O(1) 查找。使用这种方法的先决条件是事先知道所有的键值，这样才能开发出完美的散列函数。
可悲的是，您的案例不涉及已知键，因此无法构建完美的哈希函数，但是，可用的研究可能会帮助您为您的案例构建近乎完美的哈希函数。
不，通用数据类型没有这样的（已知的）数据结构。
如果有的话，它很可能已经取代了大多数常用库中的哈希表，除非有一些重大的缺点，比如巨大的常数因子或荒谬的内存使用，其中任何一个都可能使它对你来说不可行。
我在上面说“通用数据类型”，因为可能存在一些特定的特殊情况，例如当键是小范围内的整数时 - 在这种情况下，您可以只拥有一个数组，其中每个索引对应于相同的密钥，但这实际上也是一个哈希表，其中密钥对其自身进行哈希处理。
请注意，您需要一个糟糕的哈希函数、哈希函数的病态输入或一个非常小的哈希表才能真正获得哈希表的最坏情况 O(n) 性能。在你去寻找其他东西之前，你真的应该测试它，看看它是否足够快。您也可以尝试TreeMap，它的 O(log n) 操作有时会优于HashMap.