# HashMap

# 结构:数组+链表+红黑树

# 原理

HashMap是基于hashing的原理,通过put(k,v)存储对象到HashMap中,通过get(k)方式获取对象。

当使用put(k,v)传递key、value的时候,首先调用hashCode()方法,计算bucket位置来存储Node对象。

# put(k,v)过程

  1. 对key求Hash值,计算下标。
  2. 如果没有碰撞存入桶中,碰撞则放入bucket的链表或者红黑树中。
  3. 如果链表超过阈值(默认链表数超过8,总Entry数超过64)则转换为红黑树,链表长度<6则转换回链表。
  4. key结点存在则替换旧值。
  5. 如果桶满(容量*加载因子),就要resize(扩容2倍后重排)。

# get(k)过程

  1. 首先将 key hash 之后取得所定位的桶。
  2. 如果桶为空则直接返回 null 。
  3. 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是就直接返回 value。
  4. 如果第一个不匹配,则判断它的下一个是红黑树还是链表。
  5. 红黑树就按照树的查找方式返回值。不然就按照链表的方式遍历匹配返回值。

# 优化

减少碰撞。原理是如果两个不相等的对象返回不同的 hashcode 的话,那么碰撞的几率就会小些。

这就意味着存链表结构减小,这样取值的话就不会频繁调用 equal 方法,从而提高 HashMap 的性能(扰动即 Hash 方法内部的算法实现,目的是让不同对象返回不同 hashcode)。

使用不可变的、声明作 final 对象,并且采用合适的 equals() 和 hashCode() 方法,将会减少碰撞的发生。

# 多线程HashMap死循环问题

因为如果两个线程都发现 HashMap 需要重新调整大小了,它们会同时试着调整大小。 在调整大小的过程中,存储在链表中的元素的次序会反过来。 因为在resize过程中,移动到新的 bucket 位置的时候,HashMap 并不会将元素放在链表的尾部,而是放在头部,使用的是队头插入方法。 这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了,这也是导致CPU飙升的原因,所以多线程的环境下不使用 HashMap,而是使用concurrentHashMap

# LinkedHashMap

LinkedHashMap的实现就是HashMap+LinkedList的实现方式,以HashMap维护数据结构,以LinkList的方式维护数据插入顺序。 LinkedHashMap通过维护一个运行所有条目的双向链表,LinkedHashMap保证了元素的迭代顺序。迭代顺序可以是插入顺序或者是访问顺序。

# TreeMap

  • 是一个有序的key-value集合,它是通过红黑树实现的。
  • 继承于AbstractMap,所以它是一个Map,即一个key-value集合。
  • 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
  • 实现了Cloneable接口,意味着它能被克隆。
  • 实现了java.io.Serializable接口,意味着它支持序列化。
  • 基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
  • 基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。

# HashTable与HashMap的区别

  • HashTable线程安全,HashMap线程不安全。
  • HashTable不可存储null值,HashMap可以存储null值。
  • HashMap去掉了HashTable的contains⽅方法,但是加上了 containsValue()和containsKey()方法。

# ConcurrentHashMap

# 结构:HashEntry +红黑树+CAS+Synchronized

# 数据结构:Node(链表)、TreeNode(红黑树)、TreeBin(红黑树容器)

# put(k,v)流程:

  • 如果没有初始化就调用initTable()。
  • 如果hash没有冲突就直接CAS插入。
  • 如果还在进行扩容就继续扩容(多线程进行)。
  • 如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入。
  • 插入最后一个元素如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环。
  • 如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容。

# get(k)流程:

  • 计算hash值,定位到该table索引位置,如果是首节点符合就返回。
  • 如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回。
  • 以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null。