Java集合
1. ArrayList与LinkedList的异同
从底层数据结构、插入删除的时间复杂度、是否支持快速随机访问、内存占用方面比较：
底层数据结构：ArrayList底层使用Object数组；LinkedList底层使用双向链表数据结构；
插入和删除的时间复杂度：ArrayList采用数据存储，所以插入和删除元素的时间复杂度受元素位置的影响，时间复杂度为O(n)，只操作数组尾部数据时时间复杂度为O(1)。LinkedList采用链表存储，所以插入和删除元素的时间复杂度不受元素位置的影响，都是近似O(1)。
是否支持快速随机访问： LinkedList不支持高效的随机元素访问，而 ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。
内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
2. ArrayList与Vector的区别
Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。
3. HashMap的底层实现
JDK1.8 之前 HashMap 底层是 数组和链表实现存储数据的。JDK1.8 之后 HashMap 底层是 数组和链表加红黑树实现存储数据的。链表长度大于等于8时转化为红黑树，红黑树节点小于等于6时转化为链表。
HashMa是通过拉链法解决哈希冲突的。
初始化默认容量为16，默认加载因子为0.75.
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。JDK1.8 之后 HashMap 底层是 通过哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。
HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8 之后 HashMap 底层是 通过哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。同时当链表长度超过 8 时，链表转换为红黑树。
相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
HashMap 默认容量为16，加载因子为0.75，即数组长度为12时会触发扩容操作。
加载因子是表示Hash表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。反之，加载因子越小，填满的元素越少，冲突的机会减小，但空间浪费多了。
冲突的机会越大,则查找的成本越高。反之，查找的成本越小。选择0.75作为默认的加载因子，就是在 "冲突的机会"与"空间利用率"之间寻找的一种平衡与折中。
为什么使用红黑树是因为：红黑树查找效率比二叉查找树效率高，比链表更高
链表长度大于等于8时转化为红黑树，红黑树节点小于等于6时转化为链表。相关源码：
static final int TREEIFY_THRESHOLD = 8;//链表转红黑树
...
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
-----
static final int UNTREEIFY_THRESHOLD = 6;//红黑树节点转链表
...
if (lc <= UNTREEIFY_THRESHOLD)
列表比较：
| 比较 | HashMap1.7 | HashMap1.8 |
|---|---|---|
| 数据结构 | 数组+链表 | 数组+链表+红黑树 |
| 节点 | Entry | Node TreeNode |
| Hash算法 | 较为复杂 | 异或hash右移16位 |
| 对Null的处理 | 单独写一个putForNull()方法处理 | 作为以一个Hash值为0的普通节点处理 |
| 初始化 | 赋值给一个空数组，put时初始化 | 没有赋值，懒加载，put时初始化 |
| 扩容 | 插入前扩容 | 插入后，初始化，树化时扩容 |
| 节点插入 | 头插法 | 尾插法 |
4. HashMap和Hashtable的异同
通过线程是否安全、执行效率、对null键与值的支持、初始容量与扩容容量、底层结构方面分析：
-
线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。但是要保证线程安全时，使用ConcurrentHashMap 不要使用 HashTable ；
-
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
-
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
-
初始容量大小和每次扩充容量大小的不同 ：
①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的 tableSizeFor() 方法保证），比如设置HashMap初始化大小为11，实际创建出来后是16。
- 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
5. HashMap 的长度为什么是2的幂等方
取模运算%效率低，使用位运算符 & 效率高，不过，使用hash%length==hash&(length-1)的前提是 length是 2 的 n 次方，所以HashMap的长度为2的幂等方的原因是长度为2的幂等方会提高哈希计算效率以及减少哈希冲突。
拓展：使用位运算&取余
而为什么初始化容量为16呢？
设置一个合理的初始化容量可以有效的提高性能。统计分析可以得16为最佳初始化容量，可以满足大部分使用到map操作的容量要求。
6. 允许null键的map你知道哪些
| 集合类 | Key | Value | Super | 说明 |
|---|---|---|---|---|
| Hashtable | 不允许为 null | 不允许为 null | Dictionary | 线程安全 |
| ConcurrentHashMap | 不允许为 null | 不允许为 null | AbstractMap | 分段锁技术 |
| TreeMap | 不允许为 null | 允许为 null | AbstractMap | 线程不安全 |
| HashMap | 允许为 null | 允许为 null | AbstractMap | 线程不安全 |
7. ConcurrentHashMap 和 Hashtable 的区别
ConcurrentHashMap 和 Hashtable 的区别主要体现在底层数据结构与实现线程安全的方式上不同。
底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8的结构一样，数组+链表/红黑二叉树。
Hashtable和 JDK1.8 之前的 HashMap的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）：
-
① 在JDK1.7的时候，
ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了
Segment的概念，而是直接用 Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（JDK1.6以后 对synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本； -
②
Hashtable(同一把锁) ：使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
8. ConcurrentHashMap底层实现
JDK1.7
ConcurrentHashMap 类所采用的正是分段锁的思想，将 HashMap 进行切割，把 HashMap 中的哈希数组切分成小数组，每个小数组有 n 个 HashEntry 组成，其中小数组继承自ReentrantLock（可重入锁），这个小数组名叫Segment， 如下图：
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。
JDK1.8
JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全，数据结构跟 jdk1.8 中 HashMap 结构类似，都是数组 + 链表/红黑树（当链表长度大于8时，链表结构转为红黑二叉树）结构。
ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！
网友评论