HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底层实现

HashSet与HashMap区别

HashMap实现了Map接口 

HashSet实现了Set接口

HashMap储存键值对 

HashSet仅仅存储对象

HashMap使用put()方法将元素放入map中 

HashSet使用add()方法将元素放入set中

HashMap中使用键对象来计算hashcode值 

HashSet使用成员对象来计算hashcode值

HashMap比较快，因为是使用唯一的键来获取对象 

HashSet较HashMap来说比较慢

HashTable与HashMap的区别

Hashtable方法是同步的 

HashMap方法是非同步的

Hashtable基于Dictionary类 

HashMap基于AbstractMap，而AbstractMap基于Map接口的实现

Hashtable中key和value都不允许为null，遇到null，直接返回 NullPointerException 

HashMap中key和value都允许为null，遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理

Hashtable中hash数组默认大小是11，扩充方式是old*2+1 

HashMap中hash数组的默认大小是16，而且一定是2的指数

什么是ArrayList

ArrayList可以理解为动态数组，它的容量能动态增长，该容量是指用来存储列表元素的数组的大小，随着向ArrayList中不断添加元素，其容量也自动增长 

ArrayList允许包括null在内的所有元素 

ArrayList是List接口的非同步实现 

ArrayList是有序的

定义如下：

ArrayList实现了List接口、底层使用数组保存所有元素，其操作基 本上是对数组的操作

ArrayList继承了AbstractList抽象类，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能

ArrayList实现了RandmoAccess接口，即提供了随机访问功能，RandmoAccess是java中用来被List实现，为List提供快速访问功能的，我们可以通过元素的序号快速获取元素对象，这就是快速随机访问

ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆 

ArrayList实现了java.io.Serializable接口，意味着ArrayList支持序列化

什么是LinkedList

LinkedList基于链表的List接口的非同步实现 

LinkedList允许包括null在内的所有元素 

LinkedList是有序的 

LinkedList是fail-fast的

LinkedList与ArrayList的区别

LinkedList底层是双向链表 

ArrayList底层是可变数组

LinkedList不允许随机访问，即查询效率低 

ArrayList允许随机访问，即查询效率高

LinkedList插入和删除效率快 

ArrayList插入和删除效率低

解释一下：

对于随机访问的两个方法，get和set，ArrayList优于LinkedList，因为LinkedList要移动指针 

对于新增和删除两个方法，add和remove，LinedList比较占优势，因为ArrayList要移动数据

什么是ConcurrentHashMap

ConcurrentHashMap基于双数组和链表的Map接口的同步实现 

ConcurrentHashMap中元素的key是唯一的、value值可重复 

ConcurrentHashMap不允许使用null值和null键 

ConcurrentHashMap是无序的

为什么使用ConcurrentHashMap

我们都知道HashMap是非线程安全的，当我们只有一个线程在使用HashMap的时候，自然不会有问题，但如果涉及到多个线程，并且有读有写的过程中，HashMap就会fail-fast。要解决HashMap同步的问题，我们的解决方案有

Hashtable 

Collections.synchronizedMap(hashMap) 

这两种方式基本都是对整个hash表结构加上同步锁，这样在锁表的期间，别的线程就需要等待了，无疑性能不高，所以我们引入ConcurrentHashMap，既能同步又能多线程访问

ConcurrentHashMap的数据结构

ConcurrentHashMap的数据结构为一个Segment数组，Segment的数据结构为HashEntry的数组，而HashEntry存的是我们的键值对，可以构成链表。可以简单的理解为数组里装的是HashMap

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长，但是带来的好处是写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment。正是因为其内部的结构以及机制，ConcurrentHashMap在并发访问的性能上要比Hashtable和同步包装之后的HashMap的性能提高很多。在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设置为 16），及任意数量线程的读操作