说说 Java 集合类:HashMap 是如何设计的? 是如何解决什么冲突的?

说说 Java 集合类:HashMap 是如何设计的? 是如何解决什么冲突的?

  1. HashMap 是基于哈希表的Map接口的非同步实现,在Java 编程语言中,最基本的结构就是两种,一个是数组,另一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造,HashMap 也不例外,HashMap 实际上是一个链表的数组的数据结构,每个元素存放链表头节点的数组,即数组和链表的结合体.HashMap 底层就是一个数组结构,数组中的每一项又是一个链表。 当新建一个 HashMap 的时候,就会初始化一个数组,Entry 就是数组中的元素,每个Map.Entry 其实是一个 key-value 对,它持有一个指向下一个元素的引用,这就构成了链表。
  2. HashMap 的存储。当我们往HashMap 中put 元素的时候,先根据key的hashCode 重新计算hash 值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置已经存放其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果该数组位置上没有元素,就直接将元素放到数组中的位置上。
  3. HashMap 的读取。从HashMap 中 get 元素时,首先计算key 的hashCode,找到数组中对应位置的某一元素,然后通过key 的equals 方法在对应位置的链表中找到需要的元素。
  4. HashMap 的 resize(rehash)。当HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap 的数组进行扩容,数组扩容这个操作也会出现在ArrayList 中,这是一个常用的操作,而在HashMap 数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。那么HashMap什么时候进行扩容呢?当 HashMap中的元素的个数超过数组大小loadFactor 时,就会进行扩容,loadFactor 的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过160.75 = 12 的时候,就把数组大小扩展为2*16 = 32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效提高 HashMap 的性能。
-------------本文结束感谢您的阅读-------------
Thank you for your encouragement