聊聊散列表以及HashMap内部实现

淩亂°似流年 2022-01-17 22:15 197阅读 0赞

#### 散列表 ####

散列表又叫哈希表，是根据键(Key)而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

在日常生活中，也有类似"散列表"， 比如打篮球比赛，每个球员穿着有号码的球服，号码代表哪个球员，球员如果有犯规，裁判用手势指明几号球犯规即可。说湖人24号球员，就是指科比，这里24就是Key, 散列函数可以理解为f(x) = x, 经过24计算后得到24，指向数组的24下标。

下面用一张描述一下散列表:

图中hash方法是散列函数，散列函数在散列表中非常重要，决定了映射关系，决定了放在数组的位置。往散列表添加的过程是，比如添加key=24， value=kobe这个, key经过散列函数计算得到index=2，就将它在数组下标为2中。散列表中移除元素， 散列函数得到2, 把下标为2的元素设为null。取值过程也一样，24号是谁，hash(24)算一下得到2，取出下标为2的元素，返回value就可。散列表的操作是不是很简单，其实不是的，刚刚只是理想的状态, 随着加入的元素越来越多就会产生一些问题。假如又加入一个元素, key为99,hash(99)算出为2，这是发现数组2的位置已经有元素，这种情况就是哈希冲突，是由于哈希函数，不同的key计算后得到相同的值导致。有人就会说了设计一个不会冲突的函数就好啦，不好意思小声告诉你，几乎不存在这样的函数。下面就讲讲什么是哈希函数。

#### 哈希函数 ####

哈希函数有3点要求：

*  函数计算得到的值是一个非负数
 *  如果 key1 = key2, 那么hash(key1) = hash(key2)
 *  如果 key1 != key2, 那么hash(key1) != hash(key2)

前1，2点相对容易实现，第3点前面为什么说几乎不存在这样的函数, 即使著名的MD5, SHA等哈希算法，也无法完全避免哈希冲突，只不过他们出现冲突的概率非常低而已。哈希冲突无法避免是因为数组的长度有限，当你添加元素大于数组长度时，就肯定出现会冲突。想象一下，你有3个笼子，有4个鸟，那么肯定有1个笼子有2个鸟。

为了解决哈希冲突，常用方法有两类, 开放寻址法和链表法:

*  开放寻址法又可以细分几种，感兴趣得自己查资料，这里简单说一下其中一种简单的线性探测，插入数据时发现冲突，把index依次加1去找有没有空的位置，有空位置就放进去，如果到数组最后都没有，可以数组index=0开始遍历找。但是这种方法取数据时，如果遇到冲突时，相对效率会低一点，需要遍历数组，找到key相匹配的元素;
 *  链表法相对比较简单，在相应的数组的index里放一个链表，比如说, 放一个单链表, 冲突了就往单链表里放即可。取数据时也是需要遍历单链表, 找到key相匹配的元素。

当散列表中出现哈希冲突时，对于添加和获取元素都会相应的降低效率，不再是大O(1), 所以散列表要尽量得较低冲突的发生, 哈希函数要尽量保证均匀。 除了哈希冲突，数组会有满的时候，满了就需要扩容，但是扩容会使之前映射关系失效，需要重新进行hash(key)计算，重新计算出index。上面说了一堆理论，下面以java的HashMap为例子，看看源码是怎么实现散列表的。

#### HashMap的内部实现 ####

首先看构造函数(源码版本是java 8)

