哈希表原理和冲突碰撞解决方案

什么是哈希表？

        又名为散列表，本质就是一个数组，提供了键(Key)和值(Value)的映射关系，通过Key可以高效查找到匹配的Value。Key多数是字符串形式，通过hash函数把key进行运算，得出数组下标；value可以是一个POJO或者json对象。一般包括key-value也可以叫Node或者Entry。Hash常用函数包括了CRC16、CRC32、murmurHash 等，也可以自定义。可以用于实现字典、字符串搜索、计数器、缓存、LRU缓存、排序和其他一些常见的数据结构。

Hash函数如下所例：

//hash函数
public int hashCode() {
  int h = hash;
  if (h == 0 && value.length > 0) {
    char val[] = value;
    for (int i = 0; i < value.length; i++) {
      //每个字符*31
      h = 31 * h + val[i];
    }
    hash = h;
  }
return h;
}

Hash碰撞问题处理方案

含义：Hash碰撞的意思是不同key计算得到的Hash值相同，两个或多个键值映射到同一个桶（bucket）中。

冲突处理方案1——开放地址法：

        存操作：当某个Key通过哈希函数获得对应的bucket下标被占用时，继续寻找后续未被占用的bucket存储（也就是改变冲突位置，将元素放到下一个空闲位置中）

        读操作：把Key通过哈希函数转化成数组下标，即bucket桶的位置，找到bucket下标所对应的Entry，判断key是否正确，正确则直接获取对应的value；如果不正确，说明产生hash冲突， 则顺着bucket节点继续往下遍历，直到找到key一样的entry，即可取值；

冲突处理方案2——链表法：

        存操作：当发生冲突时，将冲突的元素放在散列表中的桶里，每个桶里存放一个链表 ListNode，将冲突的元素放到链表中，每个元素都存储在链表的一个节点中；

        读操作 ：把Key通过哈希函数转化成数组下标， 即bucket桶的位置，找到bucket下标所对应的链表 ListNode，判断链表的第一个Entry的key是否正确，正确则直接获取对应的value；如果不正确，说明产生hash冲突， 则顺着节点遍历该单链表，直到找到key一样的entry，即可取值；

        注意：JDK1.8之前链表采用的就是这种，之后改动为链表的长度小于8，采用链表存储；链表的长度大于8，链表会转换成红黑树存储 （treeifyBin函数：把容器里的元素变成树结构）

冲突处理方案3——再哈希法：

        当发生冲突时，使用另一个不同的哈希函数，将冲突的元素重新哈希，以解决冲突问题

冲突处理方案4——建立公共溢出区

        当发生冲突时，将冲突的元素放到一个公共的溢出区中，公共溢出区中的元素，使用链表组织起来。