java编程之HashMap解析（基本结构和代码层方法）

HashMap基本结构

hash冲突

• 任意长度的输入通过散列算法变成固定长度的输出。好坏，是否均匀取决于hash算法，hashMap把key的hashCode异或移位得到新的hash值。不同的值hash之后可能产生相同的hashCode这就是hash冲突。

如何解决hash冲突

1. 开放定址法
   当发生冲突时，我们根据某种探测技术在散列表中形成探测序列，按照此序列逐个单元去查找，直到找到开放地址。只要散列表足够大，总能找到空地址把值存入。
2. 再hash
   多个hash函数，发生冲突换另一个，直到不冲突，虽然不易发生聚集，但增加了计算时间
3. 链地址法
   每个hash表节点都有一个next指针，冲突的的元素形成一个单链表头部挂在这个next指针上。
4. 建立公共溢出区
   将hash表分为基础表和溢出表两部分，凡是和基础表冲突的都填入溢出表。

HashMap数据结构

数组查询快，增加删除慢，链表查询慢，增加删除快。HashMap结合了两种数据结构的优势。JDK1.8以前HashMap=数组+链表。这个链表如果太大影响查询速度，甚至系统安全问题，如Dos攻击。1.8中当链表长度大于8，并且数组长度大于64的时候，转为红黑树。

代码层分析

加载因子

 /**
     * 构造器中没有指定时使用的默认值，查询时间和空间占用折中选择.DEFAULT_LOAD_FACTOR =待放入元素个数/容量
     */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /**
    *int类型32位，2的31次方，但最高位为符号位。所以是2的30次方
    */ static final int MAXIMUM_CAPACITY = 1 << 30; 

转红黑树阈值

/**
* 链表长度大于等于8转为红黑树
*/ static final int TREEIFY_THRESHOLD = 8; /**
/**
*删除之后红黑树元素个数小于6个转为链表。
*/ static final int UNTREEIFY_THRESHOLD = 6; *最小的转树容量，最小应该大于4 * TREEIFY_THRESHOLD只能是64了 *小于64的容量，就算链表长度大于8，扩容也不会转树，如果链表长度大于8才转 *红黑树 */ static final int MIN_TREEIFY_CAPACITY = 64; //链表长度binCount>=8 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //转树再判断是否大于最小转树容量，小于64，扩容代价小于转树。扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); 

hash扰动函数

static final int hash(Object key) { int h; //高16位无符号右移与原来hashCode异或，结果的高16保持不变，低16位是hashCode的高16位与低16异或。 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 

将来我们通过这个hash值与容量取模定位放置数组下标的

 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); 

由于直接做&运算比%效率高，所以这里就用hash值与2^n-1做与运算。容量选取要是2的幂。这样减1就是容量数值低位掩码。高位全为0，这样无论hash是多少，结果都是0到2的n次方-1之间。

10101001 10101010 11101011 10101010
&						   11111111
-----------------------------------
						   10101010   10进制252 

0~255之间。数组下标就有了。
hashCode是32位的int。我们数组长度肯定远远小于hash。所以每次都是hashCode的低位与运算。高位就没有参与，假如两个hashCode高位不同，低位相同。那么就大大增加了碰撞几率。所以就有了扰动函数，让高16位与低是16位异或。减小碰撞。

putVal

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */ 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为null或者长度为0，则进行初始化 if ((tab = table) == null || (n = tab.length) == 0) //获取数组容量 n = (tab = resize()).length; //hash取模运算，确定key下标，该位置为null，没有冲突，构建node放入数组 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else {//已经有值了，意味着冲突或者是值覆盖 Node<K,V> e; K k; //当前位置元素的hash值和插入的key值hash值相等并且key也相等不为null，table[i]的node替换为当前插入 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //否则就意味着冲突， else if (p instanceof TreeNode)//判断table[i]是否是树型节点，是的，就用红黑树的插入 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //不是，那就是链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {//遍历推进到链表末尾，插入新的节点，更改当前节点next指针到最新节点。 p.next = newNode(hash, key, value, null); //大于于等于8且数组长度大于64转为红黑树并 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //没有到末节点，有相同的key跳出循环，更新vlaue，执行existing mapping for key if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;//跳出很精妙，和其他一起公用相同key覆盖value代码 //把e的值赋给p和e = p.next构成循环 p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //LinkedHashMap的回调 afterNodeAccess(e); return oldValue; } } ++modCount; //超过扩容阈值。扩容 if (++size > threshold) resize(); //LinkedHashMap的回调 afterNodeInsertion(evict); return null; } 

