读JDK源码-集合部分
以前读过一遍JDK源码的集合部分，读完了一段时间后忘了，直到有一次面试简历上还写着读过JDK集合部分的源码，但面试官让我说说，感觉记得不是很清楚了，回答的也模模糊糊的，哎，老了记性越来越差了，所以再回头来读一遍，并且在这里做个笔记，省的又忘了，java.util里的集合类的源代码本身不是很难，就一个一个的记录吧：
（1）.ArrayList：
此类底层数据结构是数组：
private transient Object[] elementData;
public ArrayList(int initialCapacity) {super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity]; }public ArrayList() { //[b]由这个无参构造可以看得出默认分配的capacity是10个[/b]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); } //默认添加到数组最末尾 public boolean add(E e) {ensureCapacity(size + 1); // Increments modCount!!elementData[size++] = e;return true; }//ensureCapacity方法确认一下数组长度，当长度不够minCapacity时就重新分配数组空间，在add方法中调用了此方法，传递给形参minCapacity的值为size+1、即有当前一个元素的空间就可以了，由此可以看出ArrayList的空间不是预先加载的，int newCapacity = (oldCapacity * 3)/2 + 1就表示新添加到空间的大小是原来长度的一半。 public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) { Object oldData[] = elementData; [b] int newCapacity = (oldCapacity * 3)/2 + 1[/b]; if (newCapacity < minCapacity)newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);} }//此方法是在指定位置添加一个元素，将此位置后的元素向后移动一个空间。 public void add(int index, E element) {if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);ensureCapacity(size+1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1, size - index);elementData[index] = element;size++; } //追加一个集合到list中，先确认了数组空间是否能容纳的下要添加到元素，然后利用了System.arraycopy方法将所有元素复制进数组中，实现起来很容易。 public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray(); int numNew = a.length;ensureCapacity(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew;return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) {if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew); // Increments modCountint numMoved = size - index;if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew);size += numNew;return numNew != 0; }transient Entry[] table;Entry是一个静态内部类，他实现的是[b]Map接口中的一个内部接口[/b]，接口也可以有嵌套定义的，长见识了。: static final int DEFAULT_INITIAL_CAPACITY = 16;//默认的初始分配空间大小 static final int MAXIMUM_CAPACITY = 1 << 30; //最大能分配的空间，写JDK的人真能装的，好端端的写个常数就行了，1左移一次相当于乘2，那就是2^30=1073741824（我也是计算器算的） static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子。 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; //典型的单向列表，后面的LinkedList还用到了双向列表。 final int hash; ....... } static int hash(int h) { // 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); } //可以添加<null,null>进去哎 public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); 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; }//根据hash值计算索引位置的 static int indexFor(int h, int length) { return h & (length-1); }//添加到元素不存在，在链表头添加元素 void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }//既然看到resize方法就说一下吧在addEntry方法里看到一个threshold的属性，该属性的值为capacity * loadFactor，当当前元素的个数超过threshold时就扩展数组大小，包括链表上面的元素。 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //prev和e都初始为链表第一个元素 while (e != null) { //检查链表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) //移除的就是链表第一个元素 table[i] = next; else //要移除的就是e，将prev的next指向e的next。 prev.next = next; e.recordRemoval(this);//看了一下这个方法里没有代码。 return e; //移除后的元素就交给GC了。 } prev = e; e = next; } return e; } public boolean add(E e) {return map.put(e, PRESENT)==null; //put方法返回与key关联的旧值，如果没有旧值就返回null，而在HashSet中PRESENT是个常量，所以第一次add时返回true，以后add时返回false，表示重复添加了，但实际上也添加进去了，只是key都一样，value都是PRESENT. } public boolean remove(Object o) {return map.remove(o)==PRESENT; } public void clear() {map.clear(); } public Iterator<E> iterator() {return map.keySet().iterator(); }