哈希table 理解
Hash table understading
我知道我有一个包含 m 个单元格和 n 个元素的散列 table，搜索成本为 O(n/m)（平均）
让我们看一下使用 hashtable 的两个子算法：
A. 当你有 n 个元素时，将它们插入到 m=100 的哈希 table 中，并使用它来搜索元素。
B. 当你有 n 个元素时，将它们插入到哈希 table 中，其中 m=n/3 并使用它来搜索元素。
在情况 A 中，搜索的复杂度为 O(n/100)=O(n)
在情况 B 中，搜索的复杂度为 O(n/(n/3))=O(1)
这意味着如果我们想使用 hashtable 在 O(1) 复杂度中搜索元素，我们必须在创建 hashtable 时知道元素的数量，通过 n 除以 a 来计算 m常量并传递给集合的构造函数 m
我说的对吗？我必须在 hashtable 的构造函数中传递 m 才能使用 hashtable 的好处吗？
答案是，正如我从上面的评论中了解到的那样，大多数实现会自动调整哈希表的大小，因此 m 总是类似于 n..2n。当元素数量对于当前 m 变得太大时，分配更大的哈希表
这意味着添加到哈希表在最坏的情况下可能是 O(n)（因为分配了更大的哈希表）但在摊销中它是 O(1)，就像将元素添加到 ArrayList
我知道我有一个包含 m 个单元格和 n 个元素的散列 table，搜索成本为 O(n/m)（平均） 让我们看一下使用 hashtable 的两个子算法： A. 当你有 n 个元素时，将它们插入到 m=100 的哈希 table 中，并使用它来搜索元素。 B. 当你有 n 个元素时，将它们插入到哈希 table 中，其中 m=n/3 并使用它来搜索元素。
在情况 A 中，搜索的复杂度为 O(n/100)=O(n) 在情况 B 中，搜索的复杂度为 O(n/(n/3))=O(1) 这意味着如果我们想使用 hashtable 在 O(1) 复杂度中搜索元素，我们必须在创建 hashtable 时知道元素的数量，通过 n 除以 a 来计算 m常量并传递给集合的构造函数 m
我说的对吗？我必须在 hashtable 的构造函数中传递 m 才能使用 hashtable 的好处吗？
答案是，正如我从上面的评论中了解到的那样，大多数实现会自动调整哈希表的大小，因此 m 总是类似于 n..2n。当元素数量对于当前 m 变得太大时，分配更大的哈希表 这意味着添加到哈希表在最坏的情况下可能是 O(n)（因为分配了更大的哈希表）但在摊销中它是 O(1)，就像将元素添加到 ArrayList