algorithm - 哈希表实现

标签 algorithm computer-science hashtable

最近有人问我'你将如何实现一个hastable'。我知道哈希算法至关重要,因为冲突越少,WRT性能就越好,但是应采用哪种算法/数据结构来提供摊销的固定时间{O(1)}进行插入/删除/查找?

最佳答案

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

  • 打开寻址,这是一个简单数组 [如果您是动态数组,
    可以让您的 table 快速增长]。冲突解决后-您需要使用第二个哈希函数来查找元素将映射到的下一个主菜单。请注意,当您的哈希表还允许删除时,此解决方案会有一些麻烦(可以解决)。 [“已删除”主菜的特殊标记]
  • 链接-在此解决方案中,数组中的每个主菜都是链表-包含散列到该主菜的所有元素。在这里-映射到某个值的所有元素都在列表中。

  • 为了允许自动化的O(1)插入/删除/查找,在[两种解决方案中]哈希表的重要部分是分配一个更大的表,并在达到预定义的load factor后重新哈希。

    编辑:复杂度分析:
    假设某些p的负载因子为p < 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 in wolfram alpha的正确性]。因此,平均而言,对数组的访问次数是恒定的。另外:在达到负载系数之后,您可能需要重新哈希所有元素,从而导致对该数组的O(n)访问。这将导致n * O(1) ops [添加n个元素]和1 * O(n) op [rehashing],因此您得到:(n * O(1) + 1 * O(n)) / n = O(1)自动化时间。
  • 与(1)非常相似,但分析是针对列表访问进行的。每个操作只需要一个数组访问权限,以及不同数量的列表访问权限-与以前的分析相同。
  • 关于algorithm - 哈希表实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9409699/

    相关文章:

    bash - Bash 中的多维关联数组

    c - 为什么这对于C中的哈希表不起作用(指针)

    algorithm - std::priority_queue接受2个参数(用于Dijkstra算法)

    java - 可以将第n个元素移到堆栈顶部的堆栈

    algorithm - 从向量的历史中预测二进制占用向量

    algorithm - 消防部门覆盖区域

    data-structures - 如果知道二叉树的节点数,如何找到其最小高度?

    algorithm - 子串比较

    algorithm - 给出实数列表。有什么好的算法可以将它们组合在一起,以使组中的最大值和最小值小于5。

    java - 对于一般情况,当任何一个都可以工作时,使用 HashMap 或哈希表哪个更好?