HashMap源码分析

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等多个知识点的架构资料)合理利用自己每一分每一秒的时间来学习提升自己,不要再用"没有时间“来掩饰自己思想上的懒惰!趁年轻,使劲拼,给未来的自己一个交代!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 220,809评论 6 513
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 94,189评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 167,290评论 0 359
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,399评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,425评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,116评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,710评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,629评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,155评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,261评论 3 339
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,399评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,068评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,758评论 3 332
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,252评论 0 23
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,381评论 1 271
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,747评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,402评论 2 358

推荐阅读更多精彩内容