java面试——集合（ArrayList、lterator、LinkedList）源码理解

---

ArrayList扩容机制

• 初始化：（无参时）数组大小是0，添加第一个元素时是10。有参数时，数组大小就是参数。
• 扩容条件：超过容量大小的3/4。
• 以后扩容大小是上一次数组大小的1.5倍（原容量右移一位+原容量）。
• addAll（）扩容机制： 比较下次扩容的大小和添加元素的个数，取较大值。

lterator迭代器

• fail-fast：一旦发现遍历时，其他线程来修改，即将抛异常（ArrayList）
  • 如何判断——在迭代器初始化成员变量时会记录当前集合被修改的次数，在遍历中一直比较这两个值是否相等。如果在遍历的途中集合的修改次数参数改变，就会抛出异常
• fail-safe：遍历时其他线程来修改，牺牲一致性，保持遍历（CopyOnWriteArrayList）
  • 初始化时在迭代器成员中复制了当前集合
  • add（）源码——写时复制，即在添加元素时，复制一个新数组（长度+1），在新数组的最后加入新元素。

ArrayList与LinkedList的区别

• 底层结构：
  • ArrayList是数组，需要连续的内存
  • LinkedList是双向链表，不需要连续内存
• 随机访问性能
  • ArrayList支持随机访问，实现了RandomAccess接口（里面没有方法，只是一个标识）
  • LinkedList不支持随机访问，因为是链式存储，需要遍历寻址。
• 插入、删除对比
  • ArrayList尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低（未扩容时）
  • LinkedList头尾插入删除性能高
• 内存
  • ArrayList：可以利用CPU缓存、局部性原理
  • LinkedList：占用内存多