java源码解读--hashmap

HashMap

数据结构特点

其类定义如下

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

继承了AbstractMap，实现了Map、Cloneable、Serializable，注意并没有实现Collection接口。
HashMap允许K/V值为null，非线程安全，不保证有序。

1.7版本与1.8版本区别

JDK1.7的hashmp数据结构为数组+链表，而JDK1.8的数据结构为数组+链表+红黑树，加入红黑树是为了解决发生hash碰撞后链表过长从而导致索引效率问题，主要利用了红黑树快速增删改查的特点，时间复杂度从O(n)降为O(logn)。
链表转红黑树条件：链表长度>8时，将链表转化为红黑树。

• 无冲突：存放在数组
• 有冲突但链表长度<8：存放在单链表
• 有冲突但链表长度>8：转化为红黑树并存放

构造方法

4个构造方法，可指定初始容量、负载因子以及输入一个map

   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);
       this.loadFactor = loadFactor;
// 设置扩容阈值，详见tableSizeFor函数
       this.threshold = tableSizeFor(initialCapacity);
   }


   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }

   public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
   }
//将传入的容量大小转化为：大于传入容量的最小的2次幂
   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;
   }

初始化参数

//默认初始桶大小为16，必须是2的幂次
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大桶大小，2的30次方
   static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子，在容量自动增加前可达到最大值的一种尺度
   static final float DEFAULT_LOAD_FACTOR = 0.75f;
//与红黑树有关的参数
//桶的树化阈值：链表最大长度，超过即转化为红黑树
   static final int TREEIFY_THRESHOLD = 8;
//桶的链表还原阈值：当低于该值，树转化为链表
   static final int UNTREEIFY_THRESHOLD = 6;
//最小树型化容量阈值，当哈希表的容量>该值时，才允许树形化链表
//否则，若桶内元素太多，则直接扩容，而不是树型化
   static final int MIN_TREEIFY_CAPACITY = 64;



//存储数据的Node类型数组
   transient Node<K,V>[] table;
//HashMap的大小，即HashMap中存储的键值对数量
   transient int size;
//扩容阈值，当table的大小大于等于扩容阈值时，就会扩容哈希表。
//扩容是对哈希表进行resize操作，resize操作一般会增加一倍容量
//扩容阈值=容量*负载因子
   int threshold;

Node定义

//hashmap对链表节点的定义
   static class Node<K,V> implements Map.Entry<K,V> {
//hash值
       final int hash;
//Key值
       final K key;
//Value值
       V value;
//下一个node指针
       Node<K,V> next;

       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }

       public final K getKey()        { return key; }
       public final V getValue()      { return value; }
       public final String toString() { return key + "=" + value; }

       public final int hashCode() {
           return Objects.hashCode(key) ^ Objects.hashCode(value);
       }

       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
       }

       public final boolean equals(Object o) {
           if (o == this)
               return true;
           if (o instanceof Map.Entry) {
               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
               if (Objects.equals(key, e.getKey()) &&
                   Objects.equals(value, e.getValue()))
                   return true;
           }
           return false;
       }
   }

TreeNode定义

继承了LinkedHashMap的Entry类，有左右指针和前后指针以及颜色属性。

 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	//父节点
	TreeNode<K,V> parent;  // red-black tree links
	//左儿子
        TreeNode<K,V> left;
	//右儿子
        TreeNode<K,V> right;
	//前一个元素
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
	//颜色
        boolean red;
	
	....
}

put方法

put方法主体函数

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

hash函数

无论1.7还是1.8版本都对hashcode进行了扰动处理，这样做是为了加大哈希码的随机性使分布更均匀，减少hash冲突

//将key转化为hashcode，调用了一次hashCode + 1次位运算 + 1次异或运算
//需要注意的是：当key=null时，hash值等于0，所以hashmap的key可以为null
//而hashtable在对key进行hashcode()时，若key为null会抛出异常，所以hashtable的key不能为null
//当key不等于null时，先计算hashcode()，然后对哈希码进行扰动处理：按位异或哈希码
   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

计算table存储下标

在1.8中没有专门的函数计算entry在桶中的存储位置，只是通过一句代码来完成，即

//h即hashcode，length即table的长度
h & (length-1)

putVal操作

   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;

//数组为空则通过resize方法创建，即第一次调用put函数时使用resize初始化哈希表
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;

// 计算插入存储数组的索引i，根据键值key计算的hash值得到
// 若该索引位置上没有元素，则直接插入，否则代表hash冲突
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);

       else {
//该分支代表出现hash冲突场景
           Node<K,V> e; K k;
//如果table[i]的元素的key和待插入元素的key一样，则用新值覆盖旧值
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               e = p;

//如果table[i]的元素是红黑树，直接插入红黑树
           else if (p instanceof TreeNode)
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//若是链表
           else {
               for (int binCount = 0; ; ++binCount) {
	//遍历完所有的节点没有发现key相等的节点
                   if ((e = p.next) == null) {
		//在p后插入新节点
                       p.next = newNode(hash, key, value, null);
		//判断是否需要树型化
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           treeifyBin(tab, hash);
                       break;
                   }
	//发现有key相等的节点
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       break;
	//更新p指向下一个节点
                   p = e;
               }
           }
	// 发现key冲突，直接用新value覆盖旧value
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
	//替换旧值会调用的方法，默认为空
               afterNodeAccess(e);
               return oldValue;
           }
       }
       ++modCount;
// 插入成功后，判断是否需要扩容
       if (++size > threshold)
           resize();
//插入成功时会调用的方法，默认实现为空
       afterNodeInsertion(evict);
       return null;
   }

将链表替换为红黑树

当一个桶中的元素个数超过TREEIFY—THRESHOLD(默认是8)，就会将链表转化为红黑树。

