面试必问系列：2、说一下你对Map的理解

落日映苍穹つ 2023-07-19 12:29 99阅读 0赞

思路： 先说一下map集合的特点，再说一下有哪些实现类，最后在依次讲一下每个实现类特点。

1、 Map主要用于存储键值对，根据键得到值，因此不允许键重复，但允许值重复。      **                              说出这一点  +10分    **

2、在java中的一个接口java.util.Map，它有四个实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap。  **+10分    **

3、实现类                                                                                                                                                                             **+80分   **

*   Hashmap是最常用的Map，它根据键的Hashcode值存储数据，根据键可以直接获取它的值，具有很快的访问访问速度。

<table> 
 <tbody> 
  <tr> 
   <td> <p>这里补充一下时间复杂度，</p> <p>hashmao查询分四步：<br> 1.判断key，根据key算出索引。<br> 2.根据索引获得索引位置所对应的键值对链表。<br> 3.遍历键值对链表，根据key找到对应的Entry键值对。<br> 4.拿到value。<br> 分析：<br> 以上四步要保证<strong>HashMap的时间复杂度O(1)</strong>，需要保证每一步都是O(1)，现在看起来就第三步对链表的循环的时间复杂度影响最大，链表查找的时间复杂度为O(n)，与链表长度有关。<strong>我们要保证那个链表长度为1，才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突，才能使链表长度尽可能短，理想状态为1</strong>。因此可以得出结论：HashMap的查找时间复杂度只有在最理想的情况下才会为O(1)，而要保证这个理想状态不是我们开发者控制的</p> </td> 
  </tr> 
 </tbody> 
</table>

遍历的时候，取得的数据都是随机的。只允许最多有一条记录的键为Null；HashMap不是线程安全的，也就是说，多个线程同时写hashMap可能会导致数据不一致。

<table> 
 <tbody> 
  <tr> 
   <td> <p>线程同步实现方法：</p> <p>&nbsp; 1、使用Collections.sychronizedMap方法&nbsp; &nbsp;原理&nbsp; 同步代码块</p> <p>&nbsp; 2、使用ConcurrentHashMap&nbsp; 原理&nbsp; 切分成多个桶，每个桶都是一个线程安全的Hashtable，性能更高，推荐使用。</p> </td> 
  </tr> 
 </tbody> 
</table>

*     hashTable与hashMap类似，都继承自Dictionary类，不同的是，它不允许空的键或值；但是支持线程同步，同步方式是方法上加锁sychronized，属于对象锁 ，一次只允许一个线程通过，所以写入速度会很慢。

<table> 
 <tbody> 
  <tr> 
   <td> <p>了解 锁类型详细请看</p> <p><a href="https://blog.csdn.net/zgy956645239/article/details/105218094" rel="nofollow">https://blog.csdn.net/zgy956645239/article/details/105218094</a></p> </td> 
  </tr> 
 </tbody> 
</table>

*  LinkedHashMap是hashMap的子类。 所以它的特点是 插入的时候会按照应用次数排序。遍历的时候，得到的数据是先插入的。

<table> 
 <tbody> 
  <tr> 
   <td> <p>可以尝试使用这个类写一个Redis内存淘汰算法LRU，详细请看</p> <p><a href="https://blog.csdn.net/zgy956645239/article/details/105218500" rel="nofollow">https://blog.csdn.net/zgy956645239/article/details/105218500</a></p> </td> 
  </tr> 
 </tbody> 
</table>

它的遍历速度与数据量无关，与实际数据有关。不懂的看下上面的文章。

*  TreeMap实现SortMap集合，把键按照升序排序。也可以指定比较器。使用迭代器Iterator遍历时，得到的数据是排好序的。