HashMap原理分析jdk1.8


一、HashMap

1.1HashMap的实现原理:

首先有一个每个元素都是链表(jdk1.8中满足特定条件后链表转化为红黑树)的数组,当要添加一个元素(key-value)时,就首先计算元素key的hash值,然后 使用函数f(hash)=(n - 1) & hash 以此确定插入数组中的位置。但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

1.2HashMap数据结构

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //数组上容器的最大个数 static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f;//装载因子 static final int TREEIFY_THRESHOLD = 8;//树形化阈值;单个容器上链表长度>=8符合树形化条件 static final int UNTREEIFY_THRESHOLD = 6;//调整大小时,单个容器上链表长度<6取消树形态的阈值 static final int MIN_TREEIFY_CAPACITY = 64;//树形化阈值;表容量>=64符合树形化的条件 

位桶数据结构(链表数组)

transient Node<k,v>[] table;//存储(位桶)的数组</k,v> 

数组链表中链表的节点定义

static class Node<K,V> implements Map.Entry<K,V> {         final int hash;//哈希值         final K key;         V value;         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;         }     } 

红黑树数据结构

//红黑树 static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {     TreeNode<k,v> parent;  // 父节点     TreeNode<k,v> left; //左子树     TreeNode<k,v> right;//右子树     TreeNode<k,v> prev;    // needed to unlink next upon deletion     boolean red;    //颜色属性     TreeNode(int hash, K key, V val, Node<k,v> next) {         super(hash, key, val, next);     }       //返回当前节点的根节点     final TreeNode<k,v> root() {         for (TreeNode<k,v> r = this, p;;) {             if ((p = r.parent) == null)                 return r;             r = p;         }     } 

二、HashMap

2.1.put()操作

源码如下(示例):

public V put(K key, V value) {         return putVal(hash(key), key, value, false, true);     } 	 /**      * 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为空或者table的长度为0,则要进行扩容操作,初始扩容大小为16*/         if ((tab = table) == null || (n = tab.length) == 0)             n = (tab = resize()).length; 	/*如果table的在(n-1)&hash的值是空,就新建一个节点插入在该位置*/         if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null); 	/*表示有冲突,开始处理冲突*/         else {             Node<K,V> e;  	    K k; 			/*检查第一个Node,p是不是要找的值*/             if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))                 e = p;     		/*检查第一个Node,P是否是红黑树节点*/             else if (p instanceof TreeNode)                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);      		/*处理添加冲突*/             else {                 for (int binCount = 0; ; ++binCount) { 					/*指针为空就挂在后面*/                     if ((e = p.next) == null) {                         p.next = newNode(hash, key, value, null); 		       		  /*如果冲突的节点数已经达到8个,看是否需要改变冲突节点的存储结构,                          	treeifyBin首先判断当前table的长度,如果不足64,只进行resize()             	操作,扩容table。如果table长度达到64,那么将冲突的存储结构为红黑树*/             	//TREEIFY_THRESHOLD = 8                         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 = e;                 }             } 			/*就是链表上有相同的key值*/             if (e != null) { // existing mapping for key,就是key的Value存在                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null)                     e.value = value;//新值赋给当前节点                 afterNodeAccess(e);                 return oldValue;//返回存在的旧Value值             }         }         ++modCount;     	 /*如果当前大小大于门限,门限原本是初始容量*0.75*/         if (++size > threshold)             resize();//扩容两倍         afterNodeInsertion(evict);         return null;     } 

put()操作的过程
1,判断键值对数组tab[]是否为空或为null,否则以默认大小resize();
2,根据键值key计算hash值得到插入的数组索引 i,如果tab[i]==null,直接新建节点添加,否则转入3
3,判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

2.2.get()操作

代码如下(示例):

public V get(Object key) {         Node<K,V> e;         return (e = getNode(hash(key), key)) == null ? null : e.value;     } 	  /**      * Implements Map.get and related methods      *      * @param hash hash for key      * @param key the key      * @return the node, or null if none      */ 	final Node<K,V> getNode(int hash, Object key) {         Node<K,V>[] tab;//Entry对象数组 	Node<K,V> first,e; //在tab数组中经过散列的第一个位置 	int n; 	K k; 		/*找到插入的第一个Node,方法是hash值和n-1相与,tab[(n - 1) & hash]*/ 		//也就是说在一条链上的hash值相同的         if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { 			/*检查第一个Node是不是要找的Node*/             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 //判断条件是hash值要相同,key值要相同                 return first; 	 		 /*检查first后面的node*/             if ((e = first.next) != null) {             	//判断是否是红黑树节点                 if (first instanceof TreeNode)                     return ((TreeNode<K,V>)first).getTreeNode(hash, key); 					/*遍历后面的链表,找到key值和hash值都相同的Node*/                 do {                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);             }         }         return null;     } 

get()操作的过程
1.get(key)方法时获取key的hash值,计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],
2.先判断first的key是否与参数key相等
3.不等就遍历后面的链表(或红黑树结构)
4.找到相同的key值、相同的hash 值返回对应的Value值即可

2.3.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.      *      * @return the table      */     final Node<K,V>[] resize() {         Node<K,V>[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;         int oldThr = threshold;         int newCap, newThr = 0;//newCap:扩容后的链表数组容量newThr:下一次扩容的容量阈值 		 		/*如果旧表的长度不是空*/         if (oldCap > 0) {             if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             } 			/*把新表的长度设置为旧表长度的两倍,newCap=2*oldCap*/             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY) 	      		/*把新表的门限设置为旧表门限的两倍,newThr=oldThr*2*/                 newThr = oldThr << 1; // double threshold         } 		         else if (oldThr > 0) // initial capacity was placed in threshold             newCap = oldThr;                     /*如果旧表的长度的是0,就是说第一次初始化表*/         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;//把新表赋值给table         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)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 					/*如果e后边有链表,到这里表示e后面带着个单链表,需要遍历单链表,将每个结点重*/                     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;//记录下一个结点 			 			 //新表是旧表的两倍容量,实例上就把单链表拆分为两队,               //e.hash&oldCap为偶数一队,e.hash&oldCap为奇数一对               //分成两队尾插法插入                             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);                          						//lo队不为null,放在新表原位置                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;//结束后头结点挂在数组上                         }                                                  //hi队不为null,放在新表j+oldCap位置                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;//结束后头结点挂在数组上                         }                     }                 }             }         }         return newTab;     } 

总结

HashMap在jdk1.8相比1.7增加了红黑树,以增加查询效率。
HashMap原理分析jdk1.8

红黑树使用条件
如果某个桶容器中的记录过大的话(当前是TREEIFY_THRESHOLD = 8以及table表的长度大于64时),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。

扩展问题

  • HashMap中的装载因子为什么是0.75?
  • HashMap线程安全吗?
  • HashMap实现线程安全有哪些操作?
  • 这些操作中分别是怎么实现线程安全的?
  • 你知道红黑树的原理吗?

参考文章链接: https://blog.csdn.net/tuke_tuke/article/details/51588156.

版权声明:玥玥 发表于 2021-04-11 19:23:35。
转载请注明:HashMap原理分析jdk1.8 | 女黑客导航