首页 / JAVA / 【Java】HashMap源码分析——基本概念

【Java】HashMap源码分析——基本概念

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Java】HashMap源码分析——基本概念，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3847字，纯文字阅读大概需要6分钟。

内容图文

在JDK1.8后，对HashMap源码进行了更改，引入了红黑树。
在这之前，HashMap实际上就是就是数组+链表的结构，由于HashMap是一张哈希表，其会产生哈希冲突，为了解决哈希冲突，HashMap采用了开链法，即对于用对象hashCode值计算哈希表数组下表时，当出现相同情况时，会在相同的地方追加形成链表的形式。对于分布均匀的情况下，仅仅是一个一维数组，查询时时间复杂度为O(1)，当分布不均匀的时候，在有的地方会形成链表，极端情况下完全退化成一个链表，查询时就需要遍历整个链表，时间复杂度就为O(n)，极为耗时。
在引入红黑树后，当满足一定条件时，链表就会转换成一棵红黑树。红黑树是一种AVL树(自平衡查找二叉树)，相比于链表，其查找时的时间复杂度还是很优秀的(O(logn))！

先了解一下HashMap的模型：

【Java】HashMap源码分析——基本概念 - 文章图片

其中的Node结点存放我们的键值对<K, V>;
首先，我们先了解HashMap给出的几个重要指标：

1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 默认的初始化容量大小为16
2 static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量1G
3 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子值0.75，用于扩容时的计算
4 static final int TREEIFY_THRESHOLD = 8; // 树的阈值，当链表长度大于等于8时，由链表转换成红黑树
5 static final int UNTREEIFY_THRESHOLD = 6; // 链表的阈值，暂时不清楚
6 static final int MIN_TREEIFY_CAPACITY = 64; // 最小树容量64

以上就是几个基本指标，其规定了在以后操作中的界限！
其中Node<K, V>是一个内部类，封装了这个结点的所有信息，有如下几个成员

1 final int hash;   
2 final K key;      
3 V value;       
4 Node<K,V> next;

key和value不必多说，其中的hash是利用key对象的hashCode计算得到的，具有唯一性：

1  static final int hash(Object key) {
2         int h;
3         // 可以看到hash是根据对象的hashCode值来计算
4         // hashCode是一个int值，有32位
5         // 最后改变的是其低16位
6         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
7  }

其中的next就是为了解决哈希冲突，当产生哈希冲突时，next就可以指向一张链表，或者一棵黑树！

 

接下来是几个重要的成员：

1  transient Node<K,V>[] table; // 这就是真正的HashMap，一张哈希表，实际上就是由Node结点组成的一维数组
2  transient int size; // 记录table中真正有效的结点个数，也就是键值对的个数
3  int threshold;  // 用来记录当前容量下，最适合存放多少键值对(容量*负载因子)
4  final float loadFactor; // 负载因子，若在构造方法没有特别设置，都是默认0.75
5  transient int modCount;  // 用来记录操作数

看到这，我们先不急着往下进行，先仔细分析下这些成员之间的关系：
table：真正开辟的空间，其length就是真正的容量大小
size: 真正使用的空间，总的键值对的个数
threshold:这个就比较有意思，其决定了是否需要进行扩容的操作，是一个阈值！
比如说，在初始化时，默认的容量是16，那么table的length就是16，其threshold=容量×负载因子=16×0.75=12，这就代表着，当size大于12时，就会进行扩容（容量会×2，threshold会根据新容量重新计算）的操作！
这样做的目的很明确，就是为了减少哈希冲突！有效元素的个数少于哈希表的总大小时，其产生哈希冲突的可能性一定是小于相等情况的！
综上可知，在非极限情况下（容量=threshold=MAXIMUM_CAPACITY=2^30）时，threshold总是小于容量，size总是不大于threshold！
这一切的做法，都是为了能够减少哈希冲突产生的可能性！


说到这里还是不能往下进行，我们需要知道Node中的hash成员是如何与table中的下标产生对应关系的，以及哈希冲突是如何产生的：

首先是关于hash值和table下标的映射：

1 index =   hash  & (table.length - 1)

这是一个非常巧妙的运算，当table.length满足二的整数幂时，就满足：
hash & (table.length - 1) == hash % table.length
例如：2%8 = 2 即：
0000 0010 2
&
0000 0111 （8 - 1）
0000 0010
二的整数幂减一得到的二进制数，其有效位全是1，通过&可以直接得到符合条件的有效位的值！
其实就是取余，用余数作为table的下标，而位运算的速度是比其余快的多，所以采用了这种方式！
所以这就是为什么table的大小必须是二的整数幂，以及扩容时都是乘2！

哈希冲突的产生：
以初始table.length = 16为例
对于hash = 1， 和 hash = 17来说，其对于16取余的结果都是1，那么这两个不同的hash值对应了同一个table的下标，这就产生了哈希冲突！

先将HashMap简单介绍到这，后续我会继续分析HashMap，若有错误或不足之处，还请指出！

 

我在CSDN也放了一篇【Java】HashMap源码分析——基本概念

内容总结

以上是互联网集市为您收集整理的【Java】HashMap源码分析——基本概念全部内容，希望文章能够帮你解决【Java】HashMap源码分析——基本概念所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/852630.html

来源：【匿名】