Hashtable get(kType key) 如何分摊时间复杂度 O(1) 而不是 O(log n)？

Question

与键相关联的索引通常在最简单的散列实现中table，通过以下方式检索：

size++;
int hash = hashcode(key);
int index = hash % size;

对于任意键，我们可以说索引将是 [0, size - 1] 范围内的整数，每个结果的概率相等。这些概率由下面的 table 描述，用于添加 N 个元素后的前 5 个索引。

Index            |   0              1               2              3                4
--------------------------------------------------------------------------------------------
Probabilities    |  1
                 |  1/2             1/2
                 |  1/3             1/3             1/3
                 |  1/4             1/4             1/4             1/4
                 |  1/5             1/5             1/5             1/5             1/5    
                 |                                    ...
                 |  1/N             1/N             1/N             1/N             1/N
____________________________________________________________________________________________
Total            |  H(N)         H(N) - 1        H(N) - 1.5      H(N) - 1.83     H(N) - 2.08

H(N) 描述在索引 0 处的链中应该收集多少元素。之后的每个链在统计上应该有更少的元素。

H(N) 也是直到并包括第 N 项的调和级数的值。虽然没有描述调和级数的广义闭合形式，但可以使用以下公式非常准确地近似这个值，

H(N) ≈ ln(N) + 0.5772156649 + 1 / (2N) - 1 / (12N^2)

参考：https://math.stackexchange.com/questions/496116/is-there-a-partial-sum-formula-for-the-harmonic-series

“近似”部分可以归结为ln(N) + 0.5772156649之后的项。 ln(N) 是最大的函数，因此摊销时间复杂度应该是 O(log n).

有什么我想念的吗？我将不胜感激这里的澄清。

Answer 1

将我的评论扩展为答案 - 让我们从这里开始：

The index that a key is associated with is generally, in the most simplest implementation of a hash table, retrieved in the following way:
size++;
int hash = hashcode(key);
int index = hash % size;

这实际上不是大多数散列 table 的实现方式。相反，大多数哈希 table 使用如下策略：

选择一些固定的起始槽数（比如 8 或 16 等）
添加元素后，将该元素放入插槽 hashcode(key) % tablesize。
一旦 table 中的项目数与插槽数的比率超过称为 负载因子的阈值，执行 rehash：将 table 的大小加倍，并通过重新计算 hashcode(key) % tablesize 来重新分配现有元素新的 table 大小。（这最后一步确保在 table 已调整大小的情况下仍然可以找到项目，并确保项目分布在整个 table，而不仅仅是前几个插槽。）

具体分析速度有多快将取决于您如何实现散列 table。如果您使用链式哈希（每个项目都被放入一个槽中，然后存储在一个单独的数组或包含该槽中所有项目的链表中）并且您的哈希函数“或多或少”是均匀随机的，那么（直观地）项目可能会或多或少均匀地分布在 table 个插槽中。你可以通过假设你确实有一个随机散列函数来对此进行正式分析，在这种情况下，任何一个槽中的项目的预期数量最多是 table 的负载因子（数量的比率项目到插槽的数量）。加载因子通常选择为常数，这意味着每个槽的预期项目数上限为该常数，因此要求 O(1) 预期查找时间。（对于线性探测哈希 table 的查找的预期成本，您也可以获得类似的 O(1) 界限，但数学涉及更多。）

由于重新散列步骤，出现了“摊销”部分。这个想法是，大多数时候，插入不会将加载因子推到重新哈希所需的阈值之上，因此它们非常快。但是时不时地，您确实需要重建 table。假设您将 table 的大小加倍，您可以证明每次重新散列都是由未触发重新散列的线性数量的插入进行的，因此您可以将重新散列所需的工作反推到之前的操作.

Hashtable get(kType key) 如何分摊时间复杂度 O(1) 而不是 O(log n)？

How is the Hashtable get(kType key) amortized time complexity O(1) and not O(log n)?

java

data-structures

time-complexity

hashtable

amortized-analysis