Map

java 8 HashMap

结构

数组+链表/红黑树。成员变量table是一个Node数组，Node类实现了Map.Entry接口，包含key和value。Node类本身包含一个next指针，是一个链表实现；Node类还有一个子类TreeNode，包含left、right和pre指针以及boolean类型的是否为红色的red变量，是一个红黑树实现。

几个变量

  • int threshold 阈值，初试容量默认是16，阈值为容量乘以附在因子
  • final float loadFactor 负载因子，默认0.75
  • transient int modCount 被修改的次数，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException*/
  • transient Node[] table 存放key-value的结构（在1.7中Node的名字叫Entry）

put操作

  • 计算hash值（取hashCode,将hashCode与hashCode无符号右移16位的值取异或）
  • 如果table数组为空就进行一次扩容
  • 使用数组长度建议与hash值取与得到数组下标，如果该位置上是空，就新建一个Node赋值给该下标

    • 如果这个Node的key==当前要插入的key，就讲这个Node的value属性设置为要设置的值；
    • 如果这个Node的类型为TreeNode，那么在红黑树中找到对应的节点进行设置值
    • 如果是链表，那就在链表中循环判断key是否相等找到对应的位置设置值，如果没有的话在链表末尾加上一个新的Node，当链表的节点数达到8个的时候，进行树化转化为红黑树
  • 修改次数+1，size+1,如果size大于阈值，那么就进行扩容

扩容机制

当put操作之后size大于阈值时，会进行扩容。扩容过程如下：

  • 数组容量乘2，阈值乘2
  • 将老数组中的数据转到新数组中（1.7是头插法，1.8是尾插法）

注意的点：

  • 先扩容还是先插入？在第一次put的时候，数组还没初始化的时候要先进行一次扩容，然后再插入；后面在进行扩容的时候都是先插入，然后判断手超过阈值，如果超过了在扩容
  • 扩容为什么是2倍？可以有一部分数据不用进行迁移。

get操作

  • 计算hash，然后用hash值计算数组下标
  • 如果该下标的元素为空就返回空
  • 如果该下标对应的Node的key就是当前要get的key，则直接返回这个Node的value
  • 如果这个Node是TreeNode类型，就从红黑树中找到对应的key的value
  • 否则就是链表，循环取下一个依次判断key是否相等，返回value，如果没有就返回null

HashMap中的线程安全问题

  • 写冲突问题，可能线程a将在某个下标上建了一个Node被另外的覆盖，也可能Node的next被覆盖，还有可能在某个下标下这个链表只有一个Node，被删除的时候别的线程拿到了这个Node，a线程先将node.next(null)赋值给table[i],b线程这个时候将node添加一个next
  • jdk1.7中，resize过程使用头插法将数据转移到新数组的对应下标的链表的头部（这样只用修改指针而不用循环遍历链表）可能导致环形链表。在java8中改成了尾插法。

LinkedHashMap

继承自HashMap，对Entry集合添加了一个双向链表。保证插入的顺序。

TreeMap

存储数据的是一个Entry对象root，是一个红黑树结构。可以保证value有序。

java 7 ConcurrentHashMap

结构

使用Segment数组存储数据，Segment中包含一个HashEntry的数组，HashEntry与Hashmap中的Node结构类似（jdk1.7的HashMap中叫Entry）。Segment继承了ReentrantLock类。

如何保证线程安全

在进行put操作时，先定位到一个Segment，然后再调用Segment的普通方法。在Segment的普通方法中，先进行tryLock（ReentrantLock中的方法）尝试获取锁，如果获取锁失败就会在scanAndLockForPut方法中循环获取锁知道获取为止。通过在Segment上同步加锁实现线程安全，其他Segment上的数据还是可以正常被写入，减小了锁粒度。

java 8 ConcurrentHashMap

java8中的ConcurrentHashMap摈弃了分段锁的设计，采用了CAS无锁的方式解决线程安全的问题。

put操作

如果对应数组下标的元素为null就调用casTabAt(tab, i, null, new Node(hash, key, value, null)) 方法以cas的方式如果tab[i]为null设置为新建的node返回true 否则返回false。设置成功直接返回；否则，不为null ，就拿到那个node对该node加锁进行操作。这样锁住的只是数组中的一个元素而不是整个table。

List

ArrayList

基于数组，按照数组索引存放数据，超过数组的容量时进行扩容，扩容时将老的数据复制到新的数组中。默认数组大小为10，扩容容量变为1.5倍，newCapacity = oldCapacity + (oldCapacity >> 1)。

线程安全问题

  • 并发写冲突
  • 读写冲突，特别是使用iterator时数据个数变了拿到非预期的数据或者报错产生ConcurrentModificationException

LinkedList

基于链表，无需扩容。维护了2个Node，分别是头和尾，Node中包含双指针将所有节点连接起来。

线程安全问题

同ArrayList

Vector

Vector是在ArrayList的读写方法上都加上了synchornized关键字进行加锁确保线程安全。Vector的扩容也有点不一样，初始化的时候可以指定capacityIncrement（默认为0）的值，如果capacityIncrement大于0，那么扩容每次就增加capacityIncrement的容量，否则变为原来2倍。

CopyOnWriteArrayList

在ArrayList的基础上，写操作加锁，写的时候会复制一份数组出来，然后在复制的那份数组上进行操作，最后进行替换。读操作还在原来的数组上进行，不加锁。

Set

HashSet

使用HashMap实现，内部维护了一个名为map的HashMap对象。add操作就是往map中put一组数据，value都是同一个final修饰的Object对象。

CopyOnWriteArraySet

维护了一个CopyOnWriteArrayList，add的时候对这个CopyOnWriteArrayList进行addIfAbsent操作。由于CopyOnWriteArrayList是线程安全的所以CopyOnWriteArraySet也是线程安全的。