工作了3年多，一直都没花心思去看看jdk常用类的源码。以前大学的数据结构和算法课程在刚接触java时候感觉好像无用武之地。像c语言直接使用基础类型，可能需要去实现链表，栈，队列等。jdk都已经提供了实现类。趁最近有时间看看源码实现。
1.ArrayList
成员属性
elementData：数据存储的数组，任何操作都是基于这个数组。
size：集合现在实际的大小。为什么不直接使用elementData.length，如果直接使用elementData，每次插入，删除都要操作数组的空间（代价大），所以elementData并非每个空间都实际用到，因此不能使用length表示大小。（后面的其他集合对象也都是一样的道理）
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private transient Object[] elementData;
private int size;
初始化
1.默认数组长度10
2.指定数组长度
3.传入现用集合复制的数组
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
操作
get：判断坐标是否超出SIZE，并非数组长度，不过只判断是否超出，没有判断是否小于0，这点也奇怪。然后返回读取数组的数据。
set：同get，判断坐标，替换数组中的元素。
add(E e)：判断当前大小是否超出数组长度或者小于0，（这里又判断了），超出进行扩容grow(int minCapacity)，扩容大小->原来长度位移1位，实际就是*1.5，然后就是往数组[size]赋值
add(int index, E element)：同上，检查位置，不过区别在于指定坐标，就要把坐标之后的元素全部后移一位（这就是和LinkedList的效率差别，花销太大），使用System.arraycopy移动，最后一样赋值。
remove：同上，检查位置，判断是否最后一个元素，是的情况，置空最后一个元素。否的情况，一样进行位移，把坐标后面的元素全部前移一位（花销大）。
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 boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
额外说明：这里限制数组的最大长度使用了-8，按说明是为了给vms保留字头
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2.LinkedList
成员属性
first,last：记录链表的第一个和最后一个元素，Node双向链表（next，prev）
size：集合实际大小，node的个数
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
操作
get：判断位置是否超出size和小于0（ArrayList就没判断小于0），然后计算index是在size/2的前面还是后面，如果前面就使用first进行一个个遍历，如果大于就使用last遍历（类似二分查找，这里的相对于Arraylist直接使用数组坐标查找的开销就大很多）
set：同get操作获取node，把node的值赋成新的element。（与ArrayList相同）
add(E e)：直接在尾部追加，newNode.pre = last, last.next=newNode, last=newNode;（数据结构链表添加）
add(int index, E element)：判断位置合法性，判断index==size，满足就直接使用last进行追加，不满足就进行查找，添加Node进行插入（newNode在前面）
remove：判断位置合法，查找node，node.next和node.prev（node.prev.next=node.next,node.next.prev=node.prev,代码实现还需要一些额外判断）
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
两个List对比，其实和数据结构课程归纳类似：ArrayList胜在get，LinkedList胜在add，remove。不过查看代码在add(index,e)，也需要使用get，这里可能就涉及到到底查找开销大还是数组位移开销大。
3.HashMap
由于HashMap涉及到hash表的构造，以及哈希冲突等以前数据结构学过的知识，就先把几种解决哈希冲突的方法说一下
1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1)）
2.再哈希法（有多个不同的Hash函数）
3.链地址法（HashMap使用这种）
4.建立一个公共溢出区
成员属性
DEFAULT_INITIAL_CAPACITY ：默认容量
MAXIMUM_CAPACITY ：最大容量
DEFAULT_LOAD_FACTOR：加载因子，是一个比例，当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容（加载因子：防止冲突过多，如果加载因子太大，导致容量一直没有扩容，元素的冲突就非常多）
table ：存储数据的数组
size：大小（同ArrayList的size）
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry<K,V>[] table;
transient int size;
初始化
1.直接使用默认16大小，0.75加载因子初始化
2.指定大小，默认加载因子
3.指定大小，指定加载因子
顺便提一个大小的问题：我们传入10，初始化后大小也不会是10，在 while (capacity < initialCapacity) capacity «= 1;通过一直位移来确定大小，所以传入10最后会是16。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
操作
get：null特殊处理，存储位置0。其他计算key对应的hash值（hash算法可以研究一下），然后和table长度取余数，最后遍历这个坐标下面的链表（解决哈希冲突）进行hash值，key值比较，得到value。
put：计算hash，计算在数组的位置（同get操作），查看该位置是否存在改key，有就替换value，没有就新增entry（在新增的时候会判断是否扩容，原来2倍，transfer:重新计算hash的存储位置），每次扩容都要重新计算全部元素hash，开销很大，所以恰当的加载因子非常重要
remove：找出坐标（同get操作），遍历链表找出元素，然后就是单链表删除操作（pre.next=next）。
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
额外说明
indexFor：得到hash值后与长度做一个&运算，为什么会在前面说成取余数了？在前面说过table的长度只会是2的倍数，-1之后剩余的二进制全是1，这时候&运算就变成和取余数一模一样。很多地方的位运算都很神奇。
static int indexFor(int h, int length) {
return h & (length-1);
}
4.HashTable
HashTable于HashMap作比较说明
成员属性
loadFactor：加载因子（同HashMap）
table ：存储数据的数组
count：大小（同HashMap的size）
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
private transient Entry<K,V>[] table;
private transient int count;
private float loadFactor;
初始化
默认加载因子:0.75(HashMap相同)
默认大小:11(HashMap:16)
计算实际大小也没有像HashMap那样位移计算直接根据传入的长度进行初始化。
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
useAltHashing = sun.misc.VM.isBooted() &&
(initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
操作（方法加了synchronized保证线程安全）
get：计算hash值（在useAltHashing上的处理与HashMap有区别），直接与长度求余数（HashMap通过&运算），遍历链表，判断key和hash值，返回value（基本等同）。少了null的特殊判断（不支持put.null）
put：value空异常判断，key如果为null在hash(key)也会抛出异常（不支持key，value为null）。计算hash值，遍历链表，如果存在就替换value，返回。不存在，新增entry（在新增的时候会判断是否扩容rehash: newCapacity = (oldCapacity « 1) + 1;）（基本等同HashMap）
remove：计算hash值（等同get），移除元素，也是链表移除操作（等同HashMap）
private int hash(Object k) {
if (useAltHashing) {
if (k.getClass() == String.class) {
return sun.misc.Hashing.stringHash32((String) k);
} else {
int h = hashSeed ^ k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
} else {
return k.hashCode();
}
}
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
总的来说HashTable：不允许null键值，方法都加了synchronized，默认长度11，计算hash (hash & 0x7FFFFFFF) % tab.length;
不过现在有时候为了保证HashMap线程安全直接使用Collections.synchronizedMap(m)，比较少使用HashTable。
5.HashSet
HashSet是Collection接口的子类，HashMap是Map接口的子类,两者在继承上没有关联，但是内部又使用。
成员属性
map:使用HashMap，说明所有操作都是基于HashMap，也就可以存储null值
PRESENT：定义了一个Object实体来当做每次操作HashMap的value值
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
初始化
全部基于HashMap的初始化方法，提供一一对应的初始化
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
操作
全部基于HashMap的操作方法，进行操作。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
主要的几个常用的Collection，Map都大概看了源码，其实内部实现都是以前数据结构上学过的那些常用的数据结构，不过在看源码的时候发现很多地方都是使用了位运算，毕竟位运算效率高，而且很多地方都尽量契合二进制的计算规律。所以在看源码的时候，可以重点抓住：数据结构的使用，位运算的使用。
