HashMap面试所需知识

水深无声 2022-04-11 11:30 249阅读 0赞

## 实现 ##

通过put和get存储和获取对象，存储对象时，我们将K/V传给put方法时，它调用hashcode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量。获取对象时，我们将K传递给get，他调用hashcode计算hash从而得到bucket位置，并进一步调用equals()方法确认键值对。

## HashMap的几个重要的信息： ##

默认大小为16( 2 的4次方)

扩容机制：当目前数超过总数的75%时扩展，扩展为原来的2倍，也就是2的n+1次方。

最大存2的30次方,在空间大于8的时候会变成红黑树的数据结构,当又小于6的时候又会变回链表

## List、Set、Map之间的区别? ##

List和Set都继承Collection，但是Map不是Collection的子接口。

List 可以允许重复的元素  可以插入多个null元素  有序的容器，插入的顺序和输出的顺序一样

Set 不允许重复元素  只允许一个null元素 无序容器

Map 键值对存储，键必须唯一，但是值可以重复  键只允许一个null,值可以允许有多个null   无序容器

## **HashMap集合知识:** ##

1.    关于HashMap的一些说法：

1.    HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。HashMap的底层结构是一个数组，数组中的每一项是一条链表。 
2.    HashMap的实例有俩个参数影响其性能： “初始容量” 和 装填因子。 
3.    HashMap实现不同步，线程不安全。  HashTable线程安全 
4.    HashMap中的key-value都是存储在Entry中的。
5.    HashMap可以存null键和null值，不保证元素的顺序恒久不变，它的底层使用的是数组和链表，通过hashCode()方法和equals方法保证键的唯一性
6.    解决冲突主要有三种方法：定址法，拉链法，再散列法。HashMap是采用拉链法解决哈希冲突的。 注： 链表法是将相同hash值的对象组成一个链表放在hash值对应的槽位；    用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。 沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。

**拉链法解决冲突的做法是： 将所有关键字为同义词的结点链接在同一个单链表中 。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T\[0..m-1\]。凡是散列地址为i的结点，均插入到以T\[i\]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。拉链法适合未规定元素的大小。**

## Hashtable和HashMap的区别：  ##

**a)   继承不同。  public class Hashtable extends Dictionary implements Map **

**public class HashMap extends  AbstractMap implements Map .**

**b)  Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。**

** c)  Hashtable 中， key 和 value 都不允许出现 null 值。 在 HashMap 中， null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null 。当 get() 方法返回 null 值时，即可以表示 HashMap 中没有该键，也可以表示该键所对应的值为 null 。因此，在 HashMap 中不能由 get() 方法来判断 HashMap 中是否存在某个键， 而应该用 containsKey() 方法来判断。 **

**d)  两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。 **

**e)  哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。 **

**f)  Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是old\*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。   注：  HashSet子类依靠hashCode()和equal()方法来区分重复元素。      HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值的,会去判断当前Map中是否含有该Key对象，内部是先通过key的hashCode,确定有相同的hashCode之后，再通过equals方法判断是否相同。 **

## 如果两个键的hashcode相同，你如何获取值对象？ ##

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。如果有两个值对象储存在同一个bucket，将会遍历LinkedList直到找到值对象。找到bucket位置之后，会调用keys.equals()方法去找到LinkedList中正确的节点，最终找到要找的值对象。(当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。)

在多线程的情况下，当重新调整HashMap大小的时候，就会存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历。如果条件竞争发生了，那么就会产生死循环了。

内容选自:https://blog.csdn.net/mbshqqb/article/details/79799009

https://blog.csdn.net/brycegao321/article/details/52527236