//该方法将链表节点替换为红黑树节点
   final void treeifyBin(Node<K,V>[] tab, int hash) {
       int n, index; Node<K,V> e;
// 如果hash表为空，或者hash表中元素小于进行树型化的阈值，就去扩容
       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
           resize();
       else if ((e = tab[index = (n - 1) & hash]) != null) {
	//设置红黑树头尾节点
           TreeNode<K,V> hd = null, tl = null;
           do {
	//新建一个树形节点
               TreeNode<K,V> p = replacementTreeNode(e, null);
	//如果尾节点为null，说明p是头节点
               if (tl == null)
                   hd = p;
               else {
	//设置p的前后节点
                   p.prev = tl;
                   tl.next = p;
               }
               tl = p;
           } while ((e = e.next) != null);
	//让桶元素指向红黑树的头节点
           if ((tab[index] = hd) != null)
	//调整红黑树
               hd.treeify(tab);
       }
   }

初始化红黑树

treeifyBin方法只将链表节点替换成了红黑树节点，并没有建立起红黑树的结构，接下来需要调用treeify方法构建红黑树

      final void treeify(Node<K,V>[] tab) {
          TreeNode<K,V> root = null;
          for (TreeNode<K,V> x = this, next; x != null; x = next) {
              next = (TreeNode<K,V>)x.next;
              x.left = x.right = null;
//头节点为黑色
              if (root == null) {
                  x.parent = null;
                  x.red = false;
                  root = x;
              }
              else {
                  K k = x.key;
                  int h = x.hash;
                  Class<?> kc = null;
	//从根节点开始遍历，调整顺序
                  for (TreeNode<K,V> p = root;;) {
                      int dir, ph;
                      K pk = p.key;
                      if ((ph = p.hash) > h)
                          dir = -1;
                      else if (ph < h)
                          dir = 1;
	//碰撞节点的hash值应该都一样，这里不是很明白为什么需要判断不想等的情况
                      else if ((kc == null &&
                                (kc = comparableClassFor(k)) == null) ||
                               (dir = compareComparables(kc, k, pk)) == 0)
	//相等或者不能比较的情况
                          dir = tieBreakOrder(k, pk);

                      TreeNode<K,V> xp = p;
                      if ((p = (dir <= 0) ? p.left : p.right) == null) {
                          x.parent = xp;
	//如果当前节点比x的哈希值大，x就是做孩子，否则x就是右孩子	
                          if (dir <= 0)
                              xp.left = x;
                          else
                              xp.right = x;
	//平衡红黑树
                          root = balanceInsertion(root, x);
                          break;
                      }
                  }
              }
          }
          moveRootToFront(tab, root);
      }

插入新节点时保证红黑树特性

这里会根据红黑树特性调整结构

      static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                  TreeNode<K,V> x) {
//新增节点默认红色
          x.red = true;
//xp父节点，xpp祖父节点，xppl祖父节点左节点，xppr祖父节点右节点
          for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//x的父节点为空，x是根节点，是黑色
              if ((xp = x.parent) == null) {
                  x.red = false;
                  return x;
              }
              else if (!xp.red || (xpp = xp.parent) == null)
//父节点是黑色，祖父节点是空，直接返回
                  return root;
//父节点是红色，父节点是祖父节点的左节点
              if (xp == (xppl = xpp.left)) {
	//祖父节点的右节点是红色
                  if ((xppr = xpp.right) != null && xppr.red) {
	//祖父节点右节点设置为黑色
                      xppr.red = false;
	//父节点设置为黑色
                      xp.red = false;
	//祖父节点设置为红色
                      xpp.red = true;
	//把祖父节点设置为当前节点，并继续循环操作
                      x = xpp;
                  }
	//如果祖父节点的右节点是黑色或者空
                  else {
	//若x是父节点的右节点，则需要进行左旋
                      if (x == xp.right) {
                          root = rotateLeft(root, x = xp);
                          xpp = (xp = x.parent) == null ? null : xp.parent;
                      }
	//经过左旋x为左节点
                      if (xp != null) {
		//父节点设置为黑色
                          xp.red = false;
		//祖父节点不为空
                          if (xpp != null) {
		//祖父节点设置为红色
                              xpp.red = true;
		//右旋操作
                              root = rotateRight(root, xpp);
                          }
                      }
                  }
              }
//父节点为右节点
              else {
	//祖父节点左节点为红色
                  if (xppl != null && xppl.red) {
	//祖父节点左节点设置为黑色
                      xppl.red = false;
	//父节点为黑色
                      xp.red = false;
	//祖父节点为红色
                      xpp.red = true;
	//循环操作
                      x = xpp;
                  }
//祖父节点左节点为黑色
                  else {
	//右旋
                      if (x == xp.left) {
                          root = rotateRight(root, x = xp);
                          xpp = (xp = x.parent) == null ? null : xp.parent;
                      }
	//x变为右节点
                      if (xp != null) {
                          xp.red = false;
                          if (xpp != null) {
                              xpp.red = true;
		//以祖父节点为支点左旋
                              root = rotateLeft(root, xpp);
                          }
                      }
                  }
              }
          }
      }

扩容操作

以下两种场景需要扩容：1.初始化哈希表 2.当前数组容量过小进行扩容

   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) {
           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
           newCap = DEFAULT_INITIAL_CAPACITY;
           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 = newThr;
       @SuppressWarnings({"rawtypes","unchecked"})
           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) {
                   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;
                           if ((e.hash & oldCap) == 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;
   }

get操作

   public V get(Object key) {
       Node<K,V> e;
//计算hash值，调用getNode查询，如果为空返回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;
//通过(n - 1) & hash找到下标
       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;
   }