HashMap
JDK1.7 和1.8中关于对HashMap的实现，有了一些变化，其中很重要的一个变化，就是在解决Hash冲突的时候，存储数据结构有所调整。
1.7版本：
主要实现方式： 通过数组+ 链表的方式实现。当hash冲突的时候，使用链表来解决冲突。但是当hash不均匀的时候，可能会导致数据倾斜到某个数组槽位。那么对集合的更新、查找操作最后转变为线性查找，失去了hash查找的特性。
//使用数组式的链表，如果key的hash值一样，则通过List结构来解决冲突，当hash不均匀，可能会导致最后的数据变为线性查找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);//当该数组的hash槽位有数据时，则通过链表的方式追加到链表的结尾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的版本中，同样是通过数组+链表的方式存储结构。但是1.7的Entry 被命名为Node，并且 当Node容量到达8的时候，会将Node转换为TreeNode(红黑树结构)，查找效率大大提高
/**
* 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;//不存在，直接新建并赋值到数组对应槽位if((p = tab[i = (n -1) & hash]) ==null) tab[i] = newNode(hash, key, value,null);else{ Node e; K k;//如果已经有该key值，则直接返回该Nodeif(p.hash == hash && ((k = p.key) == key || (key !=null&& key.equals(k)))) e = p;//如果该Node 是TreeNode，则直接放入到TreeNode结构中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的时候，需要转换成TreeNode数据结构来存储;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数组中，对应hash槽位的Node转换为TreeNode数据结构
*
* 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
群内提供免费的Java架构学习资料（里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料）合理利用自己每一分每一秒的时间来学习提升自己，不要再用"没有时间“来掩饰自己思想上的懒惰！趁年轻，使劲拼，给未来的自己一个交代！
网友评论