Java集合

HashMap与Hashtable的区别

  • HashMap是线程不安全的，Hashtable是线程安全的。
  • HashMap的key和value接受null，Hashtable不接受。
  • HashMap继承自AbstractMap，Hashtable继承自Directory。

ConcurrentHashMap 1.7和1.8的区别

  • 整体结构

    • 1.7：Segment + HashEntry + Unsafe
    • 1.8: 移除Segment，使锁的粒度更小，Synchronized + CAS + Node + Unsafe

  • put（）

    • 1.7：先定位Segment，再定位桶，put全程加锁，没有获取锁的线程提前找桶的位置，并最多自旋64次获取锁，超过则挂起。
    • 1.8：由于移除了Segment，类似HashMap，可以直接定位到桶，拿到first节点后进行判断
      1. first节点为空则CAS插入；
      2. first节点为-1则说明在扩容，则跟着一起扩容；
      3. else则加锁put（类似1.7）

  • resize()

    • 1.7：跟HashMap步骤一样，只不过是搬到单线程中执行，避免了HashMap在1.7中扩容时死循环的问题，保证线程安全。
    • 1.8：支持并发扩容，HashMap扩容在1.8中由**头插改为尾插**（为了避免死循环问题），ConcurrentHashmap也是，迁移也是从尾部开始，扩容前在桶的头部放置一个hash值为-1的节点，这样别的线程访问时就能判断是否该桶已经被其他线程处理过了。

  • size()

    • 1.7：很经典的思路：计算两次，如果不变则返回计算结果，若不一致，则锁住所有的Segment求和。
    • 1.8：用baseCount来存储当前的节点个数，这就设计到baseCount并发环境下修改的问题

  • 大量数据插入场景

    • 将大批量数据保存到map中有两个地方的消耗将会是比较大的：第一个是扩容操作，第二个是锁资源的争夺。
    • 第一个扩容的问题，主要还是要通过配置合理的容量大小和扩容因子，尽可能减少扩容事件的发生；
    • 第二个**锁资源的争夺，在put方法中会使用synchonized对头节点进行加锁，而锁本身也是分等级的，因此我们的主要思路就是尽可能的避免锁等级。所以，针对第二点，我们可以将数据通过通过ConcurrentHashMap的spread方法进行预处理**，这样我们可以将存在hash冲突的数据放在一个组里面，每个组都使用单线程进行put操作，这样的话可以保证锁仅停留在偏向锁这个级别，不会升级，从而提升效率。

  • 如何解决冲突

    • 在1.8中，通过拉链法处理冲突，当链表长度大于8是，转换成红黑树
    • 红黑树比较稳定，数据修改再平衡效率比较高，avl树虽然查找快但是修改效率比较低

HashMap

  • hashset和hashmap的区别

  • haspmap的底层实现put操作，扩容机制

    • put：计算hash，根据hash计算桶位，桶位为空直接放，不同追加链表最后或加到树中，判断是否需要resize
    • resize：每次resize正常情况下将容量翻倍并创建数组，根据hash计算在新数组的桶位，然后数据迁移
    • 1.7与1.8不同
      • 简化hash计算，仅将高低位与；
      • put，resize时链表中元素顺序不变；
      • 使用node替换entry

  • currenthashmap如何解决线程安全,1.7版本以及1.8版本的不同

    • cas与synchronized，锁的是数组上的节点

  • set是通过hashmap实现的

ArrayList

  • 数据结构为数组，随机访问快，插入或删除慢
  • 初始容量为10，扩容为旧数据的1.5倍，使用 Arrays.copyOf

CopyOnWriteArrayList

  • 用数组存储，volatile修饰
  • add、set、remove使用synchronized进行包装，每次操作都进行arraycopy创建新数组，get无锁