读JDK源码集合部分

时间:2022-07-17 17:20:27

以前读过一遍JDK源码的集合部分,读完了一段时间后忘了,直到有一次面试简历上还写着读过JDK集合部分的源码,但面试官让我说说,感觉记得不是很清楚了,回答的也模模糊糊的,哎,老了记性越来越差了,所以再回头来读一遍,并且在这里做个笔记,省的又忘了,java.util里的集合类的源代码本身不是很难,就一个一个的记录吧: 
(1).ArrayList: 
此类底层数据结构是数组:

Java代码  读JDK源码集合部分

  1. private transient Object[] elementData;

另外还有一个属性是用来记录size的,感觉JDK源码实现的确实很优雅,他里面的属性不多也不少,都用到很精妙。 
三个构造函数:

Java代码  读JDK源码集合部分

  1. public ArrayList(int initialCapacity) {

  2. super();

  3. )

  4. throw new IllegalArgumentException("Illegal Capacity: "+

  5. initialCapacity);

  6. this.elementData = new Object[initialCapacity];

  7. }

  8. public ArrayList() {        //[b]由这个无参构造可以看得出默认分配的capacity是10个[/b]

  9. );

  10. }

  11. public ArrayList(Collection<? extends E> c) {

  12. elementData = c.toArray();

  13. size = elementData.length;

  14. // c.toArray might (incorrectly) not return Object[] (see 6260652)

  15. if (elementData.getClass() != Object[].class)

  16. elementData = Arrays.copyOf(elementData, size, Object[].class);

  17. }

添加一个元素:

Java代码  读JDK源码集合部分

  1. //默认添加到数组最末尾

  2. public boolean add(E e) {

  3. );  // Increments modCount!!

  4. elementData[size++] = e;

  5. return true;

  6. }

  7. //ensureCapacity方法确认一下数组长度,当长度不够minCapacity时就重新分配数组空间,在add方法中调用了此方法,传递给形参minCapacity的值为size+1、即有当前一个元素的空间就可以了,由此可以看出ArrayList的空间不是预先加载的,int newCapacity = (oldCapacity * 3)/2 + 1就表示新添加到空间的大小是原来长度的一半。

  8. public void ensureCapacity(int minCapacity) {

  9. modCount++;

  10. int oldCapacity = elementData.length;

  11. if (minCapacity > oldCapacity) {

  12. Object oldData[] = elementData;

  13. )/2 + 1[/b];

  14. if (newCapacity < minCapacity)

  15. newCapacity = minCapacity;

  16. // minCapacity is usually close to size, so this is a win:

  17. elementData = Arrays.copyOf(elementData, newCapacity);

  18. }

  19. }

  20. //此方法是在指定位置添加一个元素,将此位置后的元素向后移动一个空间。

  21. public void add(int index, E element) {

  22. )

  23. throw new IndexOutOfBoundsException(

  24. "Index: "+index+", Size: "+size);

  25. );  // Increments modCount!!

  26. ,

  27. size - index);

  28. elementData[index] = element;

  29. size++;

  30. }

添加一个集合进来:

Java代码  读JDK源码集合部分

  1. //追加一个集合到list中,先确认了数组空间是否能容纳的下要添加到元素,然后利用了System.arraycopy方法将所有元素复制进数组中,实现起来很容易。

  2. public boolean addAll(Collection<? extends E> c) {

  3. Object[] a = c.toArray();

  4. int numNew = a.length;

  5. ensureCapacity(size + numNew);  // Increments modCount

  6. , elementData, size, numNew);

  7. size += numNew;

  8. ;

  9. }

  10. public boolean addAll(int index, Collection<? extends E> c) {

  11. )

  12. throw new IndexOutOfBoundsException(

  13. "Index: " + index + ", Size: " + size);

  14. Object[] a = c.toArray();

  15. int numNew = a.length;

  16. ensureCapacity(size + numNew);  // Increments modCount

  17. int numMoved = size - index;

  18. )

  19. System.arraycopy(elementData, index, elementData, index + numNew,

  20. numMoved);

  21. , elementData, index, numNew);

  22. size += numNew;

  23. ;

  24. }

