HashMap部分源码

文档中心

HashMap部分源码

HsahMap是什么
- HashMap的扩容条件
- 哈希表的核心数据结构
- put过程
- - 计算key的hash值
- 链表转树的条件

HsahMap是什么

jdk1.8后是一个数组+链表+红黑树组成的键值对存储结构，在默认参数的情况下，链表向红黑树转换，说明哈希散列的情况很糟糕了，按照泊松分布，链表长度等于8的概率为千万分之八

HashMap的扩容条件

以下都是在默认值情况下

在数组大小小于等于64时，当链表长度等于8时，直接扩容一倍
只要达到负载因子0.75的条件也会扩容一倍

哈希表的核心数据结构

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

put过程

计算key的hash值

注意：数字的哈希值是自己的本身

//首先  h >>> 16 表示把利用key计算的hashcode值转换为二进制，并且取出高16位       // 0000 0100 1011 0011 1101 1111 1110 0001    h >>> 16   0000 0000 0000 0000 0000 0100 1011 0011   //符号^表示异或操作   相同得0，不同得1  1^1=0 0^0=0 1^0=1 0^1=1   //采用异或不采用&（与）和|（或）,因为这俩的计算结果偏向0和1，这就违背了hash值尽量不同的分散的原则   //且传参采用Object就是想让不同类型的参数有不同的hash值计算方法，让数值更分散些   //还有一点，是因为加入一个元素时，要计算位置，因为要求数组长度为2的幂次，计算位置的公式为（n-1）&hash，这个等同于n%hash，但8-1=7的二进制为111，参与与运算的只有低3位，一般参与运算的最多位低16位，而高16位相当于没用，所以这里把高16位也参与进去，在效率，速度等方面权衡下，让hash值更分散，jdk1.8把计算为止的公式放在离api里，没有单独提出来static final int hash(Object key) {    int h;    // hashmap允许key为null，但concurrentHashmap不允许键值对任何一个为空    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

HashMap部分源码
1.2获取key的value值，如果获取到值了，表明该数组节点有数据，就要做链表的连接操作，首次进来为返回null
获取key的value值片描述
2.然后判断发现hashmap表不存在，直接返回null，导致get操作也返回null 在这里插入图片描述
3.这涉及到spring的缓存ExpiringCache，这还没找到资料，待补充
获取hashmap

4.这里进行插入元素操作

/***onlyIfAbsent 表示是否需要替换put进来的值，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; if ((tab = table) == null || (n = tab.length) == 0) //这里hashmap是空的，进行扩容，首次就是初始化默认参数     n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) //计算出的数组位置为空，就会进这里，直接放一个新的node节点 /** Node(int hash, K key, V value, Node next) {     this.hash = hash;     this.key = key;     this.value = value;     this.next = next; } */     tab[i] = newNode(hash, key, value, null); else { //如果该位置的数据不为空，表示有node节点就会进这里     Node<K,V> e; K k; //这的判断就是第一个节点的的key的hash值和key是否相同，相同直接替换     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) {      if ((e = p.next) == null) {      //链表的尾插法   p.next = newNode(hash, key, value, null);   //如果链表长度>=设定的链表转树的长度-1   也就是默认7就会树话，，也就是说现在插入数据后，下一次在插入该链表就会树   化的话，就会提前树化，与扩容同一机制   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);   break;      }      //      if (e.hash == hash &&   ((k = e.key) == key || (key != null && key.equals(k))))   break;      p = e;  }     }     if (e != null) { // existing mapping for key  V oldValue = e.value;  if (!onlyIfAbsent || oldValue == null)      e.value = value;  afterNodeAccess(e);  return oldValue;     } } ++modCount; //添加完数据后，会在这进行预扩容判断，也就是当前添加完是12个数组被占用的话，那么会直接扩容，也就是说先put进入数据，然后判断是否要扩容 if (++size > threshold)     resize(); afterNodeInsertion(evict); return null;    }

链表转树的条件

链表转树的条件，数组长度大于
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 当发生链表转树这种情况,需要满足capacity必须大于64(8的四倍),
* 容量大于这个值时，表中的桶才能进行树形化
*/
static final int MIN_TREEIFY_CAPACITY = 64;

待补充红黑树转化过程中的左旋右旋

设计师网址导航

HashMap部分源码