昨晚在我的 COMP 课上，我们学习了哈希以及它在尝试在哈希表中查找元素 x 时通常如何工作。
我们的场景是我们的表中有一个包含 1000 个元素的数据集，我们想知道 x 是否包含在该表中。
我们的教授设计了一个包含 100 个 Java 数组，并表示要存储这 1000 个元素，数组的每个位置都将包含一个指向链表的指针，我们将在其中保存我们的元素。
假设哈希函数将 1000 个元素中的每一个完美映射到 0 到 99 之间的值，并将元素存储在数组中的位置，则每个链表中将包含 1000/100 = 10 个元素。
现在要知道 x 是否在表中，我们只需对 x 进行散列，找到它的散列值，在该槽中查找数组并迭代我们的链表检查表中是否有 x。
我的教授最后说，查找 x 是否在表中的预期复杂度是 O(10)，实际上只是 O(1)。我不明白这是怎么回事。在我看来，如果数据集为 N 且数组大小为 n，则平均需要 N/n 步才能在表中找到 x。根据定义，这不是恒定时间吗，因为如果我们扩大数据集，时间仍会增加？
我浏览了 Stack Overflow 和在线，每个人都说散列是 O(1) 的预期时间复杂度，但有一些注意事项。我读过人们讨论链接以减少这些警告。也许我遗漏了一些关于确定时间复杂度的基本知识。
TLDR:为什么要花 O(1) 的时间在哈希表中查找值，而它似乎仍然取决于数据集的大小(因此是 N 的函数，因此不是常量)。
最佳答案
In my mind, if the dataset is N and the array size is n then it takes on average N/n steps to find x in the table.
这是一个误解，因为散列只需要您计算对象应该存储在的正确桶(在本例中为数组索引)。即使数据集的大小发生变化，此计算也不会变得更复杂.
您所说的这些注意事项很可能是哈希冲突:多个对象共享相同的哈希代码；这些可以通过更好的哈希函数来避免。
关于java - 为什么具有链表的哈希表被认为具有恒定的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43288582/