HashMap

JDK1.7 和1.8中關于對HashMap的實現(xiàn)，有了一些變化，其中很重要的一個變化，就是在解決Hash沖突的時候，存儲數(shù)據(jù)結(jié)構有所調(diào)整。

1.7版本：

主要實現(xiàn)方式： 通過數(shù)組+ 鏈表的方式實現(xiàn)。當hash沖突的時候，使用鏈表來解決沖突。但是當hash不均勻的時候，可能會導致數(shù)據(jù)傾斜到某個數(shù)組槽位。那么對集合的更新、查找操作最后轉(zhuǎn)變?yōu)榫€性查找，失去了hash查找的特性。

//使用數(shù)組式的鏈表，如果key的hash值一樣，則通過List結(jié)構來解決沖突，當hash不均勻，可能會導致最后的數(shù)據(jù)變?yōu)榫€性查找List,性能無法保證transient Entry[]table;staticclassEntryimplementsMap.Entry {finalK key;? ? ? ? V value;? ? ? ? Entry next;inthash;/**其他方法**/}? ? public V put(K key, V value) {if(key ==null)returnputForNullKey(value);inthash = hash(key);inti = indexFor(hash,table.length);//當該數(shù)組的hash槽位有數(shù)據(jù)時，則通過鏈表的方式追加到鏈表的結(jié)尾for(Entry 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);returnoldValue;? ? ? ? ? ? }? ? ? ? }? ? ? ? modCount++;? ? ? ? addEntry(hash, key, value, i);returnnull;? ? }voidaddEntry(inthash, K key, V value,intbucketIndex) {if((size >= threshold) && (null!=table[bucketIndex])) {? ? ? ? ? ? resize(2*table.length);? ? ? ? ? ? hash = (null!= key) ? hash(key) :0;? ? ? ? ? ? bucketIndex = indexFor(hash,table.length);? ? ? ? }? ? ? ? createEntry(hash, key, value, bucketIndex);? ? }voidcreateEntry(inthash, K key, V value,intbucketIndex) {? ? ? ? Entry e =table[bucketIndex];table[bucketIndex] =newEntry<>(hash, key, value, e);? ? ? ? size++;? ? }

1.8 版本

在1.8的版本中，同樣是通過數(shù)組+鏈表的方式存儲結(jié)構。但是1.7的Entry 被命名為Node，并且 當Node容量到達8的時候，會將Node轉(zhuǎn)換為TreeNode(紅黑樹結(jié)構)，查找效率大大提高

/**

? ? * Basic hash bin node, used for most entries.? (See below for

? ? * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)

? ? */staticclassNodeimplementsMap.Entry{finalinthash;finalK key;? ? ? ? V value;? ? ? ? Node next;/**其他方法**/}finalVputVal(inthash, K key, V value,booleanonlyIfAbsent,booleanevict){? ? ? ? Node[] tab; Node p;intn, i;if((tab = table) ==null|| (n = tab.length) ==0)? ? ? ? ? ? n = (tab = resize()).length;//不存在，直接新建并賦值到數(shù)組對應槽位if((p = tab[i = (n -1) & hash]) ==null)? ? ? ? ? ? tab[i] = newNode(hash, key, value,null);else{? ? ? ? ? ? Node e; K k;//如果已經(jīng)有該key值，則直接返回該Nodeif(p.hash == hash &&? ? ? ? ? ? ? ? ? ? ((k = p.key) == key || (key !=null&& key.equals(k))))? ? ? ? ? ? ? ? e = p;//如果該Node 是TreeNode，則直接放入到TreeNode結(jié)構中elseif(pinstanceofTreeNode)? ? ? ? ? ? ? ? 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);//如果該槽位的值大于等于7的時候，需要轉(zhuǎn)換成TreeNode數(shù)據(jù)結(jié)構來存儲;TREEIFY_THRESHOLD等于8if(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 keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)? ? ? ? ? ? ? ? ? ? e.value = value;? ? ? ? ? ? ? ? afterNodeAccess(e);returnoldValue;? ? ? ? ? ? }? ? ? ? }? ? ? ? ++modCount;if(++size > threshold)? ? ? ? ? ? resize();? ? ? ? afterNodeInsertion(evict);returnnull;? ? }/**

? ? * 將Node數(shù)組中，對應hash槽位的Node轉(zhuǎn)換為TreeNode數(shù)據(jù)結(jié)構

? ? *

? ? * Replaces all linked nodes in bin at index for given hash unless

? ? * table is too small, in which case resizes instead.

? ? */finalvoidtreeifyBin(Node[] tab,inthash){intn, index; Node e;if(tab ==null|| (n = tab.length) < MIN_TREEIFY_CAPACITY)? ? ? ? ? ? resize();elseif((e = tab[index = (n -1) & hash]) !=null) {? ? ? ? ? ? TreeNode hd =null, tl =null;do{? ? ? ? ? ? ? ? TreeNode 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);? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 歡迎工作一到五年的Java工程師朋友們加入Java群：?741514154

群內(nèi)提供免費的Java架構學習資料（里面有高可用、高并發(fā)、高性能及分布式、Jvm性能調(diào)優(yōu)、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構資料）合理利用自己每一分每一秒的時間來學習提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰！趁年輕，使勁拼，給未來的自己一個交代！