HashMap底层原理及相关知识点

前言

HashMap应该算是面试中出现频率非常高的知识点了,之前对这个了解甚少,所以专门系统的学习了一下,下面将各知识点和自己的理解一起整理,便于以后复习~

HashMap相关知识

1、什么是HashMap?

哈希表,也称散列表,是一种通过key值来直接访问在内存中的存储的数据结构。 HashMap是基于哈希表的Map接口实现的,它存储的是内容是键值对映射。

2、HashMap特性?

  • HashMap存储键值对,实现快速存取数据;
  • 允许null键/值;
  • 非同步;
  • 不保证有序(比如插入的顺序)。
  • 实现map接口。

3、HashMap在JDK1.8以前的存储原理和内部数据结构?

1)链表散列

什么是链表散列?通过数组和链表结合在一起使用,就叫做链表散列。这其实就是hashmap存储的原理图。

散列表

2)HashMap的数据结构和存储原理

HashMap的数据结构就是用的链表散列。那HashMap底层是怎么样使用这个数据结构进行数据存取的呢?分成两个部分:

第一步:HashMap内部有一个entry的内部类,其中有四个属性,我们要存储一个值,则需要一个key和一个value,存到map中就会先将key和value保存在这个Entry类创建的对象中。

1
2
3
4
5
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //就是我们说的map的key
V value; //value值
Entry<K,V> next;//指向下一个entry对象
int hash;//通过key算过来的你hashcode值。

第二步:构造好了entry对象,然后将该对象放入数组中。

大概的一个存放过程是:通过entry对象中的hash值来确定将该对象存放在数组中的哪个位置上,如果在这个位置上还有其他元素,则通过链表来存储这个元素。

hashmap

3)Hash存放元素的过程

通过key、value封装成一个entry对象,然后通过key的值来计算该entry的hash值,通过entry的hash值和数组的长度length来计算出entry放在数组中的哪个位置上面,

每次存放都是将entry放在第一个位置。在这个过程中,就是通过hash值来确定将该对象存放在数组中的哪个位置上。

4、HashMap在JDK1.8以前的存储原理和内部数据结构?

bucket

上图很形象的展示了HashMap的数据结构(数组+链表+红黑树),桶中的结构可能是链表,也可能是红黑树,红黑树的引入是为了提高效率。

5、HashMap 中 put 方法过程

  1. 对key的hashCode做hash操作,然后再计算在bucket中的index;
  2. 如果没碰撞直接放到bucket里;
  3. 如果碰撞了,以链表的形式存在buckets后;
  4. 如果节点已经存在就替换old value(保证key的唯一性)
  5. 如果bucket满了(超过阈值,阈值=loadfactor*current capacity,load factor默认0.75),就要resize。

6、get()方法的工作原理

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表中查找对应的节点。

7、HashMap中hash函数怎么是是实现的?还有哪些 hash 的实现方式?

  • 直接定址法:取关键字key的某个线性函数为散列地址,如Hash(key) = key 或 Hash(key) = A*key+B;A,B为常数
  • 除留取余法:关键值除以比散列表长度小的素数所得的余数作为散列地址。Hash(key) = key % p;
  • 平均取中法:先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。
  • 折叠法:把关键码自左到右分为位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。把这些部分的数据叠加起来,就可以得到具有关键码的记录的散列地址。分为移位法和分界法。
  • 随机数法:选择一个随机函数,取关键字的随机函数作为它的哈希地址。
  • 数学分析法:设有N个d位数,每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布均匀些,每种符号出现的机会均等;在某些位上分布不均匀,只有某几种符号经常出现。可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。

8、遇到哈希冲突/哈希碰撞 我们该如何处理呢?

  • 线性探测:当不同的key值通过哈希函数映射到同一散列地址上时,检测当前地址的下一个地址是否可以插入,如果可以的话,就存在当前位置的下一个地址,否则,继续向下一个地址寻找,地址++。
  • 二次探测:是针对线性探测的一个改进,线性探测后插入的key值太集中,这样造成key值通过散列函数后还是无法正确的映射到地址上,太集中也会造成查找、删除时的效率低下。因此,通过二次探测的方法,取当前地址加上i^2,可以取到的新的地址就会稍微分散开。
  • 处理哈希冲突的开链法(哈希桶):当用线性探测和二次探测时,总是在一个有限的哈希表中存储数据,当数据特别多时,效率就比较低。因此采用拉链法的方式来降低哈希冲突。

9、HashMap的属性

1)loadFactor加载因子

  • 定义:loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为:size/capacity,而不是占用桶的数量去除以capacity。

  • loadFactor加载因子是控制数组存放数据的疏密程度,loadFactor越趋近于1,那么数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor越小,也就是趋近于0,那么数组中存放的数据也就越稀,也就是可能数组中每个位置上就放一个元素。那有人说,就把loadFactor变为1最好吗,存的数据很多,但是这样会有一个问题,就是我们在通过key拿到我们的value时,是先通过key的hashcode值,找到对应数组中的位置,如果该位置中有很多元素,则需要通过equals来依次比较链表中的元素,拿到我们的value值,这样花费的性能就很高,如果能让数组上的每个位置尽量只有一个元素最好,我们就能直接得到value值了,所以有人又会说,那把loadFactor变得很小不就好了,但是如果变得太小,在数组中的位置就会太稀,也就是分散的太开,浪费很多空间,这样也不好,所以在hashMap中loadFactor的初始值就是0.75,一般情况下不需要更改它。

2)桶

根据前面画的HashMap存储的数据结构图,数组中每一个位置上都放有一个桶,每个桶里就是装一个链表,链表中可以有很多个元素(entry),这就是桶的意思。也就相当于把元素都放在桶中。

3)capacity

capacity译为容量代表的数组的容量,也就是数组的长度,同时也是HashMap中桶的个数。默认值是16。一般第一次扩容时会扩容到64,之后好像是2倍。总之,容量都是2的幂。

4)size的含义

size就是在该HashMap的实例中实际存储的元素的个数

5)threshold的作用

threshold = capacity * loadFactor,当Size>=threshold的时候,那么就要考虑对数组的扩增了,也就是说,这个的意思就是衡量数组是否需要扩增的一个标准。

10、hashCode与equals的作用与区别

在Java中任何一个对象都具备equals(Object obj)和hashCode()这两个方法,因为他们是在Object类中定义的。 equals(Object obj)方法用来判断两个对象是否“相同”,如果“相同”则返回true,否则返回false。 hashCode()方法返回一个int数,在Object类中的默认实现是“将该对象的内部地址转换成一个整数返回”。

  • hashCode是为了提高在散列结构存储中查找的效率,在线性表中没有作用。
  • equals和hashCode需要同时覆盖。
  • 若两个对象equals返回true,则hashCode有必要也返回相同的int数。
  • 若两个对象equals返回false,则hashCode不一定返回不同的int数,但为不相等的对象生成不同hashCode值可以提高哈希表的性能。
  • 若两个对象hashCode返回相同int数,则equals不一定返回true。
  • 若两个对象hashCode返回不同int数,则equals一定返回false。
  • 同一对象在执行期间若已经存储在集合中,则不能修改影响hashCode值的相关信息,否则会导致内存泄露问题。
您的支持将鼓励我继续创作~