HashMap知识点总结

蔚落 2022-05-28 13:28 138阅读 0赞

# **HashMap集合知识点总结** #

**1.HashMap的原理，内部数据结构？**

**答：**底层数据结构为哈希表（数组\+链表），当链表过长会将链表转成红黑树以实现O（logN）时间复杂度内查找。

**2.讲一下HashMap中put方法的过程？**

**答：**（1）调key的hashCode()方法计算key的哈希值，然后根据映射关系计算数组下标

（2）如果hash值冲突，调用equal()方法进一步判断key是否已存在

若key已存在，覆盖key对应的value值

若key不存在，将结点链接到链表中，若链表长度超过阈值（TREEIFY\_THRESHOLD == 8），就把链表转成红黑树

（3）如果hash值不冲突，直接放入数组中，若数据量超过**容量\*负载因子**，需要对原数组进行扩容，每次扩容2倍

**3.抛开HashMap，hash冲突有哪些解决方法？**

**答：**链地址法、开发地址法、再hash法等。

**4.针对HashMap中某个Entry链太长，查找时间复杂度可能达到O（n），怎么优化？**

**答：**将链表转为红黑树。JDK1.8已经实现。

**5.HashMap怎样解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是怎么定位到这个值新数组中的位置。**

**答：**HashMap解决hash冲突的方法是链地址法，用链表存储hash值相同的元素。

当数据量超过HashMap数组容量的负载因子（默认0.75）之后，就会进行扩容，每次扩容2倍，扩容后会对每个结点重新计算哈希值

这个值可能在两个地方，一个是在原下标的位置，另一个是在下标为<原下标+原容量>的位置。

Map是用来存储键值对的数据结构，在数组中通过数组下标来对其内容索引的，而在Map中，则是通过对象来进行索引的，用来索引的对象叫做key，其对应的对象叫value。

**1. HashMap和Hashtable的区别？**

**答：**Hashtable是线程安全的，效率低，不允许null键null值，Hashtable的hash数组默认大小是11，增加的方式是old\*2+1。

HashMap是Hashtable的轻量级实现，是线程不安全的，效率高，允许null键null值，HashMap的hash数组默认大小是16，增加的方式是old\*2。

**2. 在Hashtable上下文中，同步指的是什么？**

**答：**同步意味着在一个时间点只能有一个线程可以修改hash表，任何线程在执行Hashtable的更新操作前都需要获取对象锁，其它线程则等待锁的释放。

**3. 如何实现HashMap的同步？**

**答：**HashMap可以通过Map m = Collections.synchronizedMap(new HashMap())来达到同步的效果。具体而言，该方法返回一个同步的Map，该Map封装了底层的HashMap的所有方法。

**4. HashMap里面存入的键值对在取出时是有序的还是无序的？**

**答：**无序的。

**5. HashMap中键不可以重复，值可以重复，如果我存入了一个已经存在的键，会怎么样呢？**

**答：**会用该键对应的新值替换掉该键对应的老值，并返回老值。

**6.我们怎样去创建一个Map集合呢？**

**答：**Map<String,String> map = new HashMap<String,String>();

**7.在操作Map集合时，你经常会用到哪几个方法：**

**答：**put(K key,V value):添加元素

get(Object key):根据键获取值

remove(Object key)：根据键删除键值对元素，并把值返回

containsKey(Object key)：判断集合是否包含指定的键

**8.创建一个Map集合，往里面存<String,String>，并将所存数据遍历出来。**

**答：**

