六、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碰撞的几率

1. 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
2. 内部已重写了 equals() 、 hashCode() 等方法，遵守了HashMap内部的规范），不容易出现Hash值计算错误的情况；

HashMap 与 HashTable 有什么区别？

1. 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本
   都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap
   吧！）；
2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被
   淘汰，不要在代码中使用它；
3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有
   一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛
   NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的
   初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后
   每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你
   给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作
   为哈希表的大小，后面会介绍到为什么是2的幂次方。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈
   值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
6. 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环
   境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

十、HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap 和 Hashtable 的区别

1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁
   进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而
   HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的
   方式实现,利用CAS算法。）
2. 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，竞争会越来越激烈效率越低。