java api系列之HashMap

java api系列目录

java api系列

简述

首先看一下官方文档是怎么介绍HashMap的：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

简单来说，就是：

• 基于Map接口来实现，支持所有的map操作
• Key和Value都支持null值
• 不保证有序，无论是插入顺序，还是Key的排序等
• 不保证固定顺序，随着容量的增大或减少，顺序会发生变化

举个例子就很清楚了：

Map map = new HashMap();
map.put("java", 0);
map.put("python", 1);
map.put("go", 2);
map.put("php", 3);
map.put("c++", 4);
map.put(null, 5);
map.put("noValue", null);

通过IDEA断点查看里面的存储结构是这样的，可以看到插入顺序是打乱了的：

影响映射分布的两个因子

第一个是hash表的capacity（容量）：

The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

第二个是load factor（负载因子）：

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

当hash表存储的数据量超过capacity 乘以 load factor时，hash表会扩容，容量会翻倍，部分数据会重新映射到扩容后的地方。所以初始容量和负载因子是影响HashMap性能及分布的两个重要因素。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap默认的负载因子是0.75，这个是比较折中的数字，平衡空间和时间的开销。负载因子如果太大，会造成hash冲突严重，影响查询性能；如果太小，会容易触及扩容，浪费空间。

有效预估HashMap存储的实际数据量，来设定初始容量，可以有效避免经常扩容导致的性能开销。

put方法详解

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  //table不存在，则创建table
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  //通过hash计算偏移量位置，如果这个位置没有节点，则自己新建一个节点
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    //e为需要覆盖的节点
    Node<K,V> e; K k;
    //如果已经存在的节点的hash值和值相等（分别对应的是类的hashCode方法和equals方法）
    //则认为是覆盖操作，先记录为e，后面会将新的value覆盖旧的value
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    //如果节点是树，则以树的方式添加
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      //节点是链表
      //通过遍历链表的方式，如果整个链表所有节点没有和新的节点重复，则将新的节点放置尾端
      //如果因为放多了一个新的节点，导致链表过长，则将链表转换成红黑树
      //如果其中有一个节点和新的节点重复，则记录并跳出循环
      for (int binCount = 0; ; ++binCount) {
        //将新的节点放置链表尾端，此时e为null
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          //链表过长，为了提高查询性能，将链表转换成树
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        //链表中，其中一个节点的hash值和值相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    //如果e不为null，说明是新值覆盖旧值
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      //判断写入条件，并写入
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      //直接返回，没有改变table的大小
      return oldValue;
    }
  }
  ++modCount;
  //改变了table的大小，判断是否触发扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

总结起来就是：

1. 通过hash计算偏移量获得节点位置
2. 如果位置没有旧节点，则新建节点存放
3. 如果旧节点的key等于新节点的key，则用新的value覆盖旧的value
4. 如果旧节点是树节点，则以树的形式添加新节点
5. 如果是一个链表，则以链表的信息添加新的节点，重复则覆盖，不然的放置尾端；链表过长，则转换成树
6. 如果table大小发生改变，并且触发扩容，则扩容

hash函数详解

看完put方法，大致对HashMap整个结构有了个大概的了解，那么其中一个比较重要的步骤，通过hash值计算table偏移量，这个决定了新旧值碰撞概率，以及扩容时，节点移动时的效率。

下面是API实现的hash方法：

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
  int h;
  //兼容key为null的情况
  //hashCode是integer类型，共32位
  //保留高16位，优化低16位，在低16位中，将高16位与低16位做异或操作
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为啥要将高16位和低16位做异或操作，其实再put方法里面，我们看到计算偏移量的计算是这样的：(n - 1) & hash，n的大小一般不会很大，超过16位(65535)；所以高低位异或的目的，是让n小时，高16位也能参与hash计算，增加散列的随机性。

get方法详解

有了put方法里面讲解的节点存储结构，及hash的计算，那么就很容易理解get方法了

public V get(Object key) {
  Node<K,V> e;
  //兼容value是null的情况
  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 && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))
          return first;
      if ((e = first.next) != null) {
          //以树节点的方式获取
          if (first instanceof TreeNode)
              return ((TreeNode<K,V>)first).getTreeNode(hash, key);
          //以链表的方式，遍历获取
          do {
              if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
                  return e;
          } while ((e = e.next) != null);
      }
  }
  return null;
}

resize方法详解

有了前面的铺垫，那么怎么设计扩容，才能使节点移动最少呢？

官方是这么说的：

Initializes or doubles table size.  If null, allocates in
accord with initial capacity target held in field threshold.
Otherwise, because we are using power-of-two expansion, the
elements from each bin must either stay at same index, or move
with a power of two offset in the new table.

在扩容时，将table的大小乘以2，为什么是乘以2而不是3？

在计算偏移量：(n - 1) & hash时，n是比较关键的参数，如果n一开始是16，那么n-1的二进制是：1111，那么偏移量计算就是与hash的低4位&操作；如果n = n * 2 为32，n-1的二进制是：11111，那么偏移量计算就是与hash的低5位&操作。

这样的话，原来的节点将发生什么变化呢？

如果原来存在这样两个节点，hash值分别是A：101011和B：111011，在n=16时，这两个节点是发生碰撞的(以链表或树的形式共存)，偏移量都是1011；扩容后，A的偏移量是01011即1011保持不变，B的偏移量是11011发生节点转移。

看到这里，就明白了这样的扩容设计，保持了一半左右的节点不需要移动，而大部分碰撞节点，将迁移到新的位置，使存储和查询更加高效。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        //table的大小达到最大值，就不在扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //没达到最大值，则大小翻倍，触发阈值也翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //table大小和触发阈值都小于等于0，则说明此时做的是初始化操作
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的触发阈值等于0，则重新计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //遍历table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果这个是单节点，则直接转移到新节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果这个节点是树节点，按树节点的方式处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //遍历链表
                    do {
                        next = e.next;
                        //节点位置不变，举上面的例子：
                        //A的hash为101011，oldcup为16(10000)
                        //那么结果就是0，所以A节点归到loHead
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //反过来，就是节点位置改变了的，归到hiHead
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //将重构后的链表loHead覆盖到原来的位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //移动后的新链表hiHead放置到新的位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

整篇下来，基本就可以了解到HashMap的实现原理了，介于篇幅有限，文章中埋了个坑，树节点没怎么讲，想要了解更多，就持续关注 java api系列 ，并点赞留言告知。