Java面试-Map集合知识总结

Java面试-Map集合知识总结

Map有哪些类？

• TreeMap基于红黑树实现
• HashMap： JDK1.7基于哈希表实现，1.8基于数组+链表+红黑树
• HashTable和HashMap类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入HashTable并且不会导致数据不一致；它是遗留类，不应该去使用它。现在可以使用ConcurrentHashMap来支持线程安全，并且ConcurrentHashMap的效率会更高（1.7ConcurrentHashMap引入了分段锁，1.8引入红黑树）
• LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入的顺序，或者最近最少使用顺序

JDK1.7HashMap如何实现？

从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以常数时间内完成。但是在对HashMap进行迭代时，需要遍历整个table以及后面跟着的冲突链表。因此对于迭代比较多的场景，不宜将HashMap的初始大小设置过大。

有两个参数可以影响HashMap的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定可初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacityloadload_factor时，容量将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设置大可以减少重新哈希的次数。

JDK1.8的数据结构：数组+链表+红黑树

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果链表的长度>8&数组大小>=64，链表转为红黑树
• 如果红黑树的节点个数小于6个，转为链表

HashMap的put流程

• 首先进行哈希值的扰动，获取一个新的哈希值。（key==null）? 0 : （h =key.hashCode())^(h>>>16)

• 判断table是否为空或者长度为0，如果是则进行扩容操作

  if((tab=table)==null||(n=tab.length()==0){
      n=(tab=resize()).length;
  }
  

• 根据哈希值计算下标，如果对应小标正好没存数据，则直接插入即可，否者需要覆盖

• 判断tab[i]是否为树节点，否则向链表插入数据，是则向树中插入节点

• 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树

• 最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容

HashMap是怎么查找元素的？

• 使用扰动函数，获取新的哈希值
• 计算数组下标，获取节点
• 当前节点和key匹配，直接返回
• 否则，当前节点是否为树节点，查找红黑树
  的哈希值
• 计算数组下标，获取节点
• 当前节点和key匹配，直接返回
• 否则，当前节点是否为树节点，查找红黑树
• 否则，遍历链表查询