Java中HashMap的put、resize方法 Java源码解析之HashMap的put、resize方法详解
weixin_46078315 人气:0一、HashMap 简介
HashMap 底层采用哈希表结构 数组加链表加红黑树实现,允许储存null键和null值
数组优点:通过数组下标可以快速实现对数组元素的访问,效率高
链表优点:插入或删除数据不需要移动元素,只需要修改节点引用效率高
二、源码分析
2.1 继承和实现
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L;
继承AbstractMap<K,V>
实现了map接口 cloneable接口和可序列化接口
2.2 属性
//hashmap默认容量为 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默认容量 16 //最大容量为2的30 1073741824 static final int MAXIMUM_CAPACITY = 1 << 30; // //默认加载因子为0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表转为红黑树的阈值 static final int TREEIFY_THRESHOLD = 8; //红黑树转为链表的阈值 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; //用于快速失败机制 在对HashMap进行迭代时,如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),直接抛出ConcurrentModificationException异常 transient int modCount; //扩容阈值,计算方法为数组容量*填充因子 int threshold; //加载因子 填充因子 final float loadFactor;
loadFactor决定数组何时进行扩容,而且为什么是0.75f
它也叫扩容因子 比如数组长度为32,所以数组扩容阈值为32*0.75=24当数组中数据个数为24时数组进行扩容,
数组容量在创建的时候就确定,扩容时重新创建一个指定容量的数组,然后讲旧数组的值复制到新数组中,扩容过程非常耗时,所以0.75时基于容量和性能之间平衡的结果。
- 如果加载因子过大,也就是扩容阈值会变大,扩容门槛高,这样容量的占用率就会降低,但哈希碰撞的几率就会增加,效率下降
- 如果加载因子过小,扩容阈值变小,扩容门槛低,容量占用变大但哈希碰撞几率下降
此外用于存储数据的table字段使用transient修饰,通过transient修饰的字段在序列化的时候将被排除在外,那么HashMap在序列化后进行反序列化时,是如何恢复数据的呢?HashMap通过自定义的readObject/writeObject方法自定义序列化和反序列化操作。这样做主要是出于以下两点考虑:
1.table一般不会存满,即容量大于实际键值对个数,序列化table未使用的部分不仅浪费时间也浪费空间;
2.key对应的类型如果没有重写hashCode方法,那么它将调用Object的hashCode方法,该方法为native方法,在不同JVM下实现可能不同;换句话说,同一个键值对在不同的JVM环境下,在table中存储的位置可能不同,那么在反序列化table操作时可能会出错。
所以在HashXXX类中(如HashTable,HashSet,LinkedHashMap等等),我们可以看到,这些类用于存储数据的字段都用transient修饰,并且都自定义了readObject/writeObject方法。readObject/writeObject方法
2.3 节点类型Node内部类
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; } }
Node包含四个字段
final int hash; final K key; V value; Node<K,V> next;//包含链表下一个节点
HashMap通过hash方法计算key的哈希值,然后通过(n-1)&hash得到key在数组中存放的下标,当两个key相同时,会以链地址法处理哈希碰撞
在链表中查找数据必须从第一个元素开始,时间复杂度为O n 所以当链表长度越来越长时HashMap的查询效率就会越来越低
所以为了解决这个问题JDK1.8实现了数组+链表+红黑树来解决 当链表长度超过8个时并且数组长度大于64
时进行树化,转化后查询时间复杂度为O(logN).
2.4 红黑树的节点
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; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); }
包含左右孩子节点和双亲结点,和前驱节点,还有节点是否时红或者黑
三、构造方法
3.1 构造器1
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
最常用的构造器。默认的填充因子 0.75f 这里的填充因子后面会讲到。
3.2 构造器2
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
给定容量构造器
3.3 构造器3
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)// 如果小于0,抛出异常 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//大于最大值 initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))//若填充因子小于0或者判断非法 throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } static final int tableSizeFor(int cap) { int n = cap - 1; 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值 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; }
给定容量和填充因子。
这里的tableSizeFor会将传进的容量值进行**大于等于
最近**二次幂处理。跟循环数组的处理方式差不多
3.4 构造器4
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
四、put
public V put(K key, V value) { //底层是调用putval return putVal(hash(key), key, value, false, true); } //这里调用了hashmap提供的hash方法,32为都参与了运算所以降低了hash碰撞的几率,这里还跟数组容量有关 //下面再讨论 static final int hash(Object key) { int h; //这里就可以看到hashmap return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
通过hash函数可以看到当key为null时,key为0,所以HashMap 是允许储存空值的。而后面的公式通过hashcode的高16位异或低1位得到的hash值,主要从性能、哈希碰撞角度考虑,减少系统开销,不会因为高位没有参与下标计算而引起的碰撞
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //请注意这里的hash是已经算过的hash(key),然后计算数组下标位置(n - 1) & hash Node<K,V>[] tab; Node<K,V> p; int n, i; //首先判断数组哈希表是否为null或者长度为0,是则进行数组初始化操作 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //这里tab指向table数组 n是数组长度 //如果该数组下标位置没有数据直接插入 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值,因为hash值判断最快,如果hash值不同就不用判断下面的 //hash不同则key一定不同,但key相同hash值是可能相同的,效率提高 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); //如果链表长度大于等于转为红黑树阈值8,则转为红黑树 //这里为什么要-1,因为数组下标从0开始 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //转为红黑树操作时,内部还会判断数组长度是否小于MIN_TREEIFY_CAPACITY 64,如果是的话不转换 treeifyBin(tab, hash); break;//退出 } //如果链表中已经存在该key,直接覆盖 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //遍历数组 e = p.next p = e; } } //e代表被覆盖的值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 如果onlyIfAbsent为false并且oldValue为null,我们便对我们的value进行保存 afterNodeAccess(e); return oldValue; } } ++modCount; //如果键值对个数大于扩容阈值,进行扩容操作 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
流程图
五、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) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //如果桶为空,size为0,目标位置是否为空,是直接返回null 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; //否则如果头节点的next有值 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; }
六、resize
数组的扩容和初始化都要靠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) { threshold = Integer.MAX_VALUE; return oldTab; } //2倍扩容不能大于最大值 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //扩容阈值/2 newThr = oldThr << 1; // double threshold } //数组中没有值,带参初始化会进入这里 //且扩容因子大于0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //不带参默认会到这里 else {//否则扩充因子 <= 0 //就是没初始化过,使用默认的初始化容量,16 * 0.75 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新容量为0,重新计算threshold扩容阈值 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; } //高位引用 直接讲原索引+oldCap放到哈希桶中 //因为是2倍扩容, 扩容后位置是原位置+增长的长度 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
七、基于JDK1.7的优化
7.1 底层实现
1.7基于数组+链表 而1.8基于链表+数组+红黑树
7.2 hash
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
效率基于1.8低
7.3 put
1.7使用的是数组加链表,解决哈希冲突采用的是链表,而且1.8采用的是尾插,而1.7采用头插
7.4 扩容
1.7在扩容时会重新计算h每个元素的hash值,按旧链表的正序遍历链表,然后在新链表的头部插入,所以会出现逆序的情况,而1.8是通过高低位映射,不会出现逆序。
加载全部内容