以前读过一遍JDK源码的集合部分,读完了一段时间后忘了,直到有一次面试简历上还写着读过JDK集合部分的源码,但面试官让我说说,感觉记得不是很清楚了,回答的也模模糊糊的,哎,老了记性越来越差了,所以再回头来读一遍,并且在这里做个笔记,省的又忘了,java.util里的集合类的源代码本身不是很难,就一个一个的记录吧:
(1).ArrayList:
此类底层数据结构是数组:
Java代码
private transient Object[] elementData;
另外还有一个属性是用来记录size的,感觉JDK源码实现的确实很优雅,他里面的属性不多也不少,都用到很精妙。
三个构造函数:
Java代码
public ArrayList(int initialCapacity) {
super();
)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() { //[b]由这个无参构造可以看得出默认分配的capacity是10个[/b]
);
}
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);
}
添加一个元素:
Java代码
//默认添加到数组最末尾
public boolean add(E e) {
); // 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;
)/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) {
)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
); // Increments modCount!!
,
size - index);
elementData[index] = element;
size++;
}
添加一个集合进来:
Java代码
//追加一个集合到list中,先确认了数组空间是否能容纳的下要添加到元素,然后利用了System.arraycopy方法将所有元素复制进数组中,实现起来很容易。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
, elementData, size, numNew);
size += numNew;
;
}
public boolean addAll(int index, Collection<? extends E> c) {
)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
, elementData, index, numNew);
size += numNew;
;
}
remove(int index),get和set方法都是直接对数组指定位置的元素进行操作。
remove(Object obj),indexOf(Object obj)方法这样一些方法都是对数组的遍历,ArrayList中运行存放null,ArrayList是比较简单的。
(2).HashMap:
HashMap就是用hash方式映射key-value,底层实现是数组+链表的方式,通过hash码定位索引,如果有重复的索引存在就以链表的方式存放索引相同的元素,HashMap中会预分配空间,初始默认分配16个空间存放元素。
以数组+链表的方式存放元素:
Java代码
transient Entry[] table;
Entry是一个静态内部类,他实现的是[b]Map接口中的一个内部接口[/b],接口也可以有嵌套定义的,长见识了。:
;//默认的初始分配空间大小
<< 30; //最大能分配的空间,写JDK的人真能装的,好端端的写个常数就行了,1左移一次相当于乘2,那就是2^30=1073741824(我也是计算器算的)
.75f; //默认的加载因子。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; //典型的单向列表,后面的LinkedList还用到了双向列表。
final int hash;
.......
}
Map中的Entry就不在此列出了。。。
再看看他的变态的hash方法,我也没看明白,就先放这把,哪位要是看懂了给我回复一下:
Java代码
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 >>> 12);
) ^ (h >>> 4);
}
接下来我们就来看看HashMap是怎么样进行增删改查的
增加元素:
Java代码
//可以添加<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) {
);
}
//添加到元素不存在,在链表头添加元素
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)
* 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);
}
移除一个元素,因为这里涉及到数组和链表两种数据结构,所以移除时要分清楚:
Java代码
final Entry<K,V> removeEntryForKey(Object key) {
: 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;
}
查找就不多说了,看代码也比较简单。
(3).HashSet
看完了HashMap再看HashSet比较简单了,因为HashSet底层是HashMap实现的,要添加的元素作为HashMap的key,private static final Object PRESENT = new Object();作为value,由此可见HashSet是不允许有重复元素的。
Java代码
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();
}
(4).LinkedList
现在该LinkedList出场了,这个是我们数据结构里所学的双向链表,如果数据结构双向链表学到不错的话这个里面的代码也挺好理解的,首先看看他的field和constructor:
Java代码
private transient Entry<E> header = new Entry<E>(null, null, null);
public LinkedList() {
header.next = header.previous = header; //一开始表头元素的前驱和后继都指向了自己
}
//静态内部类
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
以下几个增删查到方法都比较简单。
Java代码
public E getFirst() {
)
throw new NoSuchElementException();
return header.next.element;
}
public E getLast() {
)
throw new NoSuchElementException();
return header.previous.element;
}
public E removeFirst() {
return remove(header.next);
}
public E removeLast() {
return remove(header.previous);
}
public void addFirst(E e) {
addBefore(e, header.next);
}
public void addLast(E e) {
addBefore(e, header);
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
Java代码
// 更新:
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
private Entry<E> entry(int index) {
|| index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
)) { //entry方法在此处采用了二分法查找
; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}