查找-散列表

1. 描述

• 思路：

  • 通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术——散列技术。
  • 存储位置=f（关键字）

• 散列函数:

  • 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,我们把这种对应关系f称为散列函数(哈希函数)

• 怎样是好的散列函数 可以参考两个原则

  • 计算简单
  • 散列地址分布均匀

• 常用的哈希函数

  • 直接寻址法
    • 如 f(key)=a*key+b（a、b为常数）
    • 场景
      • 适合查找表较小且连续的情况，优点 简单、均匀，也不会产生冲突， 缺点 先知道关键字的分布情况
  • 数字分析法
    • 如手机号 130XXXX1234
      • 130 是品牌 XXXXX基本相同，1234 变化大。
      • 哈希函数 f(key) = key%100 ^ key.subString(0,3);
    • 场景
      • 处理关键字位数比较大的情况
  • 平方取中法
    • 如 f(key) = key^2.subString(中间n位)
      • 如 f(1234) = 1522756.subString(中间3位)=227
    • 场景
      • 不知道关键字的分布，而位数又不是很大的情况
  • 折叠法
    • 将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
  • 除留余数法
    • f(key)=key mod p(p≤m)
      • mod是取模（求余数）的意思。这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
  • 随机数法
    • f(key)=random(key)
    • 场景
      • 关键字的长度不等时

• 处理哈希冲突的方法

  • 开放定址法
    • 一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总是能找到。
    • f i (key)=(f(key)+d i )MOD m(d i =1,2,3,......,m-1)
  • 再哈希法
    • 每当发生哈希地址冲突，就换一个散列函数计算，总会有一个可以把冲突解决掉。
    • f i (key)=RH i (key)(i=1,2,...,k)
      • RH i 就是不同的散列函数，如除留余数、折叠、平方取中
  • 链地址法
    • 通一个hash值引起的冲突，放到一起存储。
    • 高级语言很多采用这种方式 如java HashMap
  • 公共溢出区法
    • 凡是冲突的建立了一个公共的溢出区来存放。

• 散列表的适合场景

  • 缓存
  • 快速查找

• 散列表查找性能分析

  • 散列函数是否均匀
  • 处理冲突的方法
  • 列表的装填因子
    • 装填因子α=填入表中的记录个数/散列表长度

2. HashMap 案例

2.1 哈希方法

• jdk8 f(key) = (len - 1) & (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
  • 把h 高位^地位 让散列地址分布均匀
  • 规律 X % 2^n = X & (2^n - 1)， 对一个数对2^n取模等于这个数 对 2^n -1 按位与运算
  • 假如直接对hashCode 按位与，其实只对hashCode后面几个位进行运行，因为长度一般不是特别大，前面几位都为0，所以要实现hashCode 的每一位 都能影响 hash 的结果
    • 所以对hashcode进行扰动
      • hashCode ^ (hashCode>>>16)

2.2 处理哈希冲突的方法

• 链地址法
  • 链表，红黑书 红黑树参考
    • 链表元素个数大于等于8时 并且桶容量>= 64，链表转换成树结构
    • 链表元素个数小于等于6时，树结构还原成链表

2.3 HashMap 相关问题

• 1 树化的阈值为什么是8

  • 如果key的hashCode 分布离散良好，链表长度符合泊松分布，长度为8的时候，概率仅为0.00000006 ，红黑树的树化基本不可能发生。

• 2 还原为链表的阈值为什么是6

  • 主要是避免链表和红黑树之间频繁的转换。来回转换结构会降低性能。

• 3 HashMap jdk7 与 jdk8 主要区别

  • size>=64并且链表长度>=8 转换为红黑树， 红黑树 查找效率更高。

    • 红黑树

      • 红黑树性质
        • 跟节点黑色
        • 一个节点要么红色要么黑色
        • 每个叶子节点黑色。
        • 如果一个节点是红色，那它儿子都是黑的。
        • 每个节点，从该节点到其所有后代节点路径上，包含相同的黑节点。
      • 理解
        • 与平衡二叉树比较
          • 查找 性能略逊于平衡二叉树。
          • 插入删除 ，红黑树任何不平衡，都会在三次左右旋之内解决。
        • 理解红黑树 先理解2-3树。
          • 整颗树把红节点上面那个线划平就是一颗 2-3树， 有三个孩子的节点包含两个节点，这两个节点用红色表示。

    • 扩容的时候 不需要重新计算hash

      • 扩容 size<<1 - 1 后hash & 运算与之前size -1 & 运行区别 只在一位差别 就在size 对应的二进制 为1的位置
        • hash&n
          • 0 在之前的桶位置 j 。
          • 1 在 j+size 的桶位置。

    • 循环列表问题

      • jdk7 扩容的 transfer 倒置链表， 并发可能出现循环链表
        • get 的时候 会死循环 cpu 100%
      • jdk8 通过 head tail 避免这个情况。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    //链表元素个数大于等于8时，链表转换成树结构
    static final int TREEIFY_THRESHOLD = 8;
    
    //链表元素个数小于等于6时，树结构还原成链表
    static final int UNTREEIFY_THRESHOLD = 6;    
    
    
        static final int hash(Object key) {
        int h;
    //  (h = key.hashCode()) ^ (h >>> 16) 把h 高位^地位 让散列地址分布均匀
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
        
}