这一篇由 chenssy 发表于 2014 年 1 月,是根据 JDK1.6 的源码讲的。
2,Java 类集框架之 HashMap(JDK1.8) 源码剖析
这一篇由 push_pop 发表于 2015 年 5 月,根据 JDK1.8 讲的。
先说 1.6 的 HashMap
1.6 的 HashMap 代码较少,写的比较容易看懂。
HashMap 里存的对象是 Entry,HashMap 实际上是 Entry 数组。数组的大小是 2 的 n 次方,默认为 16,对应属性是 capacity。
HashMap 有 4 个构造函数,但其实最终调用的都是 HashMap(int initialCapacity,float loadFactor) 这个。可以看到,构造 HashMap 需要两个参数 容量 initialCapacity 和负载因子 loadFactor。
initialCapacity 这个参数并不是说 HashMap 能装多少组元素,而是 HashMap 里有多少个桶,也就是 Entry 数组的大小。它并不会总使用你设定的值,而是会取一个比 initialCapacity 大的 2 的 n 次方。
比如你设置 initialCapacity=9,实际上桶的大小会是 16。桶大小不是一成不变的,会根据 HashMap 中总元素的增加而成倍的增加。比如现在 capacity 是 16,下一次调整就是 32,再增加就是 64.
HashMap 在构造时,会设置扩容的阈值 shreshold=initialCapacity*loadFactor。
下面说常用的 put 方法。1.6 源码
- 1 public V put(K key, V value) {
- 2
- if (key == null) 3
- return putForNullKey(value);
- 4 int hash = hash(key.hashCode());
- 5 int i = indexFor(hash, table.length);
- 6
- for (Entry e = table[i]; e != null; e = e.next) {
- 7 Object k;
- 8
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- 9 V oldValue = e.value;
- 10 e.value = value;
- 11 e.recordAccess(this);
- 12
- return oldValue;
- 13
- }
- 14
- }
- 15 16 modCount++;
- 17 addEntry(hash, key, value, i);
- 18
- return null;
- 19
- }
1.6 根据 key 是否为 null,会走不同的分支,key==null 的,会单独走一个方法 putForNullKey(). null 这个 key 会固定放到 table[0]
hash 值,等于 key.hashCode 再进入一个 hash 函数算出来的值,这个 hash() 函数做了几次移位和取或运算。
indexFor() 等于用 hash 对 table 的长度取模,来得到将来放到数组的哪个位置。这里用按位与,速度比 % 要快多。
这时会有三种情况
这里有 2 点注意,
1,新建的节点,是挂在原来列表的头上,而不是末尾。这样就省得遍历到末尾了。
2,如何判断 key 相同呢?
e.hash == hash && ((k = e.key) == key || key.equals(k))
key 的 hash 值相等,且 key 的 equals 方法相等,或者根本就是一个 key(引用相同),这也是为什么一个对象要做 Key 必须要重载 hashCode() 和 equals() 方法的原因吧。
所以通过 put 返回值,可以判断 put 的是一个新 key,还是旧 key。
1.6 源码
- public V get(Object key) {
- if(key ==null)
- return getForNullKey();
- inthash = hash(key.hashCode());
- for(Entry e = table[indexFor(hash, table.length)];
- e !=null;
- e = e.next) {
- Object k;
- if(e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
如果 key==null 会单独走一个方法。
其他的 先算出 hash 值,找到对应的桶,遍历。
如果有相同的 key 就返回对应的 value ,否则返回 null。
get 比较简单。
size 属性,记录 HashMap 中有多少元素(Entry)。每次添加 Entry 时,size 都会自增 1,同时会和阈值 shreshold 比较,当 size>=shreshold 时,就是调用 resize 方法 扩容
- voidaddEntry(inthash, K key, V value,int bucketIndex) {
- Entry e = table[bucketIndex];
- table[bucketIndex] =newEntry(hash, key, value, e);
- if(size++ >= threshold)
- resize(2 * table.length);
- }
- voidresize(int newCapacity) {
- Entry[] oldTable = table;
- intoldCapacity = oldTable.length;
- if(oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- Entry[] newTable =new Entry[newCapacity];
- transfer(newTable);
- table = newTable;
- threshold = (int)(newCapacity * loadFactor);
- }
每次容量扩成之前的 2 倍
先 new 一个新数组,
再通过 transfer 方法把之前的元素都重新 hash 到新的数组中,
阈值按照新的容量重新计算。
还有删除的方法,删除也有返回值,如果返回 null,说明要删除的 key 不存在,如果不是 null,就是删除元素的 value。
可以看到 1.6 的 HashMap 采用的是数组形式,哈希值取模后就是数组的索引,所以在不冲突时,时间复杂度为 1,当冲突时,多个节点一个接一个形成一个链结构,后来者插入到链表头。
=== 分割线 =======================================
上面是 jdk1.6 的 HashMap 源代码
下面聊聊 jdk1.8 的 HashMap,这个版本的 HashMap 变化还是比较大的,整个源文件从 1000 行增加到了 2300 行(包含所有注释空行)。
第一个改变是把以前的 Entry 类 改名字 成了 Node。
Entry 和 Node 都实现了 Map.Entry 接口。 这个接口有 4 个 static 的方法,不需要实现。
在 Java8 中,接口中支持了静态方法,这个静态方法需要有 body,不需要实现。
HashMap 还是有 4 个构造函数,最主要的是 HashMap(int,float) , 1.8 中,不会在构造时就 new table 数组,而是会延迟到第一次 put 数据时。构造函数只设定了 loadFactor 和 threshold 参数,threshold 的计算方法和之前不同,它调用了一个 tableSizeFor 的方法,这个方法返回大于 initialCapacity 的 2 的 n 次幂
- /**
- * Returns a power of two size for the given target capacity.
- */
- static final inttableSizeFor(int cap) {
- intn = cap - 1;
- 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;
- }
hash 值,依然是对 key 的 hashCode 进行再 hash, 不过 hash 函数和 1.6 的又有不同。
1.8 的 put 实际上是调用 putVal 方法,这个方法多了一个 onlyIfAbsent 参数,貌似考虑在将来在 put 的时候,如果该 key 已经存在,就不覆盖了。目前这个参数还是 false,每次 put 如果 key 存在,会用新值替换旧值。
1.8 源码,putVal
- finalV putVal(inthash, K key, V value,boolean onlyIfAbsent,
- boolean evict) {
- Node[] tab; Node p; int n, i;
- if((tab = table) ==null|| (n = tab.length) == 0)
- n = (tab = resize()).length;
- if((p = tab[i = (n - 1) & hash]) ==null)
- tab[i] = newNode(hash, key, value,null);
- else {
- Node e; K k;
- if(p.hash == hash &&
- ((k = p.key) == key || (key !=null&& key.equals(k))))
- e = p;
- else if(pinstanceof TreeNode)
- e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
- else {
- for(intbinCount = 0; ; ++binCount) {
- if((e = p.next) ==null) {
- p.next = newNode(hash, key, value,null);
- if(binCount >= TREEIFY_THRESHOLD - 1)// -1 for 1st
- treeifyBin(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 keyV oldValue = e.value;
- if(!onlyIfAbsent || oldValue ==null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- if(++size > threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
1.8 的 put 比 1.6 的看起来复杂多了。代码写的更紧凑,不容易看懂,许多赋值和比较都在一个语句中写着。可能是为了执行效率吧,阅读起来体验下降。
新版的 resize 方法是一个自适应的方法,不需要参数,这个 resize 比以前复杂,有初始化 table 的任务。
没有对 key=null 去特殊处理。
情况 1,如果 table 位上没有节点,new 一个新节点挂上即可,返回 null。
情况 2,table[i] 为上有节点,且第一个节点的 key 就是本次要 put 的 key,那么用新值覆盖旧值,返回旧值。
后面就是要遍历这个位置上的挂接节点了。1.8 的这些节点有两种组织方式 ,对于 7 个一下的,还是链表的结构。对于 7 个以上的,会转化成红黑树的结构来存储。
情况 3,后面节点是树的结构。那么就调用 TreeNode 的 put 方法,有存在 key,就替换,返回旧值,不存在就新建节点,返回 null。
情况 4,后面节点是链表的结构。如果遍历这些节点,存在相同的 key,那么同情况 2,新值覆盖旧值,返回旧值。如果遍历完,没有存在 key,就新建节点,这个节点是挂在链表尾,返回 null。1.6 是挂在链表头。然后,如果链表长度大于阈值 7,那么需要将这个链表结构,转化成树的结构。
1.8 的 HashMap 新增一个内部类 TreeNode, 是继承 LinkHashMap.Entry 而来。当一个桶内的元素数量大于阈值(TREEIFY_THRESHOLD=8),会转化为树形,小于阈值(
UNTREEIFY_THRESHOLD)又会转换成链表结构。 这对于大量 hash 碰撞的情况有查找的优化,对于 hash 碰撞较小时,则不会用到 TreeNode 结构。
1.8 源码
- public V get(Object key) {
- Node e;
- return(e = getNode(hash(key), key)) ==nullnull : e.value;
- }
- finalNode getNode(int hash, Object key) {
- Node[] tab; Node first, e; int n; K k;
- 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;
- if((e = first.next) !=null) {
- if(firstinstanceof TreeNode)
- return((TreeNode)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;
- }
get 方法,如果找到了 key,则返回 value,否则,返回 null。
会根据节点结构是红黑树,还是链表用不用的方式去遍历。
put 的函数名是 putVal,而 get 的函数名是 getNode,这里不统一,有点奇怪。
删除方法,如果找到了 key,返回删除的 value,否则返回 null。
根据 node 的结构,选择在树中遍历,还是以链表的方式遍历。
1.8 源码
- finalNode removeNode(int hash, Object key, Object value,
- booleanmatchValue,boolean movable) {
- Node[] tab; Node p; intn, index;//如果桶内没元素,直接返回nullif((tab = table) !=null&& (n = tab.length) > 0 &&
- (p = tab[index = (n - 1) & hash]) !=null) {
- Node node = null, e; K k; V v;//第一个节点就找到了keyif(p.hash == hash &&
- ((k = p.key) == key || (key !=null&& key.equals(k))))
- node = p;
- else if((e = p.next) !=null) {//后面是TreeNode结构if(pinstanceof TreeNode)
- node = ((TreeNode)p).getTreeNode(hash, key);
- else{//后面是链表结构do {
- if(e.hash == hash &&
- ((k = e.key) == key ||
- (key !=null&& key.equals(k)))) {
- node = e;
- break;
- }
- p = e;
- } while((e = e.next) !=null);
- }
- }
- if(node !=null&& (!matchValue || (v = node.value) == value ||
- (value !=null&&value.equals(v)))) {//匹配到了key,根据是链表还是树,用不同方式删除。if(nodeinstanceof TreeNode)
- ((TreeNode)node).removeTreeNode(this, tab, movable);
- else if(node == p)
- tab[index] = node.next;
- else
- p.next = node.next;
- ++modCount;
- --size;
- afterNodeRemoval(node);
- return node;
- }
- }
- return null;
- }
1.8 中增加的代码主要都是因为引入了红黑树而引起的。导致许多地方都要考虑两种情况。
HashMap 碰撞有没有那么频繁呢?如果碰撞真的这么厉害,这也算是一种优化吧。
来源: http://www.cnblogs.com/fupeng/p/6803346.html