HashMap1.8源码分析

使用的数据机构

Node[] 链接结构 TreeNode[] 红黑树结构

  • 使用hash表(数组+链表),当链表过长时将其转成红黑树以实现O(logn)时间复杂度的查找

如何工作(put方法过程)

DEFAULT_INITIAL_CAPACITY = 16 初始化容量
MAXIMUM_CAPACITY= 1 << 30  = 1073741824 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默认填充因子(扩容因子)
TREEIFY_THRESHOLD = 8 阈值,当桶(bucket)上的链表数大于这个值时会转成红黑树,put方法的有用到
UNTREEIFY_THRESHOLD = 6 阈值,同上一个相反,当桶(bucket)上的链表数小于这个值时树转链表
MIN_TREEIFY_CAPACITY = 64 树的最小的容量,至少是 4 * TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64
Node<k,v>[] table 存储元素的数组,总是2的倍数
threshold 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
loadFactor 填充因子
<<左移运算:按二进制形式把所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。
>>右移运算:按二进制形式把所有的数字向右移动对应巍峨位数,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1.
1 << 30
0000 0000 0000 0000 0000 0000 0000 0001 -----> 0010 0000 0000 0000 0000 0000 0000 0000
在计算二进制转十进制得到 1073741824
  • 初始化数组resize(),如果Node<K,V>[] tab为空初始化长度为16的数组
  • 计算key的hashCode,并计算下标
什么是hash碰撞呢?两个输入串的hash函数的值一样,则称这两个串是一个碰撞(Collision)。
h >>> 16 避免hash碰撞(hash collisons)将高位分散到低位上,最后进行高16位与低16位^异或运算得出key的hash值
(n - 1) & hash]) 计算下标

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 如果没有碰撞直接放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  • 如果发生碰撞了以链表的方式放到后面
if (p.hash == hash &&
   ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

......
afterNodeAccess(e);
  • 如果链表长度超过阈值(TREEIFY_THRESHOLD > 8),把链表转化成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
}
  • 如果节点已经存在替换旧值
  • 如果桶满了(容量*填充因子,默认是16 x 0.75),就resize()扩容,扩容的大小是2的n次方
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;
}

冲突解决、扩容过程、原数组扩容后的位置?

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

推荐阅读更多精彩内容