<table> 
 <tbody> 
 <tr> 
 <td>public static void main(String[] args) { //&nbsp;创建集合对象HashMap&lt;String, String&gt; hm = new HashMap&lt;String, String&gt;();&nbsp;//&nbsp;创建元素并添加元素hm.put("it001", "马云");hm.put("it003", "马化腾");hm.put("it004", "乔布斯");hm.put("it005", "张朝阳");hm.put("it002", "裘伯君"); // wpshm.put("it001", "比尔盖茨");&nbsp;//&nbsp;遍历Set&lt;String&gt; set = hm.keySet();for (String key : set) { String value = hm.get(key);System.out.println(key + "---" + value);}}</td> 
 </tr> 
 </tbody> 
</table>

**9. HashMap中的键是用什么存储的？**

**答：**是用set集合存储的。

**10. HashMap中的值是用什么存储的？**

**答：**是用Collection集合存储的。

**11. HashMap中的链表中存放的是什么？**

**答：**是哈希地址冲突的不同记录。

**12. HashMap的数组中存放的是什么？**

**答：**是链表的头结点。

**13. HashMap中，定义了一个哈希数组table，它的类型是什么？**

**答：**Entry\[\]。

**14. HashMap中采用什么方法来解决哈希值冲突的问题？**

**答：**链地址法。

**15. HashMap的负载因子默认值是多少？**

**答：**0.75。

**16. HashMap的底层用到了哪两种数据结构？它们分别用来做什么？**

**答：**分别是数组和链表。数组的索引就是对应的哈希地址，存放的是链表的头结点即插入链表中的最后一个元素，链表存放的是哈希地址冲突的不同记录。

**17. 为什么String，Integer这样的wrapper类适合作为HashMap集合的键？**

**答：**因为String和Integer这样的wrapper类是final类型的，具有不可变性，并且已经重写了equals()方法和hashCode()方法。

**18. HashMap中添加元素的操作过程是怎样的呢？（put方法的执行流程）**

**答：**首先，调用key的hashCode()方法生成一个hash值h1，如果这个h1在HashMap中不存在，那么直接将<key,value>添加到HashMap中；如果这个h1已经存在，那么找出HashMap中所有hash值为h1的key，然后分别调用key的equals()方法判断当前添加的key值是否与已经存在的key值相同。如果equals()方法返回true，说明当前需要添加的key已经存在，那么HashMap会使用新的value值来覆盖掉旧的value值；如果equals()方法返回false，说明新增加的key在HashMap中不存在，因此就会在HashMap中创建新的映射关系。

**19. HashMap中获取元素的操作过程是怎样的呢？（get方法的执行流程）**

**答：**从HashMap中通过key查找value时，首先调用的是key的hashCode()方法来获取到key对应的hash值，这样就可以确定键为key的所有值存储的首地址，如果h对应的key值有多个，那么程序接着会遍历所有key，通过调用key的equals()方法来判断key的内容是否相等。只有当equals()方法的返回值为true时，对应的value才是正确的结果。

**20. 在使用自定义类作为HashMap的key时，明明向HashMap中添加的两个键值对的key值是相同的，可是为什么在后面添加的键值对没有覆盖前面的value呢？**

**答：**由于使用自定义的类作为HashMap的key，而没有重写hashCode()方法和equals()方法，默认使用的是Object类的hashCode()方法和equals()方法。Object类的equals()方法的比较规则如下：当参数obj引用的对象与当前对象为同一对象时，就返回true，否则返回false。hashCode()方法会返回对象存储的内存地址。由于在上例中创建了两个对象，虽然它们拥有相同的内容，但是存储在内存中不同的地址，因此在向HashMap中添加对象时，调用equals()方法的返回值为false，HashMap会认为它们是两个不同的对象，就会分别创建不同的映射关系。因此，为了实现在向HashMap中添加键值对，可以根据对象的内容来判断两个对象是否相等，这就需要重写hashCode()方法和equals()方法。

**21. 两个对象相等，那么这两个对象有着相同的hashCode，反之则不成立。**

**22. HashMap的原理是什么呢？**

**答：**HashMap的实现采用了除留余数法形式的哈希函数和链地址法解决哈希地址冲突的方案。这样就涉及到两种基本的数据结构：数组和链表。数组的索引就是对应的哈希地址。存放的是链表的头结点即插入链表中的最后一个元素，链表存放的是哈希地址冲突的不同记录。

**23. HashMap是如何解决添加元素时哈希值冲突问题的？**

**答：**当哈希地址冲突时，HashMap采用了链地址法的解决方式，将所有哈希地址冲突的记录存储在同一个线性链表中。具体来说就是根据hash值得到这个元素在数组中的位置（即下标）。如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。

**24. 如果HashMap的大小超过了负载因子（load factor）定义的容量，怎么办？**

**答：**HashMap默认的负载因子大小为0.75，也就是说，当一个map填满了75%的空间的时候，将会创建原来HashMap大小的两倍的数组，来重新调整map的大小，并将原来的对象放入新的数组中。