public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
      //loadFactor负载系数, 
      this.loadFactor = loadFactor;
      //threshold临界值
      this.threshold = tableSizeFor(initialCapacity);
    }
    
    //tableSizeFor这个方法看起来可能会懵逼，
    //这方法把一个数，先减1, 然后向右移1位再异或自己, 
    //比如0010右移1位是0001,异或后时0011,再异保证原来的位置和右移1位的位置都是1,
    //接着继续向右移2,4,8,16位并异或
    //1+2+4+8+16=31，int类型一共是32， int最大值是2的32减1
    //移16位并异或的n是保证了数的所有地位都是1
    //MAXIMUM_CAPACITY = 2的30次方, 这是这方法的最大值
    //如果小于MAXIMUM_CAPACITY，会进行n+1，n没加1前所有的位都是1
    //加1后，逢1进1，最后的得到都是2的多少次方的值。
    //如果cap = 9，tableSizeFor方法得到是16。(16是2的4次方)
    static final int tableSizeFor(int cap) {
      int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    复制代码

HashMap构造器给两个成员变量赋值，分别是loadFactor负载系数与threshold临界值，并且threshold经过tableSizeFor方法得到是一个int, 这个int不小于传进去的数，并是一个2次方值。接着分析HashMap.put()

public V put(K key, V value) {
      //调用hash方法，的到int类型的key, 再调用putVal
      return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {
      //key为null时，返回0, 调用Object的hashCode方法，并异或(h >>> 16)
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
      //定义两个数组tab和p变量
      Node<K,V>[] tab; Node<K,V> p; int n, i;
      //this.table是一个Node<K,V>[]成员变量
      //tab = this.table, this.table数组赋值给tab
      if ((tab = this.table) == null || (n = tab.length) == 0){
        //第一次put数据时table为null或者数组长度为0进来这里
        //调用resize方法，会创建一个特定数组，并会赋值到this.table
        //resize方法等会再细看, n等于this.table数组的长度
        //tab = resize(), 保证tab变量不为空
        n = (tab = resize()).length; 
      }  
      //i = (n - 1) & hash 计算得到i，i就是进过哈希函数后得到数组的下标
      // p = tab[index]
      if ((p = tab[i = (n - 1) & hash]) == null){
        // 数组的下标没存放值，调用newNode创建一个Node<K,V>对象，存储key,value
        // 并赋值给这个数组的下标位置
        tab[i] = newNode(hash, key, value, null);
      }else {
        Node<K,V> e; K k;
        //p在前面if条件语句中赋值了，到这里p不能为空，p = tab[index]
        //说明key进过哈希函数后得到数组的下标,已经有值啦
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))){
          //hash值相同, key是同一个指针或者用equals方法对比是不是相同的key
          //这里结合前面hash(Object key)和key.equals的判断说明，使用hashmap时
          //需要重写obj的hashCode和equals方法来判断是不是同一个key。
          e = p; 
        }else if (p instanceof TreeNode)
          //这里是java8开始引入的TreeNode, TreeNode是用"红黑树"来代替链表
          //这个先不深入研究
          e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
          //当哈希冲突时，会走这个else代码块
          for (int binCount = 0; ; ++binCount) {
            //遍历, p是当前数组下标的对象Node
            //Node内部有next成员变量，next也是Node类型，
            //Node是一个链表的结果
            if ((e = p.next) == null) {
              //newNode创建一个Node对象复制给next
              //哈希冲突了，往链表里添加
              p.next = newNode(hash, key, value, null);
              if (binCount >= TREEIFY_THRESHOLD - 1) {
        // -1 for 1st
                //TREEIFY_THRESHOLD = 8, 是一个常量临界值
                //treeifyBin()，当链表长度超过临界值后会把链表转成"红黑树"结构
                //本文不深入研究
                treeifyBin(tab, hash);
              }  
              break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))){
              break;
            }  
            p = e;
          }
        }
        if (e != null) { 
          //e 什么时候不为null, key相同时
          //key相同时，把value替换啦
          V oldValue = e.value;
          //onlyIfAbsent来控制是否旧的value替换新的value
          if (!onlyIfAbsent || oldValue == null)
            e.value = value;
          afterNodeAccess(e);//忽略，不研究
          return oldValue;
        }
      }
      ++this.modCount;
      //散列表的size加一
      if (++this.size > this.threshold){
        // size大于threshold，需要进行数组扩容和重新哈希映射
        resize();  
      }  
      afterNodeInsertion(evict);
      return null;
    }
    复制代码

简单看一下创建一个Node的代码, Node是散列表元素, next是单链表。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
      return new Node<>(hash, key, value, next);
    }
    
    static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      V value;
      Node<K,V> next;
    }
    复制代码