resize扩容

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) {//大于2的30次方，把Integer最大值赋给数组扩容阈值，以后就不会再扩容了 threshold = Integer.MAX_VALUE; return oldTab; } //容量未超过最大限制，扩大2倍，小于最大容量2的30次方，并且当前数组容量大于等于16，新的扩容阈值也扩大2倍 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 //有参构造器进入的，初始容量tableSizeFor的返回值离指定数值最近的最小2的次幂this.threshold = tableSizeFor(initialCapacity) newCap = oldThr; else { // zero initial threshold signifies using defaults 这种情况是初始化HashMap时啥参数都没加。用默认16的初始容量 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 第一种：进入此“if (oldCap > 0)”中且不满足该if中的两个if，有参构造，容量小于16 // 第二种：进入这个“else if (oldThr > 0)” 第一次put的时候。 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) {//如果“oldTab != null”说明是扩容，否则直接返回newTab for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //重新散列 if ((e = oldTab[j]) != null) { //oldTab[j]元素赋值给e，解除oldTab[j]和它上面元素关系 oldTab[j] = null; if (e.next == null)//把没有冲突的节点重新hash取模，把e放到newTab上 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode)//如果e是红黑树 ((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; } 

split分割

/**
*因为扩容前后每一个元素hahs值是不变的，所以它们在新的数组中位置取决于扩容后容量。其实要么在原位置，要么是原来位置加上原来数组容量。
*扩容前128
*   10101001 10101010 11101011 10101010  扰动后的hash值
*  &						    1111111  128的低位掩码127
*  -----------------------------------
*						        0101010   10进制54
*	扩容后256
*   10101001 10101010 11101011 10101010  扰动后的hash值
*  &						   11111111  256的低位掩码255
*  -----------------------------------
*						       10101010   10进制252=54+128
*	如果hash值的10101010的最前面为0，扩容前后都是54
*/ final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { //((TreeNode<K,V>)e).split(this, newTab, j, oldCap);所以b=this就是当前红黑树bins，方法参数this指的是当前hashmap TreeNode<K,V> b = this;//当前红黑树bins // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null;//保存到原来位置的结点 TreeNode<K,V> hiHead = null, hiTail = null;//保存到新位置的节点 int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next;//记录 e.next = null; if ((e.hash & bit) == 0) {//详见注释里的位与运算如果为0证明是在原位置 //e.prev树化的时候记录这前一个节点  /*	 else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);//链表节点转树节点
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null)*/ if ((e.prev = loTail) == null)//扩容后，红黑树bin中有部分在原来位置，有部分在原位置+oldCap，所以前驱需要改变了。第一个元素到来就是头部，但后续就一定有值了。 loHead = e; else loTail.next = e;//后续节点一个个遍历取出，后记也需要改变 loTail = e; ++lc;//记录原位置上元素个数 } else {//加上oldCap位置的 if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD)//小于等于6转链表，头部放入数组 tab[index] = loHead.untreeify(map); else {//如果仍大于6 tab[index] = loHead;//头部插入数组 if (hiHead != null) // (else is already treeified)仍然树化 loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map);//头部插入数组高位 else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } 

EntrySet 遍历map

相当于ArrayList的sublist，map的视图，可以对map操作

final class EntrySet extends AbstractSet<Map.Entry<K,V>> { //map中元素个数 public final int size() { return size; } //调用HashMap的清空方法 public final void clear() { HashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } //是否包含元素 public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } //删除 public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } //遍历map public final void forEach(Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { //遍历链表 for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } } 

本文地址：https://blog.csdn.net/success112/article/details/108013087