在数组长度固定的情况下，哈希表查找的时间复杂度为O(1(对我来说是有意义的。然而，我不知道哈希表是如何为动态长度的数组(如链表(工作的。当数组的元素分散在整个内存中时，直接索引显然是不可能的。
您是正确的，键实现为链表的哈希表将不是是O(1)，因为键搜索是O(n)。但是，链表并不是唯一可扩展的结构。
例如，您可以使用一个可调整大小的向量，例如每次需要展开时大小都会翻倍的向量。是可直接寻址的，而不需要O(n)搜索，因此满足O(1)条件。
请记住，调整向量的大小几乎肯定会改变将项目分配到向量的各个存储桶中的公式，这意味着你很有可能必须重新计算存储每个现有项目的存储桶。
即使单个insert操作可能必须进行O(n(重新分配，这仍将摊销到O(1(，因为重新分配将不频繁，并且随着向量变大，随着时间的推移，可能会变得更少频繁。
您仍然可以将链表的元素映射到哈希表。是的，我们确实事先不知道列表的大小，所以我们不能使用C样式或不可扩展的数组来表示我们的哈希表。这就是矢量发挥作用的地方(或者ArrayList，如果您来自Java(。
关于向量的速成课程是：如果当前数组中没有更多空间，则制作一个双倍大小的新数组，并将以前的元素复制到其中。更正式地说，如果我们想将n+1元素插入到n大小的数组中，则它将制作一个2n大小的新阵列。对于下一个溢出，它将创建一个大小为4n的数组，依此类推
以下代码可以将链表的值映射到哈希表中。
void map(Node* root) {
vector<int> hash;
while(root){
hash[root->val]++;
root = root->next;
}
for(int i = 0; i<hash.size(); i++){
cout<<hash[i]<<" ";
}
}