哈希表

2021-05-16 约 2825 字预计阅读 6 分钟次阅读

概念：

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为$ O(N) $，平衡树中为树的高度，即$ O(log_2 N) $，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表) 例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：$ hash(key) = key % capacity$; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

冲突-概念：

对于两个数据元素的关键字$ k_i $和$ k_j (i != j) $，有$ k_i != k_j $，但有：$ Hash(k_i) == Hash(k_j) $，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

冲突-避免：

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

两种方式解决冲突

链表式解决（Separate Chaining)

每个数据单元存储数据和next指针，形成链表
开放地址(Open Addressiting)

不用next指针，把其他下标的位置都对外开放。开放地址的方法:
- a.线性探测法
  
  冲突后搜索次数线性循环向后放置
- b.平方探测(二次方探测)
  
  冲突后根据搜索次数的平方循环向后放置
- c.双哈希

冲突-避免-哈希函数设计：

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数： 1.直接定制法–(常用)

取关键字的某个线性函数为散列地址：$ Hash（Key）= A*Key + B $ 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况 2.除留余数法–(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：$ Hash(key) = key% p(p<=m)$ ,将关键码转换成哈希地址

还有很多例作为了解：平方取中法，折叠法，随机数法，数学分析法（可以自己查找资料）

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

冲突-避免-负载因子调节（重点）

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

冲突-解决

解决哈希冲突两种常见的方法是：闭散列和开散列

冲突-解决-闭散列：

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

线性探测比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。插入

通过哈希函数获取待插入元素在哈希表中的位置

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

二次探测：

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$ H_i = (H_0+i^2)% m $，或者： $ H_i = (H_0-i^2)% m $ 其中：i = 1,2,3…， $ H_0 $是通过散列函数Hash(x)对元素的关键码 key进行计算得到的位置，m是表的大小。对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

冲突-解决-开散列/哈希桶（重点）

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

冲突严重时的解决办法：刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

每个桶的背后是另一个哈希表
每个桶的背后是一棵搜索树

哈希表满了

当哈希表的存储量超过百分之七十（负载因子，默认为0.75），会执行rehashing，即再次哈希，找一个大于原来二倍以上的质数重新进行计算以扩充hash表的容量

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


// key-value 模型
public class HashBucket {
  private static class Node {
    private int key;
    private int value;
    Node next;
    public Node(int key, int value) {
      this.key = key;
      this.value = value;
   }
 }
  private Node[]  array;
  private int size;  // 当前的数据个数
  private static final double LOAD_FACTOR = 0.75;
  public int put(int key, int value) {
    int index = key % array.length;
    // 在链表中查找 key 所在的结点
     // 如果找到了，更新
    // 所有结点都不是 key，插入一个新的结点
    for (Node cur = array[index]; cur != null; cur = cur.next) {
      if (key == cur.key) {
        int oldValue = cur.value;
        cur.value = value;
        return oldValue;
     }
   }
    Node node = new Node(key, value);
    node.next = array[index];
    array[index] = node;
    size++;
    if (loadFactor() >= LOAD_FACTOR) {
      resize();
   }
    return -1;
 }
  private void resize() {
    Node[] newArray = new Node[array.length * 2];
    for (int i = 0; i < array.length; i++) {
      Node next;
      for (Node cur = array[i]; cur != null; cur = next) {
        next = cur.next;
        int index = cur.key % newArray.length;
        cur.next = newArray[index];
        newArray[index] = cur;
     }
   }
    array = newArray;
 }
  private double loadFactor() {
    return size * 1.0 / array.length;
 }
  public HashBucket() {
    array = new Node[8];
    size = 0;
 }
  public int get(int key) {
    int index = key % array.length;
    Node head = array[index];
    for (Node cur = head; cur != null; cur = cur.next) {
      if (key == cur.key) {
        return cur.value;
     }
   }
   return -1;
 }
}

目录

哈希表

概念：