remove(int index),get和set方法都是直接对数组指定位置的元素进行操作。 
remove(Object obj),indexOf(Object obj)方法这样一些方法都是对数组的遍历,ArrayList中运行存放null,ArrayList是比较简单的。 
(2).HashMap: 
HashMap就是用hash方式映射key-value,底层实现是数组+链表的方式,通过hash码定位索引,如果有重复的索引存在就以链表的方式存放索引相同的元素,HashMap中会预分配空间,初始默认分配16个空间存放元素。 
以数组+链表的方式存放元素:

Java代码  读JDK源码集合部分

  1. transient Entry[] table;

  2. Entry是一个静态内部类,他实现的是[b]Map接口中的一个内部接口[/b],接口也可以有嵌套定义的,长见识了。:

  3. ;//默认的初始分配空间大小

  4. << 30; //最大能分配的空间,写JDK的人真能装的,好端端的写个常数就行了,1左移一次相当于乘2,那就是2^30=1073741824(我也是计算器算的)

  5. .75f; //默认的加载因子。

  6. static class Entry<K,V> implements Map.Entry<K,V> {

  7. final K key;

  8. V value;

  9. Entry<K,V> next;       //典型的单向列表,后面的LinkedList还用到了双向列表。

  10. final int hash;

  11. .......

  12. }

Map中的Entry就不在此列出了。。。 
再看看他的变态的hash方法,我也没看明白,就先放这把,哪位要是看懂了给我回复一下:

Java代码  读JDK源码集合部分

  1. static int hash(int h) {

  2. // This function ensures that hashCodes that differ only by

  3. // constant multiples at each bit position have a bounded

  4. // number of collisions (approximately 8 at default load factor).

  5. ) ^ (h >>> 12);

  6. ) ^ (h >>> 4);

  7. }

接下来我们就来看看HashMap是怎么样进行增删改查的 
增加元素:

Java代码  读JDK源码集合部分

  1. //可以添加<null,null>进去哎

  2. public V put(K key, V value) {

  3. if (key == null)

  4. return putForNullKey(value);

  5. int hash = hash(key.hashCode());

  6. int i = indexFor(hash, table.length);

  7. for (Entry<K,V> e = table[i]; e != null; e = e.next) {  //遍历链表,如果元素已经存在就更新,否则就在链表中添加一个。

  8. Object k;

  9. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

  10. V oldValue = e.value;

  11. e.value = value;

  12. e.recordAccess(this);

  13. return oldValue;

  14. }

  15. }

  16. modCount++;

  17. addEntry(hash, key, value, i);

  18. return null;

  19. }

  20. //根据hash值计算索引位置的

  21. static int indexFor(int h, int length) {

  22. );

  23. }

  24. //添加到元素不存在,在链表头添加元素

  25. void addEntry(int hash, K key, V value, int bucketIndex) {

  26. Entry<K,V> e = table[bucketIndex];

  27. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

  28. if (size++ >= threshold)

  29. * table.length);

  30. }

  31. //既然看到resize方法就说一下吧

  32. 在addEntry方法里看到一个threshold的属性,该属性的值为capacity * loadFactor,当当前元素的个数超过threshold时就扩展数组大小,包括链表上面的元素。

  33. void resize(int newCapacity) {

  34. Entry[] oldTable = table;

  35. int oldCapacity = oldTable.length;

  36. if (oldCapacity == MAXIMUM_CAPACITY) {

  37. threshold = Integer.MAX_VALUE;

  38. return;

  39. }

  40. Entry[] newTable = new Entry[newCapacity];

  41. transfer(newTable);

  42. table = newTable;

  43. threshold = (int)(newCapacity * loadFactor);

  44. }

移除一个元素,因为这里涉及到数组和链表两种数据结构,所以移除时要分清楚:

