JAVA1.8 HashMap源码,句句注释，如果这样都看不懂HashMap源码，那你就真没救了

目录

默认参数及构造方法put()方法resize()扩容方法get()方法remove()方法replace()方法

看源码之前首先要知道HashMap底层存储结构

默认参数及构造方法

//默认的table大小，左移4位等于16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //table最大长度 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //树化阈值，链表长度到达8 static final int TREEIFY_THRESHOLD = 8; //树降级为链表的阈值6，树的子节点到达6时，降级为链表 static final int UNTREEIFY_THRESHOLD = 6; //树化的另一个参数，当哈希表中的所有元素超过64时，才会允许树化 static final int MIN_TREEIFY_CAPACITY = 64; //定义哈希表 transient Node<K,V>[] table; // transient Set<Map.Entry<K,V>> entrySet; //当前哈希表的元素个数 transient int size; //当前哈希表结构修改次数 transient int modCount; //扩容阈值，当哈希表中的元素超过阈值时，触发扩容 int threshold; //负载因子 用于计算扩容阈值，threshold=loadFactor*table大小 final float loadFactor; //tableSizeFor的作用：计算大于等于当前cap的一个数字，并且这个数一定时二的次方数 static final int tableSizeFor(int cap) {//cap=10的话 int n = cap - 1;//n-1=9， n |= n >>> 1;//9转换二进制0b1001, 0b1001|0b0100=>0b1101 n |= n >>> 2;//0b1101|0b0001=>0b1111 n |= n >>> 4;//0b1111|0b0000=>0b1111 n |= n >>> 8;//0b1111|0b0000=>0b1111 n |= n >>> 16;//0b1111|0b0000=>0b1111 //0b1111=>15 因为15>0 又因为15<MAXIMUM_CAPACITY 返回return 15+1 返回16 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } //构造方法1 两个参数（表格大小，负载因子） 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; //把initialCapacity转换为一个大于等于initialCapacity二的次方数 this.threshold = tableSizeFor(initialCapacity); } //构造方法2，套娃，构造方法1 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //构造方法3，无参构造方法 public HashMap() { //所有的其他参数都是默认参数 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //构造方法4 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

map-put过程形象图

put()方法

