ArrayList（数组）

ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就需要将已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动，代价比较高。因此，他适合随即查找和遍历，不适合插入和删除。

LinkedList（链表）

LinkedList在内存中开辟的内存不连续。

LinkedList是有序的双向链表。

LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，它还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆、栈、队列和双向队列使用。

LinkedList是由很多节点组成，节点里有：prev（上个节点的引用）、item（具体内容）、next（下个节点的引用）

正是因为有prev和next，它们依靠存放从上到下一个节点的引用，从而形成了有序的链表

因为有前后两个节点的引用，所以他是双向链表

LinkedList不仅拥有node，还有first和last这两个变量保存头尾节点的信息。

注意：头节点的prev指向null，尾节点的next也是指向null，他们并没有关联起来，所以跟循环双向链表区别开来。

查询数据慢的原因就在于他在内存中开辟的空间是不连续的，所以没办法像ArrayList一样快速获取数据，他需要在链表上一个个查询，直到找到想要的数据。

HashMap（数组+链表+红黑树）

HashMap根据键的HashCode值存储数据，大多数的情况下可以直接定位到他的值，因而具有很快的访问速度，但遍历顺序却是不确定的。HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

大方向上，HashMap里面是一个数组，然后数组的每个元素是一个单向链表。每个实体都是嵌套类Entry的实例，Entry包含四个属性：key、value、hash值和用于单向链表的next。