Java代码  读JDK源码集合部分

  1. final Entry<K,V> removeEntryForKey(Object key) {

  2. : hash(key.hashCode());

  3. int i = indexFor(hash, table.length);

  4. Entry<K,V> prev = table[i];

  5. Entry<K,V> e = prev;     //prev和e都初始为链表第一个元素

  6. while (e != null) {    //检查链表

  7. Entry<K,V> next = e.next;

  8. Object k;

  9. if (e.hash == hash &&

  10. ((k = e.key) == key || (key != null && key.equals(k)))) {

  11. modCount++;

  12. size--;

  13. if (prev == e) //移除的就是链表第一个元素

  14. table[i] = next;

  15. else        //要移除的就是e,将prev的next指向e的next。

  16. prev.next = next;

  17. e.recordRemoval(this);//看了一下这个方法里没有代码。

  18. return e;     //移除后的元素就交给GC了。

  19. }

  20. prev = e;

  21. e = next;

  22. }

  23. return e;

  24. }

查找就不多说了,看代码也比较简单。 
(3).HashSet 
看完了HashMap再看HashSet比较简单了,因为HashSet底层是HashMap实现的,要添加的元素作为HashMap的key,private static final Object PRESENT = new Object();作为value,由此可见HashSet是不允许有重复元素的。

Java代码  读JDK源码集合部分

  1. public boolean add(E e) {

  2. return map.put(e, PRESENT)==null;   //put方法返回与key关联的旧值,如果没有旧值就返回null,而在HashSet中PRESENT是个常量,所以第一次add时返回true,以后add时返回false,表示重复添加了,但实际上也添加进去了,只是key都一样,value都是PRESENT.

  3. }

  4. public boolean remove(Object o) {

  5. return map.remove(o)==PRESENT;

  6. }

  7. public void clear() {

  8. map.clear();

  9. }

  10. public Iterator<E> iterator() {

  11. return map.keySet().iterator();

  12. }

(4).LinkedList 
现在该LinkedList出场了,这个是我们数据结构里所学的双向链表,如果数据结构双向链表学到不错的话这个里面的代码也挺好理解的,首先看看他的field和constructor:

Java代码  读JDK源码集合部分

  1. private transient Entry<E> header = new Entry<E>(null, null, null);

  2. public LinkedList() {

  3. header.next = header.previous = header; //一开始表头元素的前驱和后继都指向了自己

  4. }

  5. //静态内部类

  6. private static class Entry<E> {

  7. E element;

  8. Entry<E> next;

  9. Entry<E> previous;

  10. Entry(E element, Entry<E> next, Entry<E> previous) {

  11. this.element = element;

  12. this.next = next;

  13. this.previous = previous;

  14. }

  15. }

以下几个增删查到方法都比较简单。

Java代码  读JDK源码集合部分

  1. public E getFirst() {

  2. )

  3. throw new NoSuchElementException();

  4. return header.next.element;

  5. }

  6. public E getLast()  {

  7. )

  8. throw new NoSuchElementException();

  9. return header.previous.element;

  10. }

  11. public E removeFirst() {

  12. return remove(header.next);

  13. }

  14. public E removeLast() {

  15. return remove(header.previous);

  16. }

  17. public void addFirst(E e) {

  18. addBefore(e, header.next);

  19. }

  20. public void addLast(E e) {

  21. addBefore(e, header);

  22. }

  23. public void push(E e) {

  24. addFirst(e);

  25. }

  26. public E pop() {

  27. return removeFirst();

  28. }

Java代码  读JDK源码集合部分

  1. // 更新:

  2. public E set(int index, E element) {

  3. Entry<E> e = entry(index);

  4. E oldVal = e.element;

  5. e.element = element;

  6. return oldVal;

  7. }

  8. private Entry<E> entry(int index) {

  9. || index >= size)

  10. throw new IndexOutOfBoundsException("Index: "+index+

  11. ", Size: "+size);

  12. Entry<E> e = header;

  13. )) {  //entry方法在此处采用了二分法查找

  14. ; i <= index; i++)

  15. e = e.next;

  16. } else {

  17. for (int i = size; i > index; i--)

  18. e = e.previous;

  19. }

  20. return e;

  21. }