神的尾巴

全栈工程师、独立开发者

0%

聊聊哈希表

发表于 分类于 阅读次数： 评论：

哈希表（Hash Table，散列表），根据key而直接访问在内存存储位置的数据结构。

优缺点

优点：查找效率快
缺点：初始化时需要确定哈希表的大小

构造散列

主要有以下几种方法：

  1. 直接定址法：类似hash(k) = a * k + b，ab为常数。

  2. 数字分析法：取关键字中的若干位组成哈希地址。

    1
    2
    关键字序列：345789,234923,2335345,1231245
    如果第三位和第五位分配比较平均，则可以散列为：58,42,33,32

  3. 平方取中法：通过对关键字进行平方后，取中间几位作为哈希地址。因为平方后中间几位和关键字中每一位都相关，所以概率比较平均。

    1
    2
    3
    关键字序列：11050201,11250102,01110525
    平方后：122157778355001,126564795010404,001233265775625
    取中间位：778,795,265

  4. 分段折叠法：这种方法是按哈希表地址位数将关键字分成位数相等的几部分，然后将分割后的每部分低位对齐相加并舍弃最高进位。

    根据折叠方式的不同，分为折叠法和移位法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    关键字：123603247112020
    哈希长度为：1000

    // 折叠法
    1 2 3
       3 0 6
       2 4 7
       2 1 1
       0 2 0
       -----
    9 0 7

    // 移位法
    1 2 3
    6 0 3
       2 4 7
       1 1 2
    0 2 0
       -----
       1 1 5 （最高位已舍弃）

  5. 随机数法：通过伪随机函数生成。

  6. 除留余数法：类似hash(k) = k mod p，也可以组合其他散列方式，最后执行，限定范围。

处理冲突

处理冲突有以下几种方法：

  1. 开发地址法：hash = (hash(key) + d)，如果hash冲突后，通过添加增量序列d来避免冲突。
    增量序列有下列几种：
    1). 线性探测：d = 1,2,3…。
    2). 平方探测：d = pow(1),pow(2),pow(3)…。
    3). 伪随机数序列。
  2. 单独链表发：将散列到同一存储位置的所有元素保存在一个链表中。
  3. 再散列：通过多个构造不同的哈希函数，一直计算知道冲突不再产生。
  4. 建立一个公共溢出区：针对散列重复的，都统一放到公共溢出区。

参考文章

  1. 哈希表-wiki
  2. 哈希表处理冲突的方法
觉得对你有帮助的话，请我喝杯咖啡吧~.