java集合总结

1.常见集合

• Collection
  • List：有序可重复集合，可直接根据元素的索引来访问
    • Vector-Stack
    • ArrayList
    • LinkedList
  • Queue：队列集合
    • Deque-LinkedList、ArrayDeque
    • PriorityQueue
  • Set：无序不可重复集合，只能根据元素本身来访问
    • Hashset-LinkedHashSet
    • SortedSet-TreeSet
    • EnumSet
• Map：存储key-value对的集合，可根据元素的key来访问value
  • IdentityHashmap
  • WeakHashMap
  • HashMap-LinkedHashMap
  • HashTable-Properties
  • SortedMap-TreeMap
  • EnumMap

2.线程安全和线程不安全

• 线程安全：Hashtable、ConcurrentHashMap、Vector（synchronized）、Stack
• 线程不安全：HashMap、ArrayList、LinkedList、HashSet、TreeSet、TreeMap

3.ArrayList与LinkedList

• 线程安全：不安全
• 底层数据结构
  • ArrayList：Object数组
  • LinkedList：双向循环链表
• 插入删除是否受位置影响
  • ArrayList：数组存储，插入和删除元素的时间复杂度受元素位置影响，
  • LinkedList：链表存储，插入和删除元素时间复杂度不受位置影响
• 是否支持快速随机访问
  • ArrayList：实现了RandomAccess接口，能随机访问
  • LinkedList：不支持高效的随机元素访问
• 内存空间占用
  • ArrayList：在list列表的结尾会预留一定的容量空间
  • LinkedList：每个元素都需要消耗比ArrayList更多的空间（要存放直接后继和直接前驱和数据）

4.ArrayList扩容机制

本质：计算出新的扩容数组size后实例化，并将原有数组内容复制到新数组去，默认情况下，新的容量会是原容量的1.5倍

5.Array和ArrayList

• Array可以包含基本类型和对象类型，ArrayList只能包含对象类型
• Array大小是固定的，ArrayList的大小是动态变化的
• ArrayList提供了更多的方法和特性，eg：addAll（），removeAll（），iterator（）等

6.HashMap

• 底层数据结构
  • 1.7 数组+链表，链表主要解决哈希冲突
  • 1.8 数组+链表+红黑树，链表过长会严重影响HashMap的性能，红黑树搜索时间复杂度是O（logn），链表是O（n）。链表和红黑树的转换
    • 当链表超过8且数据总量超过64才会转红黑树
    • 将链表转换成红黑树前会判断，如果当前数组的长度小于64，会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
• 解决hash冲突
  • 开放定址法（再散列法）：以p为基础，再hash，以此类推，直到不冲突
  • 再哈希法：提供多个hash函数，直到不冲突
  • 链地址法：HashMap采用的方法。哈希值相同的元素构成一个单链表
  • 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区
• 加载因子
  • Node[] table初始化长度为16，负载因子默认0.75，threshold是Hashmap所能容纳键值对的最大值，threshold=length*Load factor。在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
  • 0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下
    • 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值
    • 如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactory的值，这个值可以大于1
• key的存储索引怎么计算的
  • 根据key的值计算出hashcode的值
  • 根据hashcode计算出hash的值
  • hash&（length-1）计算得到存储位置
• put流程
  • 根据key计算出hash值，找到该元素再数组中存储的下标
  • 如果数组是空的，调用resize进行初始化
  • 如果没有哈希冲突直接放在对应的数组下标里
  • 如果冲突，且key已经存在，覆盖掉value
  • 如果冲突，发现该节点是红黑树，就将这个节点挂在树上
  • 如果冲突后是链表，判断该链表是否大于8
    • 如果大于8并且数组容量小于64，就扩容。
    • 如果节点大于8并且数组容量大于64，结构转为红黑树，
    • 否则，链表插入键值对，若key存在，就覆盖掉value
• 扩容
  • 容量超过负载因子所定义的容量之后，就会扩容。将HashMap的大小扩大为原来数组的两倍，并将原来的对象放到新的数组中。
  • 1.8两处优化
    • resize之后，元素的位置在原来的位置或者原来位置+oldCap。如果bit是0，索引没变，如果是1则为原索引+oldcap
    • 1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法），1.8不会倒置，使用尾插法。
• hashMap的key：一般用Integer，String这种不可变类当key，String最常用
  • 因为字符串是不可变的，所以创建的时候hashcode就被缓存了，不需要重新计算
  • 获取对象的时候要用到equals和hashcode，键对象正确的重写这两个方法是非常重要的。
