ArrayList
ArrayList底层实现是对象数组，优点是set、get时间为O(1)，缺点是add和remove时间为O(n)，需要留意的是扩容的过程以及remove的算法
public class MyArrayList<E>{
private static final int DEFAULT_CAPACITY = 10;
Object[] elementData;
int size;
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
public boolean contains(Object o){
return indexOf >= 0;
}
public E remove(int index){
rangeCheck(index);
E oldValue = elementData[index];
int numMoved = size - index - 1;
if(numMoved > 0){
System.copyarray(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
public boolean remove(Object o){
if(o == null){
for(int i = 0; i < size; i++){
fastRemove(i);
return true;
}
}else{
for(int i = 0; i < size; i++){
fastRemove(i);
return true;
}
}
return false;
}
public void fastRemove(int index){
int numMoved = size - index - 1;
if(numMoved > 0){
System.copyarray(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null;
}
public boolean add(E e){
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
public E get(int index){
rangeCheck(index);
return elementData[index];
}
public E set(int index, E element){
rangeCheck(index);
E oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
public void ensureCapacity(int minCapacity){
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
if(minCapacity - elementData.length > 0){
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private int hugeCapacity(int minCapacity){
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(index){
return "Size:" + size + ", Index:" + index;
}
public int indexOf(Object o){
if(o == null){
for(int i = 0; i < size; i++){
if(elementData[i] == null){
return i;
}
}
}else{
for(int i = 0; i < size; i++){
if(elementData[i].equals(o)){
return i;
}
}
}
return -1;
}
}本节参考 jdk1.8 源码
HashMap
table中放Entry（最新的JDK源码为Node），Entry组成链表或红黑树
Entry(Node定义)
static class Node<K, V> implements Map.Entry<K, V>{
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}从整体上看，HashMap底层的存储结构是基于数组和链表实现的。对于每一个要存入HashMap的键值对（Key-Value Pair），通过计算Key的hash值来决定存入哪个数组单元（bucket），为了处理hash冲突，每个数组单元实际上是一条Entry单链表的头结点，其后引申出一条单链表。
存取过程
取值过程大致如下：先检查table中的头结点，table中如果是树，从树中找；不然从链表中找
public V get(Object key){
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K, V> getNode(int hash, Object key){
Node<K, V>[] tab; Node<K, V> first, e; int n; K k;
//桶中头结点不为空，检查头结点
if((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null){
if(first.hash == hash &&
((k = first.key)) == key || (key != null && key.equals(k))))
return first;
if((e = first.next) != null){
//如果为红黑树，按树遍历
if(first instanceof TreeNode)
return ((treeNode<K, V>) first).getTreeNode(hash, key);
do{
if(e.hash == hash &&
(k = e.key) == key || (key != null && key.equals(k)))
return e;
}while((e = e.next) != null);
}
}
return null;
}添加键值对put(key,value)的过程：
1，判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；
2，根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入3
3，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/*表示有冲突,开始处理冲突*/
else {
Node<K,V> e;
K k;
/*检查第一个Node，p是不是要找的值*/
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
/*指针为空就挂在后面*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，
//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
//resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*如果有相同的key值就结束遍历*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/*就是链表上有相同的key值*/
if (e != null) { // existing mapping for key，就是key的Value存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回存在的Value值
}
}
++modCount;
/*如果当前大小大于门限，门限原本是初始容量*0.75*/
if (++size > threshold)
resize();//扩容两倍
afterNodeInsertion(evict);
return null;
} 扩容机制resize()
构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时,需要重新计算bucket的位置。
为什么通过计算h & (length-1)来获得bucket的位置，而不是通过计算h % length？
实际上，在HashMap中，h & (length-1) == h % length，但是需要一个前提：length必须满足是2的幂。这也正是在解释DEFAULT_INITIAL_CAPACITY和HashMap构造方法时强调的HashMap的bucket容量必须是2的幂。当length是2的幂，那么length的二进制数可以表示为1000...000，因此length - 1的二进制数为0111...111，当h与length - 1位与时，除了h的最高位的被修改为0，其余位均保持不变，这也正是实现了h % length的效果。只是相比于h % length，h & (length-1)的效率会更高。
HashMap的bucket容量必须为2的幂的另一个重要原因是一旦满足此条件，那么length即为偶数，length - 1便为奇数，所以length - 1的最后一位必为1。因此，h & (length - 1)得到的值既可能是奇数，也可能是偶数，这确保了散列的均匀性。如果length - 1是偶数，那么h & (length - 1)得到的值必为偶数，那么HashMap的空间便浪费了一半。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/*如果旧表的长度不是空*/
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
newThr = oldThr << 1; // double threshold
}
/*如果旧表的长度的是0，就是说第一次初始化表*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
/*下面开始构造新表，初始化表中的数据*/
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//把新表赋值给table
if (oldTab != null) {//原表不是空要把原表中数据移动到新表中
/*遍历原来的旧表*/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
/*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/
else { // preserve order保证顺序
新计算在新表的位置，并进行搬运
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//记录下一个结点
//新表是旧表的两倍容量，实例上就把单链表拆分为两队，
//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//lo队不为null，放在新表原位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} HashMap的总结
本节参考
HashMap的默认大小为16，即桶数组的默认长度为16；
HashMap的默认装载因子是0.75；
HashMap内部的桶数组存储的是Entry对象，也就是键值对对象。
构造器支持指定初始容量和装载因子，为避免数组扩容带来的性能问题，建议根据需求指定初始容量。装载因子尽量不要修改，0.75是个比较靠谱的值。
桶数组的长度始终是2的整数次方（大于等于指定的初始容量），这样做可以减少冲突概率，提高查找效率。（可以从indexfor函数中看出，h&(length-1),若length为奇数，length-1为偶数那么h&(length-1)结果的最后一位必然为0，也就是说所有键都被散列到数组的偶数下标位置,这样会浪费近一半空间。另外，length为2的整数次方也保证了h&(length-1)与h%length等效）.
HashMap接受null键；
HashMap不允许键重复，但是值是可以重复的。若键重复，那么新值会覆盖旧值。
HashMap通过链表法解决冲突问题，每个Entry都有一个next指针指向下一个Entry，冲突元素（不是键相同，而是hash值相同）会构成一个链表。并且最新插入的键值对始终位于链表首部。
当容量超过阈值（threshold）时,会发生扩容，扩容后的数组是原数组的两倍。扩容操作需要开辟新数组，并对原数组中所有键值对重新散列，非常耗时。我们应该尽量避免HashMap扩容。
HashMap非线程安全。
线程安全与HashTable
HashMap是一个非线程安全的，因此适合运用在单线程环境下。如果是在多线程环境，可以通过Collections的静态方法synchronizedMap获得线程安全的HashMap，如下代码所示。
Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());
HashTable和HashMap底层采用相同的存储结构，在很多方法的实现上二者的思路基本一致。最主要的区别主要有两点。
HashTable实现了所谓的线程安全，在HashTable很多方法上都加上了synchronized。
在HashMap的分析中，我们发现当我们新增键值对时，HashMap是允许Key和Value均为null。但是HashTable不允许Key或Value为null，关于这一点我们可以通过查看HashTable源码得知。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // 若value为空则抛出NullPointerException。
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode(); // 若key为空则抛出NullPointerException。
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}关于HashSet
HashSet基于HashMap实现；而Map是键值对形式的，因此构造一个PRESENT假装为值。
private static final Object PRESENT = new Object();另外，
HashSet无序；允许值为null；非线程安全；底层增删等操作基于HashMap实现；
LinkedHashSet有序；允许值为null；非线程安全；依赖于HashSet，底层增删等操作基于LinkedHashMap实现；
TreeSet有序；不允许为null；非线程安全；底层增删等操作基于TreeMap实现。
本节参考 https://segmentfault.com/a/11...
http://blog.csdn.net/tuke_tuk...