哈希 table 真的是 O(1) 吗？
Is a hash table really O(1)?
按我的理解，一个散列table是一个链表数组，所以它实际上应该是O(n/array_length).
不是说它的 O(1) 完全错误吗？
例如，如果我在基于 100 大小的数组的哈希 table 上有 100 万个项目，则平均查找需要 5,000 个项目。显然不是 O(1)，尽管我假设散列的大多数实现 table 使用更大的数组。
大多数语言（JS、Go 等）散列 table 实现中通常使用的数组大小是多少？
在您提到的实现中，数组开始时很小，随着添加的元素越来越多，重新分配的大小也越来越大。
数组大小保持在元素计数的常数因子内，因此每个槽的平均元素数是有界的。
你是对的。一般来说，不能说all hash table都是O(1)。这取决于一些设计决策和其他因素。
在您的示例中，您似乎在谈论具有固定数量的桶 (100) 和无限数量的条目 N 的哈希 table。使用该设计，平均需要进行 N / 50 次比较才能找到存在的密钥，平均需要进行 N / 100 次比较才能发现不存在的密钥。即O(N).
有一个通用的实施策略来处理这个问题。随着散列 table 变大，您会定期调整主数组的大小，然后重新分配键/条目。例如，标准 Java HashMap 和 HashTable 类 跟踪数组大小与条目数的比率。当比率超过可配置的 负载因子 时，主阵列大小 ts 加倍。 （有关负载因子的解释，请参阅 javadoc。）
这个分析比较复杂。但是，如果我们可以假设键在桶中大致均匀分布，我们得到以下结果：
- 平均查找时间为
O(1)
- 平均插入时间为
O(1)
- 最坏情况下的插入时间为
O(N) ... 当插入触发调整大小时。
如果密钥分布严重偏斜怎么办？
如果哈希函数很差，或者生成密钥的过程不正常，就会发生这种情况。
好吧，如果您对此不采取任何措施，最坏的情况是所有键都具有相同的哈希值并最终出现在同一个存储桶中……无论主数组大小如何。这导致 O(N) 查找和插入。
但是有几种方法可以缓解这种情况。一种简单的方法是对密钥的哈希码执行第二次哈希操作。这在某些情况下会有所帮助。更复杂的方法是用平衡二叉树替换散列链。这将查找和插入的平均行为（对于病态键的情况）从 O(N) 更改为 O(logN)`。
从 Java 8 开始，HashMap 实现使用哈希链或树，具体取决于给定桶中的键数。
And what is usually the array size that is being used in most languages' (JS, Go, etc) hash table implementations?
对于 Java（可能还有其他），数组大小在散列 table 的生命周期内发生变化，如上所述。在Java中，大小或数组有上限。 Java 数组只能有 231 - 1 个元素。
按我的理解，一个散列table是一个链表数组，所以它实际上应该是O(n/array_length).
不是说它的 O(1) 完全错误吗？
例如，如果我在基于 100 大小的数组的哈希 table 上有 100 万个项目，则平均查找需要 5,000 个项目。显然不是 O(1)，尽管我假设散列的大多数实现 table 使用更大的数组。
大多数语言（JS、Go 等）散列 table 实现中通常使用的数组大小是多少？
在您提到的实现中，数组开始时很小，随着添加的元素越来越多，重新分配的大小也越来越大。
数组大小保持在元素计数的常数因子内，因此每个槽的平均元素数是有界的。
你是对的。一般来说，不能说all hash table都是O(1)。这取决于一些设计决策和其他因素。
在您的示例中，您似乎在谈论具有固定数量的桶 (100) 和无限数量的条目 N 的哈希 table。使用该设计，平均需要进行 N / 50 次比较才能找到存在的密钥，平均需要进行 N / 100 次比较才能发现不存在的密钥。即O(N).
有一个通用的实施策略来处理这个问题。随着散列 table 变大，您会定期调整主数组的大小，然后重新分配键/条目。例如，标准 Java HashMap 和 HashTable 类 跟踪数组大小与条目数的比率。当比率超过可配置的 负载因子 时，主阵列大小 ts 加倍。 （有关负载因子的解释，请参阅 javadoc。）
这个分析比较复杂。但是，如果我们可以假设键在桶中大致均匀分布，我们得到以下结果：
- 平均查找时间为
O(1) - 平均插入时间为
O(1) - 最坏情况下的插入时间为
O(N)... 当插入触发调整大小时。
如果密钥分布严重偏斜怎么办？
如果哈希函数很差，或者生成密钥的过程不正常，就会发生这种情况。
好吧，如果您对此不采取任何措施，最坏的情况是所有键都具有相同的哈希值并最终出现在同一个存储桶中……无论主数组大小如何。这导致 O(N) 查找和插入。
但是有几种方法可以缓解这种情况。一种简单的方法是对密钥的哈希码执行第二次哈希操作。这在某些情况下会有所帮助。更复杂的方法是用平衡二叉树替换散列链。这将查找和插入的平均行为（对于病态键的情况）从 O(N) 更改为 O(logN)`。
从 Java 8 开始，HashMap 实现使用哈希链或树，具体取决于给定桶中的键数。
And what is usually the array size that is being used in most languages' (JS, Go, etc) hash table implementations?
对于 Java（可能还有其他），数组大小在散列 table 的生命周期内发生变化，如上所述。在Java中，大小或数组有上限。 Java 数组只能有 231 - 1 个元素。