• 为什么是线程不安全的
  • 多线程下扩容死循环（1.7头插法导致的，1.8不会出现环形链表的问题）
  • 多线程的put可能导致元素的丢失。如果计算出的索引位置相同，会造成前一个key被后一个key覆盖，从而导致元素丢失。
  • put 和 get 并发时，可能导致get为null。线程1执行put，因为元素个数超出threshold导致rehash，线程2此时执行get，有可能导致这个问题。

7.ConcurrentHashMap

• 实现原理
  • 1.7
    • 由segment数组结构和HashEntry数组结构组成，把哈希桶切分成小数组，每个小数组有n个HashEntry组成。
      • segment继承了ReentrantLock，所以segment是一种可重入锁，扮演锁的角色，HashEntry用于存储键值对数据
  • 1.8
    • 选择了与hashmap相同的数组+链表+红黑树结构。在锁的实现上，抛弃了原有的Segment分段锁，采用cas+synchronized实现更加低粒度的锁。将锁级别控制在了更细粒度的哈希桶元素级别，提高并发度
• put逻辑
  • 1.7
    • 尝试获取锁，获取失败，利用自旋获取锁，如果自旋重试次数超过64次，则改为阻塞获取锁
    • 获取到锁后
      • 将当前segment中的table通过key的hashcode定位到HashEntry
      • 遍历该HashEntry，如果不为空则判断传入的key和当前遍历的key是否相等，相等则覆盖旧的value
      • 不为空则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容
      • 释放segment的锁
  • 1.8
    • 根据key计算出hash的值
    • 判断是否需要进行初始化
    • 定位到Node，拿到首节点f，判断首节点f
      • 如果为null，则通过cas的方式尝试添加
      • 如果为f.hash=MOVED=-1，说明其他线程在扩容，参与一起扩容
      • 如果都不满足，synchronized锁住f节点，判断是链表还是红黑树，遍历插入
    • 当在链表长度达到8的时候数组扩容或者将链表转换为红黑树
• get方法不需要加锁
  • Node的元素val和指针next是用volatile修饰的，在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。
  • 与volatile修饰的哈希桶没有关系：哈希桶主要是保证在数组扩容的时候保证可见性
• 不支持key或者value为null
  • value不为null：无法判断是映射的value为null，还是没找到对应的key而为null。
• 并发度
  • 1.7 默认16，可以在构造函数中设置，如果设置了并发度，ConcurrentHashMap会使用大于等于该值的最小的2的幂指数作为实际并发度，即如果设置的是17，则实际并发度为32
• 迭代器是强一致性还是弱一致性
  • HashMap是强一致性，ConcurrentHashMap是弱一致性
  • 迭代器创建后会按照哈希表结构遍历每个元素，在遍历过程中，内部元素可能发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器会 发现并反映出来，即弱一致性。

8.Hashtable

• 使用Synchronized来实现线程安全，多线程访问的时候，只有一个线程能访问或操作对象。

9.多线程下安全的操作map还有其他方法么

• Collections.synchronizedMap：对方法进行加同步锁。如果传入的是HashMap对象，也是对HashMap做了一层包装，里面使用对象锁来保证多线程场景下线程安全，本质也是全表锁。

10.Collection框架中实现比较

• 内部比较器：实体类实现Comparable接口，并实现compareTo（T t）方法
• 外部比较器：实现Comparator接口的compare（T t1，T t2）

11.Iterator 和 ListIterator

• Iterator：遍历，可以遍历所有集合，eg：Map，List，Set，但只能再向前方向上遍历集合中的元素
• ListIterator：只能遍历List实现的对象，但可以向前和向后遍历集合中的元素
  • 区别：
    • 添加元素：Iterator无法向集合中添加元素，ListIterator可以向集合中添加元素
    • 修改元素：Iterator无法修改元素，ListIterator可以使用set（）修改集合中的元素
    • 索引：Iterator无法获取集合中元素的索引，ListIterator可以获取结合中的索引

12.快速失败和安全失败

• 快速失败fail-fast
  • 在用迭代器遍历一个集合对象时， 如果遍历过程中集合对象的内容进行了修改（增删改），则会抛出ConcurrentModificationException
  • 原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量，集合在被遍历期间如果内容发生变化，就会改变modCount的值，每当迭代器使用hashNext/next遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历，否则抛出异常，终止遍历。
  • 注：这里异常的抛出条件是检测到modCount != expectedmodCount这个条件，如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出，因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug
  • 场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如hashmap，arrayList这些集合类
• 安全失败fail-safe
  • 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历
  • 原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发ConcurrentModification Exception
  • 缺点：基于拷贝内容的优点避免了ConcurrentModificationException，但同样滴，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的
  • 场景：java.util.concurrent包下的容器都是安全失败的，可以在多线程下并发使用，并发修改，比如ConcurrentHashMap