Hashtable实施

Question

我最近被问到'你将如何实施一个可憎的'.我知道哈希算法是关键的,因为较少的冲突会带来更好的WRT性能,但是应该使用什么算法/数据结构来为插入/删除/查找提供分摊的常量时间{O(1)}？

Answer 1

哈希表有两种主要可能性:

1. 打开寻址,这是一个简单的数组 [动态数组实际上,如果你可以让你的表在飞行中增长].一旦遇到冲突 - 您需要使用第二个哈希函数来查找元素将映射到的下一个主进程.请注意,当您的哈希表也允许删除时,此解决方案存在一些问题[可以解决].["删除"主菜的特殊标记]
2. 链接 - 在此解决方案中,数组中的每个主进程都是一个链接列表 - 包含对此主菜进行散列的所有元素.在这里 - 映射到特定值的所有元素都在列表中.

关于哈希表[在两个解决方案中]的重要部分,为了允许机动化的O(1)插入/ del /查找 - 分配更大的表并在达到预定义的加载因子后重新散列.

编辑:复杂analsis:
假设负载系数p为一些p < 1.

1. 每次访问中"碰撞"的概率p因此,数组访问的意思是:Sigma(i * p^(i-1) * (1-p)) for each i in [1,n]这给你:Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST.[看看Sigma(i*p ^(i-1))<1 /(p-1)^ 2在wolfram alpha中的正确性.因此平均导致对阵列的恒定访问次数.另外:在达到加载因子后,您可能需要重新散列所有元素,从而导致O(n)对数组的访问.这导致n * O(1)ops [添加n个元素]和1 * O(n)op [rehashing],因此得到:(n * O(1) + 1 * O(n)) / n = O(1)armotorized time.
2. 与(1)非常相似,但分析是在列表访问上完成的.每个操作只需要一次数组访问,以及不同数量的列表访问 - 使用与以前相同的分析.