根据上面代码总结一下添加元素的过程，Hashmap的Key和Value都是Object, Key的映射唯一性不能用对象本身，需要重写hashcode方法保证与equal方法保证，Node里成员变量hash 等于 (h = key.hashCode()) ^ (h >>> 16) 。 (n - 1) & hash 得到就是数组的下标index。这里设计有点巧妙的，h = key.hashCode()里h是key的hash值，int有32位，h ^ (h >>>16)意思是低16位异或高16位，查了一下资料这样处理好处是的得到的数同时拥有低16位和高16位的特征，保证了数值的随机性，减低哈希冲突，这步计算称为扰动函数过程。 (n - 1) & hash 实质是求余计算, 等价于 hash % (n -1) ， 这里n是数组的长度， 求余后得到的index就保证了一定在数组长度内。 (n - 1) & hash = hash % (n -1) 这个等价关系有个条件n必须是2次方, n - 1的值二进制里的所有位置都为1(比如16 - 1= 0000 1111)。回看到Hashmap的构造器里tableSizeFor方法，就明白为什么了，就是要保证n的是2次方。如果调用Hashmap无参数构造器，默认是16。添加元素的过程中，数组下标里没值，就放一个Node对象，如果有值就分为2个两种情况，第一种key相同，替换value; 第二种如果key不相同，就是哈希冲突啦，追加Node链表里，当链表中元素个数超过了一个临界值，Node链表会换成红黑树结构TreeNode。

看看HashMap获取元素过程

public V get(Object key) {
      Node<K,V> e;
      return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k)))){
          //对比key, 以及equals方法，key相同，返回Node的值
          return first;
        } 
        //first是Node的当前的值，first的hash和key都不是要拿的值
        //从next链表指针中拿
        if ((e = first.next) != null) {
          if (first instanceof TreeNode)
            //如果是红黑树，从红黑树中找
            return ((TreeNode<K,V>)first).getTreeNode(hash, key);
          do {
            //遍历链表，从next指针从找key相同的，找到返回值
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
          } while ((e = e.next) != null);
        }
      }
      return null;
    }
    复制代码

前面说到当链表中元素个数超过了一个临界值，Node链表会换成红黑树结构。红黑树也是基于链表实现一种数据结构，当哈希冲突比较多时，链表遍历每次需要从链头中获取，效率低，换成红黑树是为提高效率。红黑树本文不深入，有兴趣自己查查。下面看看resize方法

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = this.table;
      			//oldCap旧的数组长度，第一次为0
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //成员变量threshold赋值给oldThr
            int oldThr = this.threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
              	//newCap = oldCap << 1, 扩容oldCap乘以2
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY){
                    //扩容, oldThr乘以2
                    newThr = oldThr << 1; 
                }  
            }
            else if (oldThr > 0) {
                //成员变量threshold赋值给oldThr
                //oldThr赋值给newCap
                newCap = oldThr; 
            }else {
                //当调用了无参HashMap构造器是oldThr=0，
                // newCap, newThr 设定默认值
                newCap = DEFAULT_INITIAL_CAPACITY;
                //newThr等于负载系数乘以默认数组长度
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
      			//threshold等于负载系数乘以数组长度
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes","unchecked"})
      		  //创建新的数组Node
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {
                //遍历旧的数组
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        //e = oldTab[j]
                        //旧的数组设为null，清楚旧数组元素
                        oldTab[j] = null;
                        if (e.next == null){
                            //e.next == null意味着这个节点没有哈希冲突，链表中没数据
                        		//e.hash & (newCap - 1)根据hash值重新计算新数组里index
                            //把e赋值到新的数组里
                            newTab[e.hash & (newCap - 1)] = e;
                        }else if (e instanceof TreeNode){
                           //有哈希冲突时，红黑树的处理
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        }else { 
                            // 有哈希冲突，链表中有数据, 遍历链表，并迁移到新的数组中
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                   //如果为0,说明扩容后索引的计算依然与扩容前一致
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                  //扩容后索引与扩容前不一致
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }
    复制代码

resize方法，第一次会创建一个新的数组，数组长度为2次方值，每次扩容后数组容量右移1位，也就是乘以2，threhold = 数组容量 \* 负载因子，在put方法的最后，如果size > threhold, 就需要扩容，HashMap负载因子默认为0.75，意思是在添加数据的过程，当size 大于当前数组75%长度时，需要扩容到数组长度的2倍。扩容过程中需要把旧数组的元素移到新数组中，旧数组的元素包含没哈希冲突的元素和有哈希冲突的元素，没哈希冲突的元素，根据新的数组长度重新配置index存放即可，有哈希冲突的还需要把链表或者红黑树的元素一并复制到新的数组中。 添加和获取过程如果都理解啦，HashMap的移除过程也就很明朗啦，hash值得到index，对比一下key是否相同，如果有冲突遍历一下找到相同key, 找到元素移除即可，源码就不列出来啦，HashMap的添加移除获取过程大概原理就这样啦。

转载于:https://juejin.im/post/5cc5379c6fb9a031f416087b