ArrayList和LinkedList的区别是什么？
底层数据结构
ArrayList 是动态数组的数据结构实现
LinkedList 是双向链表的数据结构实现
操作数据效率
ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】， LinkedList不支持下标查询
查找（未知索引）： ArrayList需要遍历，链表也需要遍历，时间复杂度都是O(n)
新增和删除
ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)
内存空间占用
ArrayList底层是数组，内存连续，节省内存
LinkedList 是双向链表需要存储数据，和两个指针，更占用内存
线程安全
ArrayList和LinkedList都不是线程安全的
如果需要保证线程安全，有两种方案：
在方法内使用，局部变量则是线程安全的
使用线程安全的ArrayList和LinkedList
适合随机访问：对于频繁随机访问元素的场景，ArrayList性能更好。
适合频繁插入和删除：对于频繁插入和删除元素的场景，LinkedList性能更好。
红黑树
红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）
红黑树的特质
性质1：节点要么是红色,要么是黑色
性质2：根节点是黑色
性质3：叶子节点都是黑色的空节点
性质4：红黑树中红色节点的子节点都是黑色
性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质，保证红黑树的平衡
红黑树的复杂度
查找：
红黑树也是一棵BST（二叉搜索树）树，查找操作的时间复杂度为：O(log n)
添加：
添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)
添加完成后涉及到复杂度为O(1)的旋转调整操作
故整体复杂度为：O(log n)
删除：
首先从根节点开始找到被删除元素的位置，时间复杂度O(log n)
删除完成后涉及到复杂度为O(1)的旋转调整操作
故整体复杂度为：O(log n)
散列表
在HashMap中的最重要的一个数据结构就是散列表，在散列表中又使用到了红黑树和链表
散列表(Hash Table)又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性
散列函数和散列冲突
将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash(key)
散列冲突-链表法（拉链）
在散列表中，数组个下标位置我们可以称之为桶（bucket）或者槽（slot），每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
时间复杂度：l插入：O(1) 删除，查询O(n)
但如果是红黑树，查询的时间复杂度是 O(logn)
说一下HashMap的实现原理
HashMap的数据结构：底层使用hash表的数据结构，就是数组和链表或红黑树
当我们往HashMap里put元素使，会利用key通过计算key的hashCode重新hash得到当前元素所在的数组下标位置。
存储时，如果出现hash值相同的key，这时候就要分情况了：
如果key相同，则覆盖原始值。
如果key不同，会将key-value放入链表或红黑树中。
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
HashMap的jdk1.7和jdk1.8有什么区别
JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值头插法加到链表中即可。
jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8） 时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。因为链表索引的时间复杂度是O(n)，红黑树是O(logn)，扩容 resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表
HashMap的put方法的具体流程
首先put的时候会检查键值对数组table是否为空，如果是空则会进行初始化扩容（resize()），因为hashmap是惰性加载，默认的构造方法中只初始化了负载因子是0.75
然后根据key计算出hashcode，再次hash得到数组索引
之后判断table[i]是否为空：
如果不为空，直接插入。
如果为空，判断两个key是否相同
相同则覆盖
不同就会检测table[i]是否是红黑树
是红黑树，将键值对插入到红黑树中
如果不是，那就是链表，会直接使用尾插法插入到链表尾部。这时候还会检查链表长度是否大于8，大于8的话会转成红黑树，在红黑树里吗进行插入操作
插入成功后，会判断键值对数量size是否已经超过了最大容量（数组大学*0.75），如果超过，进行扩容。
讲一讲HashMap的扩容机制
在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
每次扩容的时候，都是扩容之前容量的2倍；
扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
如果是红黑树，走红黑树的添加
如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
HashMap的寻址算法
首先会计算对象的hashcode
再次调用hash方法进行二次hash：这个方法会让hashcode右移16位 异或 当前hashcode，让hash分布更加均匀
最后根据 （容量-1）&hash得到索引
hashmap在1.7情况下的多线程死循环问题
数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环
面试题-HashSet与HashMap的区别
(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了 Map接口, 存储的是键值对.
(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.
面试题-HashTable与HashMap的区别
主要区别：
在实际开中不建议使用HashTable，在多线程环境下可以使用ConcurrentHashMap类