/** 作用：让key的hash的高16位也参与路由运算（[lengh-1&h]=index），扰动函数 假设 h=0b 0010 0101 1010 1100 0011 1111 0010 1110 0b 0010 0101 1010 1100 0011 1111 0010 1110 ^(异或，相同等于0，不同为一) 0b 0000 0000 0000 0000 0010 0101 1010 1100（h>>>16） => 0010 0101 1010 1100 0001 1010 1000 0010 为什么要高16位参与运算呢？ 在table长度还不是很高的情况下，让高16位也参与路由运算（[lengh-1&h]=index），使散列表更加松散，降低hash碰撞 */ static final int hash(Object key) { int h; //key=null返回0 //key1=null返回key.hashCode()) ^ (h >>> 16) return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //put方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //onlyIfAbsent=>如果散列表中已经存在某一个key,就不插入了，一般的话都是传入false，就是key有的话替换，没有的话传入一个新的 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { //tab：引用当前hashMap的散列表 Node<K,V>[] tab; //p:表示当前散列表的元素 Node<K,V> p; //n:表示散列表数组的长度 ,i:表示路由寻址的结果 int n, i; //延迟初始化逻辑，第一次调用putVal时会初始化hashMap对象中最耗费内存的散列表， //（tab = table) == null说明table=null,还没有进行初始化 if ((tab = table) == null || (n = tab.length) == 0) //resize（）创建散列表 //为什么要在put的时候创建散列表呢， //这是一个懒加载机制，比如说我们新建一个hashMap时，只是放着，不存数据， //，只有我们往里面加入数据的时候，才会新建散列表初始化，这样就节省了内存空间 n = (tab = resize()).length; // 最简单的一种情况：寻址找到的桶位，刚好是null,这个时候，直接将当前的k-v=>node 扔进去就可以离 //n在上面语句判断赋值的，(n - 1) & hash路由算法，判断散列表i位置元素==null if ((p = tab[i = (n - 1) & hash]) == null) //直接把key,value新建节点 tab[i] = newNode(hash, key, value, null); else { //e:node临时元素 //k:表示临时的一个key Node<K,V> e; K k; //p在上面语句判断赋值， //（p.hash == hash 表示桶位中的该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) //p赋值给e,现在e为一个与当前要插入的key-value一致的key的元素 e = p; //如果是红黑树的话 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //链表情况，而且链表的头元素，与我们要插入的key不一致 for (int binCount = 0; ; ++binCount) { //(e = p.next) == null条件成立说明，链表迭代到末尾最后一个元素了，也没有找到与要插入的key一致的node if ((e = p.next) == null) { //那么就将node插入到当前链表的末尾 p.next = newNode(hash, key, value, null); //触发树化操作：如果链表的长度达到树化标准了 //（TREEIFY_THRESHOLD=8，链表长度达到8，不算数组的长度就是8-1=7） if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //树化函数 treeifyBin(tab, hash); break; } //条件成立的话，说明找到了相同key的node元素，需要进行特换操作 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break; //下一次循环 p = e; } } //条件成立，说明找到一个与你插入元素key完全一直的元素，需要进行替换操作 if (e != null) { // existing mapping for key V oldValue = e.value; //onlyIfAbsent =false !onlyIfAbsent=true if (!onlyIfAbsent || oldValue == null) //把值覆写 e.value = value; afterNodeAccess(e); //返回覆盖后的值 return oldValue; } } //表示散列表结构修改的次数。替换不算 ++modCount; //插入新元素。size自增，如果自增后的值大于扩容阈值，则触发扩容 if (++size > threshold) //扩容操作 resize(); afterNodeInsertion(evict); return null; }

扩容-链表处理

resize()扩容方法

//为什么需要扩容 //为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题 final Node<K,V>[] resize() { //oldTab 引用扩容前的hash表 Node<K,V>[] oldTab = table; //oldCap ：表示扩容前table数组的长度，oldTab ==null,是第一次没有放数据时是null int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldThr :表示扩容之前的扩容阈值，触发本次扩容的阈值 int oldThr = threshold; //newCap:扩容之后的table数组的大小 //newThr:扩容之后，下次再次触发扩容的阈值 int newCap, newThr = 0; //条件如果成立：说明hashMap中的散列表已经初始化过了，这是一次正常扩容 if (oldCap > 0) { //扩容之前的table数组大小，已经达到最大阈值（1<<30），则不扩容，且设置条件为int最大值(0x7fffffff) if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //newCap = oldCap << 1:表示oldCap 左移一位赋值给newCap,左移一位就表示乘了一个2次方 //newCap < 数组最大值限制（1<<30），且扩容之前的阈值>=16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //这种情况下，则下次扩容的阈值，等于当前阈值的翻倍 newThr = oldThr << 1; // double threshold } //oldCap==0，说明hashMap 中的散列表是null(还没有初始化) //1. new HashMap(int initialCapacity, float loadFactor) //2. new HashMap(int initialCapacity) //3. new HashMap(map)并且map有数据 else if (oldThr > 0) // initial capacity was placed in threshold //把oldThr赋值给新的数组大小（oldThr是通过tableSizeFor计算出来的 所以 一定是一个二的次方数） newCap = oldThr; //oldCap==0 ，oldThr==0这个是table数组大小为0，扩容阈值也为0 //new HashMap()；//无参构造时会出现这种情况 else { // zero initial threshold signifies using defaults //默认数组大小16赋值newCap newCap = DEFAULT_INITIAL_CAPACITY; //扩容阈值等于，负载因子*默认数组大小16=12赋值给newThr newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //什么时候newThr会等于0？ //1.当你自定义的 扩容阈值<16时 //2. oldThr > 0并且oldCap==0时 if (newThr == 0) { //这种情况，就需要自己计算下次扩容阈值了 计算方法很简单 新的数组大小*负载因子 float ft = (float)newCap * loadFactor; //newCap <(1<<30) ft<(1<<30) 如果条件成立则ft转换为int,不成立择把int的最大值赋值给newThr //（其实一般都是成立的） newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //newThr赋值给扩容阈值 threshold = newThr; //创建出一个更长更大的数组newTab @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //赋值 table = newTab; //oldTab != null 说明hashMap本次扩容之前，table不为null if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //当前node节点 Node<K,V> e; //(e = oldTab[j]) != null，说明当前桶位有数据，但是数据具体是数据，还是链表，还是红黑树，并不知道 if ((e = oldTab[j]) != null) { //方便JVM GC时回收内存 oldTab[j] = null; //第一种情况：说明这个桶就一个元素，还没有生成链表， //这是直接计算出当前元素应存放在新数组中的位置，然后扔进去就可以了 if (e.next == null) //把这个e值赋值给寻址算法后的哈希表中 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表示当链表的下一个元素 Node<K,V> next; do { //赋值 next = e.next; //1.hash->.... ...1 1111 //2.hash->.... ...0 1111 //& // oldCap=16 =>ob 1 0000 //1.=============>1 //2.=============>0 //(e.hash & oldCap) == 0说明hash的高位等于0，则表示当前这个元素要放到低位链中 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置空 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; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { //tob:引用当前hashMap的散列表 Node<K,V>[] tab; //first：桶位中的头元素，e临时node元素 Node<K,V> first, e; //n:table数组的长度 int n; K k; //(tab = table) != null判断是表否有数据 //(first = tab[(n - 1) & hash]) != null判断桶中是否有数据 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //第一种情况：定位出来的桶位元素，即为咱们要get的数据 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; }

remove()方法

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //tab:引用当前hashMap中的散列表 Node<K,V>[] tab; //p:当前node元素 Node<K,V> p; //n:表示散列表数组长度 //index:表示寻址结果 int n, index; //(tab = table) != null判断是表否有数据 //(p = tab[index = (n - 1) & hash]) != null判断寻址算法找到桶位中是否有数据 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //条件成立：说明桶位中有数据，需要进行查找，删除 //node:查找的的结果 //e:当前Node 的下一个元素 Node<K,V> node = null, e; K k; V v; //第一种情况，当前桶位中的元素就是要删除的元素 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) //找到元素赋值给node node = p; else if ((e = p.next) != null) { //第二种情况：当前桶位中的元素是树结构 if (p instanceof TreeNode) //找到元素赋值给node node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //第三种情况：当前桶位中的元素是链表结构 else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { //找到元素赋值给node node = e; break; } p = e; } while ((e = e.next) != null); } } //删除逻辑，node != null，说明按照key查找到需要删除的数据 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //树结构 ：node 是树节点 if (node instanceof TreeNode) //树节点移出操作 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //数组：当前桶位的元素就是要删的元素 else if (node == p) //将改元素的下一个元素放置桶位 tab[index] = node.next; //链表结构 else //链表删除：将当前元素p的下一个元素设置成要删除的下一个元素 p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; } @Override public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null; }

replace()方法

@Override public boolean replace(K key, V oldValue, V newValue) { Node<K,V> e; V v; //e = getNode(hash(key), key)找到node节点 //(v = e.value) == oldValue 检查oldValue和找的node节点的value是否一致 if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { //如果(v = e.value) == oldValue 则进行替换 e.value = newValue; afterNodeAccess(e); return true; } return false; } @Override public V replace(K key, V value) { Node<K,V> e; //e = getNode(hash(key), key)找到node节点 if ((e = getNode(hash(key), key)) != null) { //替换操作 V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; }