列表(List)中数组实现(ArrayList类)
JDK8源码中，初始长度是10，每次数组扩展都增加1/2左右。即：
代码语言：javascript复制 private void grow(int minCapacity) { //minCapacity为size 1，每次add元素都要检查
int oldCapacity = elementData.length; //扩展前数组的容量
int newCapacity = oldCapacity (oldCapacity >> 1); //扩展后数组的容量约为原容量1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}优点：
可以通过下标来访问或者修改元素，对下标访问的set和get时间复杂度为O(1);
缺点:
- 插入和删除的花费开销较大，除非变动是在ArrayList的末端进行。比如当在第一个位置前插入一个元素，那么首先要把所有的元素往后移动一个位置；数组扩展时，需要将原数组的元素全部复制到新数组。
- 数组要在连续的空间里存储集合的元素，由于数据存储是连续的，因此支持用下标访问元素；
数组实现(Vector 类)
同样基于数组实现，会在内存中开辟一块连续的空间来存储。ArrayList是非线程安全的，效率高；Vector是基于线程安全的，但效率低，并且是方法级别的同步，不是绝对的线程安全。 初始容量10，每次数组扩展到原来容量的2倍（每次扩充的容量大小是可以设置的，而ArrayList类不支持设定）。
链表实现(LinkedList类)
每一个元素存储本身数据的同时还存储上、下两个元素的地址(双向链表)。
优点：
- 新项的插入和现有项的删除平均开销很小O(1)（假设变动项的位置已知），因此提供了addFirst和removeFirst, addLast和removeLast, getFirst 和 getLast 等有效添加、删除和访问两端的项的方法;
- 可以在非连续的内存空间里面存储一个集合的元素；
缺点：
- 根据索引的访问时间复杂度为O(n)；
- 存放相同多的数据，一般情况下，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。
2. 栈(Stack)
栈，在计算机中运用广泛，比如说JVM，它就是基于栈来执行指令的。栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈顶，对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表，即后进先出。
栈一般有两种实现，所有操作时间复杂度O(1)：
- 栈的链表实现：利用LinkedList类，通过表顶端的元素插入和删除。
- 栈的数组实现：模仿ArrayList类，和栈相关的有两个元素，arrayList数组和topOfStack索引，初始状态topOfStack==-1，每次进栈一个元素x，topOfStack增1并令arrayList[topOfStack]=x；每次出栈一个元素，我们置返回值arrayList[topOfStack]，并令topOfStack减1。
3. 队列(Queue)
对于队列来说，元素只能从队列尾插入，从队列头访问和删除。普通的队列是一种先进先出(First In First Out，FIFO)的数据结构，而优先队列中，元素都被赋予优先级。当访问元素的时候，具有最高优先级的元素最先被删除。 队列也是表，一般有两种实现，所有操作时间复杂度O(1)(优先队列是通过大顶堆或者小顶堆实现)：
- 队列的链表实现：利用LinkedList类，通过表尾端插入元素，前端删除元素，并记录队列中元素个数currentSize。
- 队列的数组实现：保留一个数组theArray以及位置front和back，代表队列的两端；同时还要记录队列中元素个数currentSize。要使一个元素x入队，则currentSize和back增1，theArray[back]=x；要使一个元素出队，我们置返回值theArray[front]，且currentSize减1,、front增1。采用循环数组的方式，当front和back到达数组的尾端，他们又绕回开头。
4. 集合(Set)
元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是由该元素的HashCode决定的，其位置其实是固定的） Set接口有两个实现类：HashSet和LinkedHashSet
- HashSet：(底层由HashMap实现)，HashSet类按照哈希算法来存取集合中的对象，存取速度比较快 ，存入HashSet的对象必须定义hashCode()和equals()来确保对象的唯一性。
- LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。
SortedSet接口有一个实现类：TreeSet 底层是通过 TreeMap来实现的（如同HashSet底层是是通过HashMap来实现的一样），因此二者的实现方式几乎完全一样。
5. 映射（Map）
元素按键值对存储，一般无放入顺序，其中值可以重复，但键是唯一的，不能重复。Map接口有三个实现类：HashMap，Hashtable，LinkeHashMap
- HashMap：基于散列表实现，使用对象的“散列码”(hash code)来快速查询（默认使用的是Object的equals()和hashCode()方法，因此如果需要以自己定义的对象作为key，需要重写这两个方法，但是由于String字符串的这两个方法已经重写，以字符串作为key可以不重写），非线程安全，高效，允许有一个key设为null，初始容量16，负载因子0.75（比如容量16，可以存放
16*0.75=12个数据，减少冲突），增加方式：一般old*2，由于允许设置初始容量，同时要保证容量增加后要是2的指数，所以容量增加比较复杂 - Hashtable：同样基于散列表实现，但线程安全（同样是方法级别的同步），低效，不允许任何key设为null，初始容量11，负载因子0.75，增加方式是
old*2 1； - LinkeHashMap：LinkedHashMap是HashMap的一个子类，它保留插入的顺序。LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个插入元素before和下一个插入元素after的引用，从而在哈希表的基础上又构成了双向链接列表。
- SortedMap接口的实现类：TreeMap 的实现是红黑树算法，每个 Entry 都被当成“红黑树”的一个节点对待，对key进行排序。插入、删除和查询都比较慢，复杂度O(logN)，基于hash的复杂度一般为O(1)。但TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。
HashMap和Hashtable的hash值计算方式也不相同 Hashtable是直接使用对象的hashCode，并且计算在hash表中的索引时直接使用%，如下代码：
代码语言：javascript复制 int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;并且在高并发环境下，完全可以用ConcurrentHashMap来代替Hashtable。
还有一点不同：HashMap去掉了Hashtable 的contains方法，但是加上了containsValue（）和containsKey（）方法。
如何实现HashMap的同步？
HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);，具体而言，该方法返回一个同步的Map，该Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
