HashMap 详解一-阿里云开发者社区

开发者社区> 云计算> 正文

HashMap 详解一

简介: 本文代码来自JDK8 实现原理 建立一个数组 根据元素哈希值计算数组索引, 保存到数组 索引号相同的元素通过链表保存 链表长度超过范围转红黑树保存 默认常量 初始长度大小: DEFAULT_INITIAL_CAPACITY = 1 << 4, 为了区分容量和元素数目, 这里就用长度表示容量 最大长.

本文代码来自JDK8

实现原理

  1. 建立一个数组
  2. 根据元素哈希值计算数组索引, 保存到数组
  3. 索引号相同的元素通过链表保存
  4. 链表长度超过范围转红黑树保存

默认常量

  • 初始长度大小: DEFAULT_INITIAL_CAPACITY = 1 << 4, 为了区分容量和元素数目, 这里就用长度表示容量
  • 最大长度大小: MAXIMUM_CAPACITY = 1 << 30
  • 默认加载因子: DEFAULT_LOAD_FACTOR = 0.75f
  • 链表转红黑树的阈值: TREEIFY_THRESHOLD = 8
  • 红黑树转链表的阈值: UNTREEIFY_THRESHOLD = 6
  • 转换红黑树要求最小数组长度: MIN_TREEIFY_CAPACITY = 64

变量

  • transient Node[] table: 保存元素的数组
  • transient int size: 元素个数, 不是数组长度
  • int threshold: 对数组扩容的阈值, 容量*加载因子
  • final float loadFactor: 加载因子, 越大填充的数据就越多, 冲突也会越多; 越小填充的数据就越少, 冲突也会减少, 为什么取 0.75 默认值就不深入讨论了

哈希值计算

// key为空, 对应哈希值为 0
// 否则将 key 的哈希值进行扰动: 高 16 位与低 16 位进行异或
// 这样做的原因是当哈希值与数组长度减一进行与运算得出索引时, 
// 对于数组长度比较小的情况, 如果没有扰动, 哈希值的高位将不参与运算, 最后的索引值很有可能会重复
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

关于 tableSizeFor 方法留到下一 part 再讲.


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章