六、ArrayList和LinkedList区别 ArrayList和Vector的区别
ArrayList和LinkedList
- 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实
现。 - 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数
据存储方式，所以需要移动指针从前往后依次查找。 - 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为
ArrayList 增删操作要影响数组内的其他数据的下标。 - 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储
了两个引用，一个指向前一个元素，一个指向后一个元素。 - 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
- 综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更
推荐使用 LinkedList。
ArrayList和Vector
- 这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合
- 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程
安全的。 - 性能：ArrayList 在性能方面要优于 Vector。
- 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增
加 1 倍，而 ArrayList 只会增加 50%。
七、List 和 Set 的区别 HashSet 的实现原理
区别
List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个
null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个
null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。
另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，
无法用下标来取得想要的值
HashSet 的实现原理区别
HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为
PRESENT，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层
HashMap 的相关方法来完成，HashSet 不允许重复的值。
八、能否使用任何类作为 Map 的 key？ HashMap中String、Integer这样的包装类适合作为K
可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：
- 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。
- 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
- 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
- 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的
性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关
的问题了
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少
Hash碰撞的几率
- 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
- 内部已重写了 equals() 、 hashCode() 等方法，遵守了HashMap内部的规范），不容易出现Hash值计算错误的情况；
HashMap 与 HashTable 有什么区别？
- 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本
都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap
吧！）； - 效率： 因为线程安全的问题，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 总是使用2的幂作
为哈希表的大小，后面会介绍到为什么是2的幂次方。 - 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈
值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。 - 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环
境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。
十、HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap 和 Hashtable 的区别
- ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁
进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而
HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的
方式实现,利用CAS算法。） - HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
- 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的
数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的
HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是
主要为了解决哈希冲突而存在的； - 实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个
桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数
据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率
提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红
黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对
synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在
JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；②
Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同
步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一
个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。