哈希 table 查找总是 O(n) 时间？
Hash table is always O(n) time for lookup?
我不明白哈希表是如何进行恒定时间查找的，如果有恒定数量的桶的话。假设我们有 100 个桶和 1,000,000 个元素。这显然是 O(n) 查找，这就是复杂点，以了解对于非常大的 n 值事物的行为方式。因此，哈希表永远不是常量查找，它总是 O(n) 查找。
为什么人们说它的平均查找时间为 O(1)，最坏情况下只有 O(n)？
通俗地说，挥手：
在一个极端情况下，您可以拥有一个完美分布的散列映射，每个桶一个值。在这种情况下，您直接查找 returns 值，成本是 1 次操作——或者按一次操作的顺序，如果您愿意：O(1).
在现实世界中，实现往往是这样安排的，通过扩展table等大小来满足数据的要求。当您的项目多于存储桶时，您就会开始增加复杂性。
在最坏的情况下，你有一个桶，一个桶里有n个项目。在这种情况下，它基本上就像线性地搜索列表。因此，如果该值恰好是最后一个，则需要进行 n 次比较才能找到它。或者，按 n 的顺序：O(n).
对于给定的数据集，后一种情况几乎总是/可能/存在。这就是为什么人们投入了大量的研究和精力来提出好的哈希算法。因此，理论上可以设计一个会导致碰撞的数据集。因此，有一些方法可以达到 O(n) 性能，除非实施调整其他方面； table 大小、哈希实现等等等等
说
Say we have 100 buckets, and 1,000,000 elements.
你基本上剥夺了 hashmap 的重新散列的真正能力，也没有根据需要考虑 hashmap 的初始容量。在每个条目都有自己的桶的情况下，Hashmap 更有效。更高的 hashmap 容量可以实现更小的冲突百分比。每次碰撞都意味着您需要遍历相应的列表。
哈希 table 实现应考虑以下几点。
哈希table 的设计使其在条目数大于桶数达到某个阈值时重新调整自身大小。如果我们希望实现自己的自定义 Hash table.
一个好的散列函数可以确保条目在散列桶中分布良好table。这使存储桶中的列表保持简短。
以上注意访问时间保持不变。
使用散列的目的是能够像数组一样直接索引到table。在理想情况下，每个桶只有一个项目，我们很容易实现 O(1)。
一个实用的哈希 table 的桶数多于它的元素数，因此每个桶只有一个元素的几率很高。如果插入到 table 中的元素数量过多，将调整 table 的大小以增加桶的数量。
总是有可能每个元素都有相同的哈希值，或者所有活动的哈希值都被分配到同一个桶；在那种情况下，查找时间确实是 O(n)。但是一个好的哈希 table 实现将被设计成最小化这种情况发生的可能性。
我不明白哈希表是如何进行恒定时间查找的，如果有恒定数量的桶的话。假设我们有 100 个桶和 1,000,000 个元素。这显然是 O(n) 查找，这就是复杂点，以了解对于非常大的 n 值事物的行为方式。因此，哈希表永远不是常量查找，它总是 O(n) 查找。
为什么人们说它的平均查找时间为 O(1)，最坏情况下只有 O(n)？
通俗地说，挥手：
在一个极端情况下，您可以拥有一个完美分布的散列映射，每个桶一个值。在这种情况下，您直接查找 returns 值，成本是 1 次操作——或者按一次操作的顺序，如果您愿意：O(1).
在现实世界中，实现往往是这样安排的，通过扩展table等大小来满足数据的要求。当您的项目多于存储桶时，您就会开始增加复杂性。
在最坏的情况下，你有一个桶，一个桶里有n个项目。在这种情况下，它基本上就像线性地搜索列表。因此，如果该值恰好是最后一个，则需要进行 n 次比较才能找到它。或者，按 n 的顺序：O(n).
对于给定的数据集，后一种情况几乎总是/可能/存在。这就是为什么人们投入了大量的研究和精力来提出好的哈希算法。因此，理论上可以设计一个会导致碰撞的数据集。因此，有一些方法可以达到 O(n) 性能，除非实施调整其他方面； table 大小、哈希实现等等等等
说
Say we have 100 buckets, and 1,000,000 elements.
你基本上剥夺了 hashmap 的重新散列的真正能力，也没有根据需要考虑 hashmap 的初始容量。在每个条目都有自己的桶的情况下，Hashmap 更有效。更高的 hashmap 容量可以实现更小的冲突百分比。每次碰撞都意味着您需要遍历相应的列表。
哈希 table 实现应考虑以下几点。
哈希table 的设计使其在条目数大于桶数达到某个阈值时重新调整自身大小。如果我们希望实现自己的自定义 Hash table.
，这就是我们应该如何设计
一个好的散列函数可以确保条目在散列桶中分布良好table。这使存储桶中的列表保持简短。
以上注意访问时间保持不变。
使用散列的目的是能够像数组一样直接索引到table。在理想情况下，每个桶只有一个项目，我们很容易实现 O(1)。
一个实用的哈希 table 的桶数多于它的元素数，因此每个桶只有一个元素的几率很高。如果插入到 table 中的元素数量过多，将调整 table 的大小以增加桶的数量。
总是有可能每个元素都有相同的哈希值，或者所有活动的哈希值都被分配到同一个桶；在那种情况下，查找时间确实是 O(n)。但是一个好的哈希 table 实现将被设计成最小化这种情况发生的可能性。