本文旨在探究HashMap的源码设计思路,仅供学习交流之用.
1.问:在JDK1.8中,HashMap的继承与实现的关系如何?
答:
源码如下:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ...
HashMap继承了AbstractMap,实现了Map,Cloneable, Serializable。
利用IDEA的yFiles得效果图如下:
2.问:接第一问,为何这么设计
答: 首先关于AbstractMap,其实现了Map接口,继承此abstract类可以避免重复造轮子,提高代码的重用率;其次关于Cloneable,查看它的源码后可以发现其并没有声明任何的方法,实现 Cloneable是来表示该对象能被克隆,能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException;最后关于Serializable,与Cloneable类似,内部也没有方法,实现Serializable也是为了确保HashMap类本身能够实现序列化。
1.描述 DEFAULT_INITIAL_CAPACITY
答:
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap的初始容量,左移4位即是1*2^4 = 16,
那为什么要设置为16,可以初始化是指定么?
其实是可以的,并且是推荐的 [阿里巴巴开发手册]:
具体见 HashMap容量为什么设置初始值为16
2.描述 MAXIMUM_CAPACITY
答:
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap的最大容量,如需指定,必须为2的n次幂,且小于初始的2^30
3.描述 DEFAULT_LOAD_FACTOR
答:默认的负载因子, 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容,扩容为原来的两倍。
至于为什么设置为0.75,是因为负载因子太小了浪费空间并且会发生更多次数的resize,太大了哈希冲突增加会导致性能不好,所以0.75只是一个折中的选择,和泊松分布没有什么关系,本质上就是trade off–(权衡之后的折中方案)。具体见
HashMap defaultLoadFactor = 0.75和泊松分布没有关系.
为什么每次扩容都是原来的两倍?
JDK8因为巧妙的设计,性能有了大大的提升:由于数组的容量是以2的幂次方扩容的,那么一个Entity在扩容时,新的位置要么在原位置,要么在原长度+原位置的位置。原因如下图:
数组长度变为原来的2倍,表现在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过hash转换坐标的方法计算后,恰好出现一个现象:最高位是0则坐标不变,最高位是1则坐标变为“10000+原坐标”,即“原长度+原坐标”。如下图:
详见HashMap的扩容机制
4.描述 TREEIFY_THRESHOLD
答:
/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8;
TREEIFY,即树形化。TREEIFY_THRESHOLD,表树化域值: 默认值为 8 。表示在一个node(Table)节点下的值的个数大于8(链表的长度大于8)时候,会将链表转换成为红黑树。
那为什么是8呢?
首先需要明确的是treeify不是一个廉价的操作,因此需要避免频繁的树形化,其次,链表太长也会影响查找效率,所以我们需要找到一个合适的值。
TREEIFY_THRESHOLD的寻找过程和泊松分布有关。记住结论:8个键值对同时存在于同一个桶(bin)的概率只有 0.00000006,具体见源码中的如下片段
/* Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million * /
因此认为8是一个比较合理的值
5.描述 UNTREEIFY_THRESHOLD
答:
/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6;
桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容(resize())时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表
6.描述 MIN_TREEIFY_CAPACITY
答:
/** * 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. */ static final int MIN_TREEIFY_CAPACITY = 64;
最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树)
否则,若桶内元素太多时,则直接扩容,而不是树形化
为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
1.初始化容量和负载因子,原16和0.75
public HashMap(int initialCapacity, float loadFactor)
2.仅初始化容量
public HashMap(int initialCapacity)
3.无参构造函数
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
4.指定K,V类型
public HashMap(Map<? extends K, ? extends V> m)
方法名 | 返回值 | 作用 |
---|---|---|
put(k,v) | void | 插入一个k,v键值对 |
get(k) | v | 提供k,计算hash值后获取v或返回空 |
entrySet() | Set<Map.Entry<K,V>> | 返回entrySet的存储值 |
containsKey(k) | boolean | 是否含有k |
keySet() | Set < k > | 返回ket的集合 |
clear() | void | 清空hashmap |
containsValue(v) | boolean | 是否含有value |
isEmpty() | boolean | 是否为空 |
size() | int | 容量 |
values() | Collection | 返回v的集合(不会去重!) |
clone | Object | 浅拷贝 |
compute(K key, BiFunction remappingFunction) | V | 对 hashMap 中指定 key 的值进行重新计算 |
computeIfAbsent(K key, BiFunction remappingFunction) | V | 如果k不存在就重新计算,如果存在就当无事发生 |
computeIfPresent(K key, BiFunction remappingFunction) | k | 对 hashMap 中指定 key 的值进行重新计算,前提是该 key 存在于 hashMap 中。 |
putAll(Map<? extends K, ? extends V> m) | void | 将所有键/值对添加到 hashMap 中(将一个hashmap中的值填入本map中,重复的key会被忽略而不是覆盖) |
merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) | V | 1.key不存在,则插入新值。2.key存在,value不存在,则插入指定的value.3.value如果存在,则返回经过计算后的值 |