前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap 底层是怎么样的

HashMap 底层是怎么样的

作者头像
happyJared
发布2019-06-16 13:07:15
1.8K0
发布2019-06-16 13:07:15
举报
文章被收录于专栏:happyJared
JDK1.8 之前

JDK1.8 前,HashMap 底层是 数组+链表,也就是 链表散列。 HashMap 通过 key 先计算 hashCode,再经过 扰动函数 处理后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(n 指的是数组长度);如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同;如果相同,直接覆盖;如果不同,就通过 拉链法 解决冲突。

扰动函数:指的是 HashMap 的 hash 方法,扰动函数是为了减少碰撞,防止一些实现比较差的 hashCode() 方法

JDK1.8 的 hash() 方法 相比于 JDK1.7 hash() 方法更加简化,但是原理不变。

JDK1.8 HashMap 的 hash() 方法源码:

代码语言:javascript
复制
  static final int hash(Object key) {
      int h;
      // key.hashCode():返回散列值也就是hashcode
      // ^ :按位异或
      // >>>:无符号右移,忽略符号位,空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比 JDK1.7 的 HashMap 的 hash() 方法源码:

代码语言:javascript
复制
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

两者的区别:JDK1.7 的 hash() 方法性能会稍差些,毕竟扰动动作做了 4 次。

拉链法: 是将链表与数组相结合,也就是创建一个链表数组,数组的每一格就是一个链表,若遇到哈希冲突,则将冲突的值加到链表中。

链表数组

JDK1.8 之后

相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,链表将转化为红黑树,以减少搜索时间。

JDK1.8 之后的 HashMap 底层数据结构

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树,就是为了解决二叉查找树的在某些情况下,会退化成线性结构的缺陷。推荐阅读: 《Java 8系列之重新认识HashMap》

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.06.15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • JDK1.8 之前
  • JDK1.8 之后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档