在Java8与Java7中HashMap源码实现的对比
一、hashmap的原理介绍
此乃老生常谈,不作仔细解说。
一句话概括之:hashmap是一个散列表,它存储的内容是键值对(key-value)映射。
二、java 7 中hashmap的源码分析
首先是hashmap
的构造函数代码块1中,根据初始化的capacity
与loadfactor
(加载因子)初始化hashmap
.
//代码块1 public hashmap(int initialcapacity, float loadfactor) { if (initialcapacity < 0) throw new illegalargumentexception("illegal initial capacity: " + initialcapacity); if (initialcapacity > maximum_capacity) initialcapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan(loadfactor)) throw new illegalargumentexception("illegal load factor: " +loadfactor); this.loadfactor = loadfactor; threshold = initialcapacity; init(); }
java7中对于<key1,value1>
的put
方法实现相对比较简单,首先根据 key1
的key
值计算hash
值,再根据该hash
值与table
的length
确定该key
所在的index
,如果当前位置的entry
不为null
,则在该entry
链中遍历,如果找到hash
值和key
值都相同,则将值value
覆盖,返回oldvalue
;如果当前位置的entry
为null
,则直接addentry
。
代码块2 public v put(k key, v value) { if (table == empty_table) { inflatetable(threshold); } if (key == null) return putfornullkey(value); int hash = hash(key); int i = indexfor(hash, table.length); for (entry<k,v> e = table[i]; e != null; e = e.next) { object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { v oldvalue = e.value; e.value = value; e.recordaccess(this); return oldvalue; } } modcount++; addentry(hash, key, value, i); return null; } //addentry方法中会检查当前table是否需要resize void addentry(int hash, k key, v value, int bucketindex) { if ((size >= threshold) && (null != table[bucketindex])) { resize(2 * table.length); //当前map中的size 如果大于threshole的阈值,则将resize将table的length扩大2倍。 hash = (null != key) ? hash(key) : 0; bucketindex = indexfor(hash, table.length); } createentry(hash, key, value, bucketindex); }
java7 中resize()
方法的实现比较简单,将oldtable
的长度扩展,并且将oldtable
中的entry
根据rehash
的标记重新计算hash
值和index
移动到newtable
中去。
代码如代码块3中所示,
//代码块3 --jdk7中hashmap.resize()方法 void resize(int newcapacity) { entry[] oldtable = table; int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) { threshold = integer.max_value; return; } entry[] newtable = new entry[newcapacity]; transfer(newtable, inithashseedasneeded(newcapacity)); table = newtable; threshold = (int)math.min(newcapacity * loadfactor, maximum_capacity + 1); } /** * 将当前table的entry转移到新的table中 */ void transfer(entry[] newtable, boolean rehash) { int newcapacity = newtable.length; for (entry<k,v> e : table) { while(null != e) { entry<k,v> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexfor(e.hash, newcapacity); e.next = newtable[i]; newtable[i] = e; e = next; } } }
hashmap性能的有两个参数:初始容量(initialcapacity
) 和加载因子(loadfactor
)。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash
操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
根据源码分析可以看出:在java7 中 hashmap的entry
是按照index
索引存储的,遇到hash冲突的时候采用拉链法解决冲突,将冲突的key
和value
插入到链表list
中。
然而这种解决方法会有一个缺点,假如key
值都冲突,hashmap会退化成一个链表,get
的复杂度会变成o(n)
。
在java8中为了优化该最坏情况下的性能,采用了平衡树来存放这些hash冲突的键值对,性能由此可以提升至o(logn)
。
代码块4 -- jdk8中hashmap中常量定义 static final int default_initial_capacity = 1 << 4; static final int treeify_threshold = 8; // 是否将list转换成tree的阈值 static final int untreeify_threshold = 6; // 在resize操作中,决定是否untreeify的阈值 static final int min_treeify_capacity = 64; // 决定是否转换成tree的最小容量 static final float default_load_factor = 0.75f; // default的加载因子
在java 8 hashmap的put
方法实现如代码块5所示,
代码块5 --jdk8 hashmap.put方法 public v put(k key, v value) { return putval(hash(key), key, value, false, 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) n = (tab = resize()).length; //table为空的时候,n为table的长度 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newnode(hash, key, value, null); // (n - 1) & hash 与java7中indexfor方法的实现相同,若i位置上的值为空,则新建一个node,table[i]指向该node。 else { // 若i位置上的值不为空,判断当前位置上的node p 是否与要插入的key的hash和key相同 node<k,v> e; k k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//相同则覆盖之 else if (p instanceof treenode) // 不同,且当前位置上的的node p已经是treenode的实例,则再该树上插入新的node。 e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value); else { // 在i位置上的链表中找到p.next为null的位置,bincount计算出当前链表的长度,如果继续将冲突的节点插入到该链表中,会使链表的长度大于tree化的阈值,则将链表转换成tree。 for (int bincount = 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 key v oldvalue = e.value; if (!onlyifabsent || oldvalue == null) e.value = value; afternodeaccess(e); return oldvalue; } } ++modcount; if (++size > threshold) resize(); afternodeinsertion(evict); return null; }
再看下resize
方法,由于需要考虑hash冲突解决时采用的可能是list
也可能是balance tree
的方式,因此resize
方法相比jdk7中复杂了一些,
代码块6 -- jdk8的resize方法 inal 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;//如果超过最大容量,无法再扩充table return oldtab; } else if ((newcap = oldcap << 1) < maximum_capacity && oldcap >= default_initial_capacity) newthr = oldthr << 1; // threshold门槛扩大至2倍 } else if (oldthr > 0) // initial capacity was placed in threshold newcap = oldthr; 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];// 创建容量为newcap的newtab,并将oldtab中的node迁移过来,这里需要考虑链表和tree两种情况。 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); // split方法会将树分割为lower 和upper tree两个树, 如果子树的节点数小于了untreeify_threshold阈值,则将树untreeify,将节点都存放在newtab中。 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; } if (hitail != null) { hitail.next = null; newtab[j + oldcap] = hihead; } } } } } return newtab; }
再看一下tree的treeifybin
方法和puttreeval
方法的实现,底层采用了红黑树的方法。
// 代码块7 //min_treeify_capacity 的值为64,若当前table的length不够,则resize() final void treeifybin(node<k,v>[] tab, int hash) { int n, index; node<k,v> e; if (tab == null || (n = tab.length) < min_treeify_capacity) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { treenode<k,v> hd = null, tl = null; do { treenode<k,v> p = replacementtreenode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } } // putval 的tree版本 final treenode<k,v> puttreeval(hashmap<k,v> map, node<k,v>[] tab, int h, k k, v v) { class<?> kc = null; boolean searched = false; treenode<k,v> root = (parent != null) ? root() : this; for (treenode<k,v> p = root;;) { int dir, ph; k pk; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableclassfor(k)) == null) || (dir = comparecomparables(kc, k, pk)) == 0) { if (!searched) { treenode<k,v> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tiebreakorder(k, pk); } treenode<k,v> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { node<k,v> xpn = xp.next; treenode<k,v> x = map.newtreenode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((treenode<k,v>)xpn).prev = x; moveroottofront(tab, balanceinsertion(root, x)); return null; } } }
看了这些源码,并一一做了比较之后,惊叹于源码之妙,收益良多。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。
上一篇: Android禁止横屏竖屏切换的有效方法