Luckylau's Blog

Java基础之集合框架

发表于 | 分类于 |

java的集合框架详细解读(基于jdk1.8）

java集合框架

java集合框架需要掌握的是六大接口（Collection、Set、List、Map、Iterator和Comparable）和两个工具类Arrays和Collections。

Collection接口继承了Iterable接口，是最基本集合接口,由于Iterable接口依赖Iterator接口，所以所有实现Collection接口的容器类都有iterator方法，用于返回一个实现了Iterator接口的对象。Iterator对象称作迭代器，Iterator接口方法能以迭代方式逐个访问集合中各个元素，并可以从Collection中除去适当的元素。另外由Collection接口派生出3个主要接口，分别是List ,Set,Queue。

Map也是接口，但没有继承Collection接口。该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对（key/value pairs）。

Comparable可以用于比较的实现，实现了Comparable接口的类可以通过实现comparaTo方法从而确定该类对象的排序方式。

另外就是两个重要的工具类，分别是用来操作数组、集合的Arrays和Collections，例如在ArrayList和Vector中大量调用了Arrays.Copyof()方法，而Collections中有很多静态方法可以返回各集合类的synchronized版本，即线程安全的版本，当然了，如果要用线程安全的结合类，首选Concurrent并发包下的对应的集合类。

Collection接口概览

Collection接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    //@since 1.8
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    //@since 1.8
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }
    //@since 1.8
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }
    //@since 1.8
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

在Java8的新特性中有一个新特性为接口默认方法，该新特性允许我们在接口中添加一个非抽象的方法实现，而这样做的方法只需要使用关键字default修饰该默认实现方法即可。该特性又叫扩展方法。

List接口概览

​ List是一个继承Collection接口的接口，当然间接的继承了Iterable接口，实现类包括：ArrayList、LinkedList、Vector等。List是有序的Collection可以对每个元素的插入位置进行精准控制，可以根据索引访问元素，允许重复元素，有自己的迭代器 ListIterator。Java8有28个方法，我们只列举常见方法，也是后面会主要分析其实现的方法。

1
2
3
4
5
6
7
8
9
10
boolean add(E e);
void add(int index, E e);
E set(int index, E e);
get(int index);
boolean remove(Object o);
Iterator iterator();
int indexOf(E e);
int lastIndexOf(E e);
void clear();
List subList(int fromIndex, int toIndex);

ArrayList

​ ArrayList是一个可改变大小的数组，当更多的元素加入到ArrayList中时，其大小将会动态的增长。内部的元素可以直接通过get与set方法进行访问，因为ArrayList本质上就是一个数组。ArrayList不是线程安全的，只能在单线程环境下，多线程环境下可以考虑用 collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

初始化代码
1
2
3
4
5
6
7
8
9
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;

涉及知识点：

transient

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package test1;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
class UserInfo implements Serializable {  
    private static final long serialVersionUID = 996890129747019948L;  
    private String name;  
    private transient String psw;   
    public UserInfo(String name, String psw) {  
        this.name = name;  
        this.psw = psw;  
    }   
    public String toString() {  
        return "name=" + name + ", psw=" + psw;  
    }  
}    
public class TestTransient {  
    public static void main(String[] args) {  
    	UserInfo userInfo = new UserInfo("张三", "123456");  
        System.out.println(userInfo);  
        try {  
            // 序列化，被设置为transient的属性没有被序列化  
            ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(  
                    "UserInfo.out"));  
            o.writeObject(userInfo);  
            o.close();  
        } catch (Exception e) {  
            // TODO: handle exception  
            e.printStackTrace();  
        }  
        try {  
            // 重新读取内容  
            ObjectInputStream in = new ObjectInputStream(new FileInputStream(  
                    "UserInfo.out"));  
            UserInfo readUserInfo = (UserInfo) in.readObject();  
            //读取后psw的内容为null  
            System.out.println(readUserInfo.toString());  
        } catch (Exception e) {  
            // TODO: handle exception  
            e.printStackTrace();  
        }  
    }  
}
三种构建方法

第一个构造方法使用提供的initialCapacity来初始化elementData数组的大小。

第二个构造方法调用第一个构造方法并传入参数10，即默认elementData数组的大小为10。

第三个构造方法则将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// ArrayList带容量大小的构造函数。       
 public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
// ArrayList无参构造函数。默认容量是10。    
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }      
// 创建一个包含collection的ArrayList     
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
add方法代码

boolean add(E e)

void add(int index, E element)

boolean addAll(Collection<? extends E> c)

boolean addAll(int index,Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
   // 将e添加到ArrayList中    
   public boolean add(E e) {    
       ensureCapacityInternal(size + 1);  // Increments modCount!!    
       elementData[size++] = e;    
       return true;    
   }     
   // 将e添加到ArrayList的指定位置    
   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++;    
   }  
   private void rangeCheckForAdd(int index) {
       if (index > size || index < 0)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }   
   // 将集合c追加到ArrayList中    
   public boolean addAll(Collection<? extends E> c) {    
       Object[] a = c.toArray();    
       int numNew = a.length;    
       ensureCapacityInternal(size + numNew);  // Increments modCount    
       System.arraycopy(a, 0, elementData, size, numNew);    
       size += numNew;    
       return numNew != 0;    
   }    
  
   // 从index位置开始，将集合c添加到ArrayList    
   public boolean addAll(int index, Collection<? extends E> c) {    
       rangeCheckForAdd(index);  
       Object[] a = c.toArray();    
       int numNew = a.length;    
       ensureCapacityInternal(size + numNew);  // Increments modCount    
  
       int 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;    
   }  
   // 确定ArrarList的容量。    
   // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
   }
  private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”    
       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 static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }
remove方法代码

E remove(int index)

boolean remove(Object o)

void removeRange(int fromIndex, int toIndex)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    // 删除ArrayList指定位置的元素    
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; // clear to let GC do its work
        return oldValue;
    }
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
   // 删除元素        
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
           // 便利ArrayList，找到“元素o”，则删除，并返回true。    
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
	// 删除fromIndex到toIndex之间的全部元素。    
protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    // 快速删除第index个元素    
private void fastRemove(int index) {    
        modCount++;    
        int numMoved = size - index - 1;    
        // 从"index+1"开始，用后面的元素替换前面的元素。    
        if (numMoved > 0)    
            System.arraycopy(elementData, index+1, elementData, index,    
                             numMoved);    
        // 将最后一个元素设为null    
        elementData[--size] = null; // Let gc do its work    
    }
get方法代码

E get(int index)

E set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
// 获取index位置的元素值    
public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
// 设置index位置的值为element
public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
clear方法代码
1
2
3
4
5
6
7
// 清空ArrayList，将全部的元素设为null    
    public void clear() {    
        modCount++;    
        for (int i = 0; i < size; i++)    
            elementData[i] = null;      
        size = 0;    
    }
clone方法代码

调用父类的clone方法返回一个对象的副本，将返回对象的elementData数组的内容赋值为原对象elementData数组的内容，将副本的modCount设置为0。

1
2
3
4
5
6
7
8
9
10
11
12
// 克隆函数     
public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
indexOf(Object o)方法代码
1
2
3
4
5
6
7
8
9
10
11
12
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 (o.equals(elementData[i]))  
             return i;  
     }  
     return -1;  
     }
lastIndexOf(Object o)方法代码
1
2
3
4
5
6
7
8
9
10
11
12
public int lastIndexOf(Object o) {  
     if (o == null) {  
         for (int i = size-1; i >= 0; i--)  
         if (elementData[i]==null)  
             return i;  
     } else {  
         for (int i = size-1; i >= 0; i--)  
         if (o.equals(elementData[i]))  
             return i;  
     }  
     return -1;  
     }
writeObject和readObject方法代码

void writeObject(java.io.ObjectOutputStream s)

void readObject(java.io.ObjectInputStream s) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   // java.io.Serializable的写入函数    
    // 将ArrayList的“容量，所有的元素值”都写入到输出流中    
    private void writeObject(java.io.ObjectOutputStream s)    
        throws java.io.IOException{    
    // Write out element count, and any hidden stuff    
    	int expectedModCount = modCount;    
    	s.defaultWriteObject();    
        // 写入“数组的容量”    
        s.writeInt(elementData.length);    
   		 // 写入“数组的每一个元素”    
   		 for (int i=0; i<size; i++)    
            	s.writeObject(elementData[i]);
    	if (modCount != expectedModCount) {    
              throw new ConcurrentModificationException();    
        } 
    }    
    // java.io.Serializable的读取函数：根据写入方式读出    
    // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出    
    private void readObject(java.io.ObjectInputStream s)    
        throws java.io.IOException, ClassNotFoundException {    
        // Read in size, and any hidden stuff    
        	s.defaultReadObject();    
        // 从输入流中读取ArrayList的“容量”    
        	int arrayLength = s.readInt();    
        	Object[] a = elementData = new Object[arrayLength];    
        // 从输入流中将“所有的元素值”读出    
        	for (int i=0; i<size; i++)    
            	a[i] = s.readObject();    
    }    
}
其他方法

boolean contains(Object o)

boolean isEmpty()

int size()

Object[] toArray()

T[] toArray(T[] a)

void trimToSize()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// ArrayList是否包含Object(o)    
    public boolean contains(Object o) {    
        return indexOf(o) >= 0;    
    }    
// 返回ArrayList是否为空    
    public boolean isEmpty() {    
        return size == 0;    
    } 
// 返回ArrayList的实际大小    
    public int size() {    
        return size;    
    }    
// 返回ArrayList的Object数组    
    public Object[] toArray() {    
        return Arrays.copyOf(elementData, size);    
    }    
// 返回ArrayList元素组成的数组  
    public <T> T[] toArray(T[] a) {    
        // 若数组a的大小 < ArrayList的元素个数；    
        // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中    
        if (a.length < size)    
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());    
        // 若数组a的大小 >= ArrayList的元素个数；    
        // 则将ArrayList的全部元素都拷贝到数组a中。    
        System.arraycopy(elementData, 0, a, 0, size);    
        if (a.length > size)    
            a[size] = null;    
        return a;    
    } 
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

几点说明：

ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法

Arrays.copyof()方法

1
2
3
4
5
6
7
8
9
10
11
public static <T> T[] copyOf(T[] original, int newLength) {  
    return (T[]) copyOf(original, newLength, original.getClass());  
} 
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
    T[] copy = ((Object)newType == (Object)Object[].class)  
        ? (T[]) new Object[newLength]  
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
    System.arraycopy(original, 0, copy, 0,  
                     Math.min(original.length, newLength));  
    return copy;  
}  //该方法实际上是在其内部又创建了一个长度为newlength的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中。

System.arraycopy()方法

​ 该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

LinkedList

​ LinkedList 是一个双向循环链表,在添加和删除元素时具有比ArrayList更好的性能。但在get与set方面弱于ArrayList。当然这些对比都是指数据量很大或者操作很频繁的情况下的对比，如果数据和运算量很小，那么对比将失去意义。 LinkedList还实现了Queue接口，该接口比List提供了更多的方法，包括offer()，peek()，poll()等。所以除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。LinkedList同样是非线程安全的，只在单线程下适合使用。LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

初始化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
两种构建方法

无参构造方法和Collection的构造方法，先调用无参构造方法建立一个空链表，然后将Collection中的数据加入到链表的尾部后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 默认构造函数    
   public LinkedList() {
    }
// 包含“集合”的构造函数:创建一个包含“集合”的LinkedList    
    public LinkedList(Collection<? extends E> c) {    
        this();    
        addAll(c);    
    } 
// 将“集合(c)”添加到LinkedList中。    
    // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。    
    public boolean addAll(Collection<? extends E> c) {    
        return addAll(size, c);    
    }   
// 从双向链表的index开始，将“集合(c)”添加到双向链表中。
   public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }
private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 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;
        }
    }
add方法代码

boolean add(E e)

void add(int index, E element)

void addFirst(E e)

void addLast(E e)

void push(E e)

boolean offer(E e)

boolean offerLast(E e)

boolean offerFirst(E e)

E set( int index, E element)

boolean addAll(Collection<? extends E> c)

boolean addAll(int index, Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//将元素(E)添加到LinkedList中    
    public boolean add(E e) {        
        linkLast(e);
        return true;    
    } 
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
 // 在index前添加节点，且节点的值为element    
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    } 
private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
// 将元素添加到LinkedList的起始位置    
public void addFirst(E e) {
        linkFirst(e);
    }
// 将元素添加到LinkedList的结束位置    
public void addLast(E e) {
        linkLast(e);
    }
// 将e插入到双向链表开头    
    public void push(E e) {
        addFirst(e);
    }
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
// 将e添加双向链表末尾    
public boolean offer(E e) {
        return add(e);
    }
// 将e添加双向链表开头    
    public boolean offerFirst(E e) {    
        addFirst(e);    
        return true;    
    }    
// 将e添加双向链表末尾    
    public boolean offerLast(E e) {    
        addLast(e);    
        return true;    
    }   
// 设置index位置对应的节点的值为element    
public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
get方法代码

E get(int index)

E getFirst()

E getLast()

E peekFirst()

E peekLast()

E peek()

E element()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 返回LinkedList指定位置的元素    
public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
// 获取LinkedList的第一个元素     
public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
// 获取LinkedList的最后一个元素    
public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    } 
// 返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
   
    // 返回最后一个节点    
    // 若LinkedList的大小为0,则返回null    
 public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }
    
// 返回第一个节点      
 public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    // 返回第一个节点    
    // 若LinkedList的大小为0,则抛出异常    
   public E element() {
        return getFirst();
    }
remove方法代码

E poll()

E removeFirst()

E removeLast()

E pollFirst()

E pollLast()

E pop()

boolean removeLastOccurrence(Object o)

boolean removeLastOccurrence(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 删除LinkedList的最后一个元素     
public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
// 删除index位置的节点    
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }
  
// 删除并返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
   public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
   private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    // 删除并返回第一个节点       
     public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
   
    // 删除并返回最后一个节点        
   public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
// 删除并返回第一个节点    
   public E pop() {
        return removeFirst();
    }
// 删除LinkedList的第一个元素    
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
}
    // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点    
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点    
    public boolean removeFirstOccurrence(Object o) {    
        return remove(o);    
    }    
   
    // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点    
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点 
public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
clear方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 清空双向链表    
public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }
lastIndexOf(Object o)方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 从后向前查找，返回“值为对象(o)的节点对应的索引”    
    // 不存在就返回-1    
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }
listIterator(int index)方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)    
public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
// List迭代器    
private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        public boolean hasNext() {
            return nextIndex < size;
        }
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
        public int nextIndex() {
            return nextIndex;
        }
        public int previousIndex() {
            return nextIndex - 1;
        }
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }
        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
其他方法

boolean contains(Object o)

int size()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 判断LinkedList是否包含元素(o)    
    public boolean contains(Object o) {    
        return indexOf(o) != -1;    
    }    
// 返回LinkedList的大小    
    public int size() {    
        return size;    
    }              
 // 从前向后查找，返回“值为对象(o)的节点对应的索引”    
 // 不存在就返回-1      
public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

Vector

​ Vector 和ArrayList类似,但属于强同步类。如果你的程序本身是线程安全的(thread-safe，没有在多个线程之间共享同一个集合/对象)，那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%。

Vector的API源码显的比较臃肿、基本现在已经不再推荐使用Vector了、可以使用经过处理后的ArrayList来代替多线程环境中的Vector。

初始化代码

Vector是JDK1.0引入了，它的很多实现方法都加入了同步语句，因此是线程安全的，可以用于多线程环境。

Vector实现了Serializable接口，因此它支持序列化，同时实现了Cloneable接口，能被克隆，实现了RandomAccess接口，支持快速随机访问。

Vector继承了AbstractList，实现了List，它是一个队列，因此实现了相应的添加、删除、修改、遍历等功能。

源码基于jdk1.8

1
2
3
4
5
6
7
8
9
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;
    protected int elementCount;
    // 容量增长系数  
    protected int capacityIncrement;
    private static final long serialVersionUID = -2767605614048989439L;
四种构建方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
public Vector() {
        this(10);
    }
 public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }
add方法代码

synchronized boolean add(E e)

void add(int index, E element)

synchronized boolean addAll(Collection<? extends E> c)

synchronized boolean addAll(int index, Collection<? extends E> c)

synchronized void addElement(E obj)

synchronized E set(int index, E element)

synchronized void insertElementAt(E obj, int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
public void add(int index, E element) {
        insertElementAt(element, index);
    }
public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }
public synchronized boolean addAll(Collection<? extends E> c) {
        modCount++;
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);
        System.arraycopy(a, 0, elementData, elementCount, numNew);
        elementCount += numNew;
        return numNew != 0;
    }
public synchronized boolean addAll(int index, Collection<? extends E> c) {
        modCount++;
        if (index < 0 || index > elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);
        int numMoved = elementCount - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        elementCount += numNew;
        return numNew != 0;
    }
public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
public synchronized void setElementAt(E obj, int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        elementData[index] = obj;
    }
public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }
get方法代码

synchronized E get(int index)

synchronized E elementAt(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        return elementData(index);
    }
public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return elementData(index);
    }
remove方法代码

boolean remove(Object o)

synchronized E remove(int index)

synchronized boolean removeElement(Object obj)

synchronized void removeElementAt(int index)

synchronized void removeAllElements()

boolean removeAll(Collection<?> c) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public boolean remove(Object o) {
        return removeElement(o);
    }
public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);
        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--elementCount] = null; // Let gc do its work
        return oldValue;
    }
public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }
public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
}
public synchronized void removeAllElements() {
        modCount++;
        // Let gc do its work
        for (int i = 0; i < elementCount; i++)
            elementData[i] = null;
        elementCount = 0;
    }
public synchronized boolean removeAll(Collection<?> c) {
        return super.removeAll(c);
    }
//AbstractCollection
public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
clear方法代码

void clear()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void clear() {
        removeRange(0, size());
    }
protected synchronized void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = elementCount - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // Let gc do its work
        int newElementCount = elementCount - (toIndex-fromIndex);
        while (elementCount != newElementCount)
            elementData[--elementCount] = null;
}
indexOf方法

int indexOf(Object o)

synchronized int indexOf(Object o, int index) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int indexOf(Object o) {
        return indexOf(o, 0);
    }
public synchronized int indexOf(Object o, int index) {
        if (o == null) {
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
lastIndexOf方法代码

synchronized int lastIndexOf(Object o)

synchronized int lastIndexOf(Object o, int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public synchronized int lastIndexOf(Object o) {
       return lastIndexOf(o, elementCount-1);
   }
public synchronized int lastIndexOf(Object o, int index) {
       if (index >= elementCount)
           throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
       if (o == null) {
           for (int i = index; i >= 0; i--)
               if (elementData[i]==null)
                   return i;
       } else {
           for (int i = index; i >= 0; i--)
               if (o.equals(elementData[i]))
                   return i;
       }
       return -1;
   }
clone方法代码
1
2
3
4
5
6
7
8
9
10
11
12
public synchronized Object clone() {
     try {
         @SuppressWarnings("unchecked")
             Vector<E> v = (Vector<E>) super.clone();
         v.elementData = Arrays.copyOf(elementData, elementCount);
         v.modCount = 0;
         return v;
     } catch (CloneNotSupportedException e) {
         // this shouldn't happen, since we are Cloneable
         throw new InternalError(e);
     }
 }
hashcode方法代码
1
2
3
4
5
6
7
8
9
10
public synchronized int hashCode() {
        return super.hashCode();
    }
//AbstractList<E> 
 public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }
equals方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public synchronized boolean equals(Object o) {
        return super.equals(o);
    }
//AbstractList<E> 
public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;
        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }
listIterator(int index)方法代码

synchronized ListIterator listIterator()

synchronized ListIterator listIterator(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public synchronized ListIterator<E> listIterator() {
        return new ListItr(0);
    }
public synchronized ListIterator<E> listIterator(int index) {
        if (index < 0 || index > elementCount)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
final class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }
        public boolean hasPrevious() {
            return cursor != 0;
        }
        public int nextIndex() {
            return cursor;
        }
        public int previousIndex() {
            return cursor - 1;
        }
        public E previous() {
            synchronized (Vector.this) {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                cursor = i;
                return elementData(lastRet = i);
            }
        }
        public void set(E e) {
            if (lastRet == -1)
                throw new IllegalStateException();
            synchronized (Vector.this) {
                checkForComodification();
                Vector.this.set(lastRet, e);
            }
        }
        public void add(E e) {
            int i = cursor;
            synchronized (Vector.this) {
                checkForComodification();
                Vector.this.add(i, e);
                expectedModCount = modCount;
            }
            cursor = i + 1;
            lastRet = -1;
        }
}

synchronized Iterator iterator()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public synchronized Iterator<E> iterator() {
        return new Itr();
    }
private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        public boolean hasNext() {
            // Racy but within spec, since modifications are checked
            // within or after synchronization in next/previous
            return cursor != elementCount;
        }
        public E next() {
            synchronized (Vector.this) {
                checkForComodification();
                int i = cursor;
                if (i >= elementCount)
                    throw new NoSuchElementException();
                cursor = i + 1;
                return elementData(lastRet = i);
            }
        }
        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            synchronized (Vector.this) {
                checkForComodification();
                Vector.this.remove(lastRet);
                expectedModCount = modCount;
            }
            cursor = lastRet;
            lastRet = -1;
        }
        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            synchronized (Vector.this) {
                final int size = elementCount;
                int i = cursor;
                if (i >= size) {
                    return;
                }
        @SuppressWarnings("unchecked")
                final E[] elementData = (E[]) Vector.this.elementData;
                if (i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
                    action.accept(elementData[i++]);
                }
                // update once at end of iteration to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
其他方法

synchronized int capacity()

boolean contains(Object object)

synchronized boolean containsAll(Collection<?> collection)

synchronized void copyInto(Object[] elements)

Enumeration elements()

synchronized void ensureCapacity(int minimumCapacity)

synchronized E firstElement()

synchronized boolean isEmpty()

synchronized E lastElement()

synchronized boolean retainAll(Collection<?> collection)

synchronized void setSize(int length)

synchronized int size()

synchronized List subList(int start, int end)

synchronized T[] toArray(T[] contents)

synchronized Object[] toArray()

synchronized String toString()

synchronized void trimToSize() 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
public synchronized int capacity() {
        return elementData.length;
    }
public boolean contains(Object o) {
        return indexOf(o, 0) >= 0;
    }
public synchronized boolean containsAll(Collection<?> c) {
        return super.containsAll(c);
    }
//AbstractCollection<E>
public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }
public synchronized void copyInto(Object[] anArray) {
        System.arraycopy(elementData, 0, anArray, 0, elementCount);
    }
 public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;
            public boolean hasMoreElements() {
                return count < elementCount;
            }
            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }
public synchronized void ensureCapacity(int minCapacity) {
        if (minCapacity > 0) {
            modCount++;
            ensureCapacityHelper(minCapacity);
        }
    }
public synchronized E firstElement() {
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(0);
    }
 public synchronized boolean isEmpty() {
        return elementCount == 0;
    }
public synchronized E lastElement() {
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(elementCount - 1);
    }
public synchronized boolean retainAll(Collection<?> c) {
        return super.retainAll(c);
    }
//AbstractCollection<E>
public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
public synchronized void setSize(int newSize) {
        modCount++;
        if (newSize > elementCount) {
            ensureCapacityHelper(newSize);
        } else {
            for (int i = newSize ; i < elementCount ; i++) {
                elementData[i] = null;
            }
        }
        elementCount = newSize;
    }
public synchronized int size() {
        return elementCount;
    }
public synchronized List<E> subList(int fromIndex, int toIndex) {
        return Collections.synchronizedList(super.subList(fromIndex, toIndex),
                                            this);
    }
//AbstractList<E>
public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }
public synchronized Object[] toArray() {
        return Arrays.copyOf(elementData, elementCount);
    }
@SuppressWarnings("unchecked")
public synchronized <T> T[] toArray(T[] a) {
        if (a.length < elementCount)
            return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
        System.arraycopy(elementData, 0, a, 0, elementCount);
        if (a.length > elementCount)
            a[elementCount] = null;
        return a;
    }
 public synchronized String toString() {
        return super.toString();
    }
//AbstractCollection<E> 
public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }
public synchronized void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (elementCount < oldCapacity) {
            elementData = Arrays.copyOf(elementData, elementCount);
        }
    }

Stack

​ Stack（栈）是以栈的形式来存储数据，其特点是先进后出（FILO），同时Stack继承与Vector，所以如果把Stack内部的实现也是通过动态数组来实现的、而不是其他的数据结构。在List体系中有个LinkedList是以双向链表的数据结构来存储数据的，使用LinkedList完全可以达到Stack的效果、但是Stack不能作为双向链表来使用，并且LinkedList不是线程安全的、而Stack是线程安全的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public
class Stack<E> extends Vector<E> 
    public Stack() {
    }
    public E push(E item) {
        addElement(item);
        return item;
    }
    public synchronized E pop() {
        E  obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
    public synchronized E peek() {
        int  len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    public boolean empty() {
        return size() == 0;
    }
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

Queue接口概览

是一个泛型接口，父接口：Collection，子接口：Deque。

1
2
3
4
5
6
7
8
public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

boolean add(E e)和 boolean offer(E e)调用相同。

E element()和E peek()获取但不移除失败时，element抛出异常，peek()返回null

E remove()和E poll()获取并移除失败时，remove()抛出异常，poll()返回null

Deque 双端队列，可以实现队列，也可以用作栈。

Set接口概览

​ 存入Set的每个元素必须是惟一的，因为Set不保存重复元素。加入Set的元素重新必须定义equals()方法和hashcode()方法以确保对象的唯一性。Set不保证维护元素的次序，Set与Collection有完全一样的接口。

HashSet

初始化代码

​ HashSet继承了AbstractSet，实现了Set接口。其实AbstractSet已经实现Set接口了。AbstractSet继承自AbstractCollection，而AbstractCollection实现了Collection接口的部分方法，而Set接口和Collection接口完全一致，所以AbstractSet只是实现了AbstractCollection没有实现的Set接口的方法和重写了部分AbstractCollection已经实现的方法。对于HashSet中保存的对象，请注意正确重写其equals和hashCode方法，以保证放入的对象的唯一性。

1
2
3
4
5
6
7
8
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;//底层使用HashMap来保存HashSet中所有元素。
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();//定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final
五种构建方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public HashSet() {
        map = new HashMap<>();
    }
public HashSet(Collection<? extends E> c) {
        //实际底层使用默认的加载因子0.75和足以包含指定collection中所有元素的初始容量来创建一个HashMap。
        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);
    }
//以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
//此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
add方法代码

boolean add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
 /** 
 * 底层实际将将该元素作为key放入HashMap。 
 * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
 * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， 
 * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， 
 * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， 
 * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。 
 * @param e 将添加到此set中的元素。 
 * @return 如果此set尚未包含指定元素，则返回true。 
 */  
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
get方法代码

通过Iterator遍历HashSet

1
2
3
public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
1
2
3
4
5
6
7
8
9
10
11
12
public class test1 {
	public static void main(String[] args) {
		Set<String> set = new HashSet<String>(12,1);
		set.add("a");
		set.add("b");
		set.add("c");
		Iterator<String> iterator = set.iterator();
		while(iterator.hasNext()){
			System.out.println(iterator.next());
		}
	}
}
remove方法代码
1
2
3
public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
clear方法代码
1
2
3
4
5
6
7
/**
     * Removes all of the elements from this set.
     * The set will be empty after this call returns.
     */
    public void clear() {
        map.clear();
    }
clone()方法代码
1
2
3
4
5
6
7
8
9
10
@SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }
writeObject和readObject方法代码

void writeObject(java.io.ObjectOutputStream s)

void readObject(java.io.ObjectInputStream s) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();
        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }
        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }
        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);
        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }
其他方法

size()方法

1
2
3
public int size() {
        return map.size();
    }

isEmpty()方法

1
2
3
public boolean isEmpty() {
       return map.isEmpty();
   }

contains(Object)方法

1
2
3
public boolean contains(Object o) {
        return map.containsKey(o);
    }

LinkedHashSet

LinkedHashSet会调用HashSet的父类构造函数，让其底层实现为LinkedHashMap，这样就很好的实现了LinkedHashSet所需要的功能。

初始化代码
1
2
3
4
5
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = -2851667679971038690L;
四种构建方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
 public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
 public LinkedHashSet() {
        super(16, .75f, true);
    }
 public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
//super调用的是LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet

TreeSet底层实现严重依赖于TreeMap。

未完待续

Collections与Arrays工具类

Collection是一个接口，它是Set、List等容器的父接口；Collections是一个工具类，提供了一系列的静态方法来辅助容器操作，这些方法包括对容器的搜索、排序、线程安全化等等。

Collections的常用方法

sort排序
1
2
public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list,Comparator<? super T> c)

由此可以看出我们有两种方式排序，list中的对象实现Comparable接口以及根据Collections.sort重载方法来实现。

list中的对象实现Comparable接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
//String 本身含有compareTo方法，所以可以直接调用sort方法
public class SortTest {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> listS = new ArrayList<String>();
		listS.add("abd");
		listS.add("abc");
		System.out.println(listS.toString());
		Collections.sort(listS);
		System.out.println(listS.toString());
	}
}
//[abd, abc]
//[abc, abd]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortTest {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Student st1 =new Student("mm",29);
		Student st2 =new Student("tt",24);
		List<Student> listS = new ArrayList<Student>();
		listS.add(st1);
		listS.add(st2);
		System.out.println(listS.toString());
		Collections.sort(listS);
		System.out.println(listS.toString());
	}
}
class Student implements Comparable<Student>{
	private String name;
	private Integer age;
	public Student(String name, Integer  age) {
		this.name = name;
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public Integer  getAge() {
		return age;
	}
	@Override
	public String toString(){
		return "name: " + this.name +" age: " + this.age;
	}
	@Override
	public int compareTo(Student o) {
		// TODO Auto-generated method stub
		return this.age.compareTo(o.getAge());
	}	
}
//[name: mm age: 29, name: tt age: 24]
//[name: tt age: 24, name: mm age: 29]

根据Collections.sort重载方法来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class SortTest {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Student st1 =new Student("mm",29);
		Student st2 =new Student("tt",24);
		List<Student> listS = new ArrayList<Student>();
		listS.add(st1);
		listS.add(st2);
		System.out.println(listS.toString());
		Collections.sort(listS,new Mycompare());
		System.out.println(listS.toString());
	}
}
class Student{
	private String name;
	private Integer age;
	public Student(String name, Integer  age) {
		this.name = name;
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public Integer  getAge() {
		return age;
	}
	@Override
	public String toString(){
		return "name: " + this.name +" age: " + this.age;
	}
	
}
class Mycompare implements Comparator<Student> {
	@Override
	public int compare(Student arg0, Student arg1) {
		// TODO Auto-generated method stub
		return arg0.getAge().compareTo(arg1.getAge());
	}	
}
//[name: mm age: 29, name: tt age: 24]
//[name: tt age: 24, name: mm age: 29]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class SortTest {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Student st1 =new Student("mm",29);
		Student st2 =new Student("tt",24);
		List<Student> listS = new ArrayList<Student>();
		listS.add(st1);
		listS.add(st2);
		System.out.println(listS.toString());
		Collections.sort(listS,new Comparator<Student>() {
			@Override
			public int compare(Student o1, Student o2) {
				// TODO Auto-generated method stub
				return o1.getAge().compareTo(o2.getAge());
			}
		});
		System.out.println(listS.toString());
	}
}
class Student{
	private String name;
	private Integer age;
	public Student(String name, Integer  age) {
		this.name = name;
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public Integer  getAge() {
		return age;
	}
	@Override
	public String toString(){
		return "name: " + this.name +" age: " + this.age;
	}	
}
//[name: mm age: 29, name: tt age: 24]
//[name: tt age: 24, name: mm age: 29]
shuffle 随机排序
1
2
public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)
binarySearch

查找指定集合中的元素，返回所查找元素的索引

1
2
3
4
5
6
public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
                                   T key)
public static <T> int binarySearch(List<? extends T> list,
                                   T key,
                                   Comparator<? super T> c)
max
1
2
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp)
min
1
2
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll,Comparator<? super T> comp)
indexOfSubList

查找subList在list中首次出现位置的索引

1
public static int indexOfSubList(List<?> source,List<?> target)
lastIndexOfSubList

同上

replaceAll

替换批定元素为某元素,若要替换的值存在刚返回true,反之返回false

1
public static <T> boolean replaceAll(List<T> list,T oldVal,T newVal)
reverse

反转集合中元素的顺序

1
public static void reverse(List<?> list)
rotate

集合中的元素向后移m个位置，在后面被遮盖的元素循环到前面来

1
public static void rotate(List<?> list, int distance)
copy

将集合n中的元素全部复制到m中,并且覆盖相应索引的元素

1
public static <T> void copy(List<? super T> dest, List<? extends T> src)
swap

交换集合中指定元素索引的位置

1
public static void swap(List<?> list,int i,int j)
fill
1
public static <T> void fill(List<? super T> list, T obj)
nCopies

返回大小为n的List，List不可改变,其中的所有引用都指向o

1
public static <T> List<T> nCopies(int n, T o)

Arrays常用方法

asList方法
1
2
3
4
5
@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
binarySearch方法

binarySearch方法支持在整个数组中查找

1
int index = Arrays.binarySearch(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 6);

在某个区间范围内查找

1
2
3
4
5
6
public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                   int key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }
int index = Arrays.binarySearch(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 1, 6, 6);
copyOf及copyOfRange方法
sort方法
toString方法
deepToString方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;
public class test8 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] stuGrades = { { 80, 81, 82 }, { 84, 85, 86 }, { 87, 88, 89 } };		
		System.out.println(Arrays.toString(stuGrades));
		System.out.println(Arrays.deepToString(stuGrades));		
		Stu stu1 = new Stu("aa",20);
		Stu stu2 = new Stu("bb",24);	
		Stu[][] stus ={{stu1,stu2},{stu1,stu1}};
		System.out.println(Arrays.toString(stus));
		System.out.println(Arrays.deepToString(stus));
	}
}
class Stu{
	private String name;
	private int age;	
	public Stu(String name , int age) {
		this.name = name;
		this.age = age;
	}
	@Override
	public String toString(){
		return "{name: " + name + " age: " + age+"}";
	}	
}
//output
[[I@2a139a55, [I@15db9742, [I@6d06d69c]
[[80, 81, 82], [84, 85, 86], [87, 88, 89]]
[[Ltest1.Stu;@4e25154f, [Ltest1.Stu;@70dea4e]
[[{name: aa age: 20}, {name: bb age: 24}], [{name: aa age: 20}, {name: aa age: 20}]]
equals方法
deepEquals方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;
public class test8 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[][] name1 = {{ "G","a","o" },{ "H","u","a","n"},{ "j","i","e"}};  
        String[][] name2 = {{ "G","a","o" },{ "H","u","a","n"},{ "j","i","e"}};  
        System.out.println(Arrays.equals(name1, name2));    // false  
        System.out.println(Arrays.deepEquals(name1, name2));// true       
        String[] name3 = {"G","a","o","H","u","a","n","j","i","e"};  
        String[] name4 = {"G","a","o","H","u","a","n","j","i","e"};  
        System.out.println(Arrays.equals(name3, name4));      // true  
        System.out.println(Arrays.deepEquals(name3, name4));  // true  
	}
}
fill方法
1
2
3
4
5
6
7
8
9
public class test8 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] stu = new int [8];
		System.out.println(Arrays.toString(stu));//[0, 0, 0, 0, 0, 0, 0, 0]
		Arrays.fill(stu,1);
		System.out.println(Arrays.toString(stu));//[1, 1, 1, 1, 1, 1, 1, 1]
	}
}

Map接口概览

​ Map一次存一对元素, Collection 一次存一个。Map 的键不能重复，保证唯一。Map 一次存入一对元素，是以键值对的形式存在。键与值存在映射关系，一定要保证键的唯一性。

Map接口常用方法

1、添加：

1
2
put(K key, V value) //可以相同的key值，但是添加的value值会覆盖前面的，返回值是前一个，如果没有就返回null。 
putAll(Map<? extends K,? extends V> m) // 从指定映射中将所有映射关系复制到此映射中（可选操作）。

2、删除

1
2
remove(Object key) //删除关联对象，指定key对象
clear() //清空集合对象

3、获取

1
get(key) //可以用于判断键是否存在的情况。当指定的键不存在的时候，返回的是null。

3、判断：

1
2
3
boolean isEmpty()//长度为0返回true否则false
boolean containsKey(Object key)//判断集合中是否包含指定的key
boolean containsValue(Object value)//判断集合中是否包含指定的value

4、长度：

1
int size()

5、遍历Map的方式：

1
2
3
4
5
6
7
//1、将map集合中所有的键取出存入set集合。
Set<K> keySet() //返回所有的key对象的Set集合，再通过get方法获取键对应的值。
//2、values()，获取所有的值。
Collection<V> values() //不能获取到key对象
//3、Map.Entry对象(推荐使用)重点
Set<Map.Entry<k,v>> entrySet()//将map 集合中的键值映射关系打包成一个对象。
Map.Entry//对象通过Map.Entry 对象的getKey，getValue获取其键和值。

HashMap

​ Java8的HashMap对之前做了较大的优化，其中最重要的一个优化就是桶中的元素不再唯一按照链表组合，也可以使用红黑树进行存储，总之，目标只有一个，那就是在安全和功能性完备的情况下让其速度更快，提升性能。

初始化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
  	// 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   	// 最大容量 
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
  	// 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
 	// 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 填充因子
    final float loadFactor;
四种构建方法

HashMap(int, float)

HashMap(int)

HashMap()

HashMap(Map<? extends K>)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否则报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 初始容量不能大于最大值，否则为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 填充因子不能小于或等于0，不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    // 初始化填充因子                                        
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);    
}
//返回大于initialCapacity的最小的二次幂数值
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
public HashMap(int initialCapacity) {
    // 调用HashMap(int, float)型构造函数
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    // 初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
//putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}
put方法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
  // table未初始化或者长度为0，进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
  //确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
          // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
              // 将第一个元素赋值给e，用e来记录
                e = p;
           // hash值不相等，即key不相等；为红黑树结点
            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);
                      // 结点数量达到阈值，转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                     // 跳出循环 
                        break;
                    }
                    //判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                      // 相等，跳出循环
                        break;
                   // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //onlyIfAbsent为false或者旧值为null,用新值替换旧值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
               // 访问后回调
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
//通过hashCode()的高16位异或低16位实现,这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//扩容机制
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;
            }
          // 容量翻倍，使用左移，效率更高
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
  		// oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
  	    // 新阈值为0
        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;
        if (oldTab != null) {
          // 复制元素，重新进行hash
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                      // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
                        do {
                            next = e.next;
                            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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
get方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
          // 桶中第一项(数组元素)相等
            if (first.hash == hash && // always check first node
                ((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;
    }
remove方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
  // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
clear方法代码
1
2
3
4
5
6
7
8
9
public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }
clone方法代码
1
2
3
4
5
6
7
8
9
10
11
12
public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }
其他方法

略

LinkedHashMap

​ 我们需要按照元素插入的顺序来访问元素，此时，LinkedHashMap就派上用场了。LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。除了可以保迭代历顺序，这种结构还有一个好处：迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。

初始化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LinkedHashMap<K,V>  extends HashMap<K,V> implements Map<K,V> {
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    // 版本序列号
    private static final long serialVersionUID = 3801124242820219131L;
    // 链表头结点
    transient LinkedHashMap.Entry<K,V> head;
    // 链表尾结点
    transient LinkedHashMap.Entry<K,V> tail;
    // 访问顺序
    final boolean accessOrder;
}
五种构建方法

LinkedHashMap(int, float)

LinkedHashMap(int)

LinkedHashMap()

LinkedHashMap(Map<? extends K, ? extends V>)

LinkedHashMap(int, float, boolean)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
}
public LinkedHashMap() {
        super();
        accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}//可以指定accessOrder的值，从而控制访问顺序
未完待续

HashTable

初始化代码
1
2
3
4
5
6
7
8
9
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    private transient Entry<?,?>[] table;
    private transient int count;
    private int threshold;// 阈值，用于判断是否需要调整Hashtable的容量
    private float loadFactor;// 加载因子
    private transient int modCount = 0;
    private static final long serialVersionUID = 1421746759512286392L;
四种构建方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
    }
    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);
    }
    public synchronized void putAll(Map<? extends K, ? extends V> t) {
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }
put方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 = key.hashCode();// //在此处计算key的hash值，如果此处key为null，则直接抛出空指针异常。
        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;
    }
private void addEntry(int hash, K key, V value, int index) {
        modCount++;
        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }
get方法代码
1
2
3
4
5
6
7
8
9
10
11
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}
remove方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
        for(Entry<K,V> 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;
    }
clear方法代码
1
2
3
4
5
6
7
public synchronized void clear() {
       Entry<?,?> tab[] = table;
       modCount++;
       for (int index = tab.length; --index >= 0; )
           tab[index] = null;
       count = 0;
   }
clone方法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public synchronized Object clone() {
        try {
            Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
            t.table = new Entry<?,?>[table.length];
            for (int i = table.length ; i-- > 0 ; ) {
                t.table[i] = (table[i] != null)
                    ? (Entry<?,?>) table[i].clone() : null;
            }
            t.keySet = null;
            t.entrySet = null;
            t.values = null;
            t.modCount = 0;
            return t;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

TreeMap

TreeMap底层使用的数据结构是红黑树，HashMap在达到一定阈值时候会使用红黑树。

未完待续

Iterator接口概览

Iterator接口也是Java集合框架的成员，主要用于遍历（即迭代访问）Collection集合中的元素，Iterator对象也被称为迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }//这是Java 8为Iterator新增的默认方法，该方法可使用Lambda表达式来遍历集合元素
}

Comparable接口概览

在Java集合框架里面，各种集合的操作很大程度上都离不开Comparable和Comparator，虽然它们与集合没有显示的关系，但是它们只有在集合里面的时候才能发挥最大的威力。

Comparable

1
2
3
public interface Comparable<T>{
  public int compareTo(T o);
}

Comparator

1
2
3
4
5
public interface Comparator<T>{
  int compare(T o1, T o2);
  boolean equals(Object obj);
  .....//其他是1.8扩展的
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Person implements Comparable {
	     String name;
	     int age;
		public Person(String name, int age) {
			this.name = name;
			this.age = age;
		}
		@Override
		public int compareTo(Object o) {
			// TODO Auto-generated method stub
			Person another =(Person)o;
			int i = this.name.compareTo(another.name);
			if(i== 0){
				return age - another.age;
			}else{
				return i;
			}
		}
		
		
	@Override
		public String toString() {
			return "Person [name=" + name + ", age=" + age + "]";
		}
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Person p1 =new Person("a",20);
		Person p2 =new Person("a",12);
		List<Person> list = new ArrayList<Person>();
		list.add(p1);
		list.add(p2);
		Collections.sort(list);
		System.out.println(Arrays.deepToString(list.toArray()));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Person {
	     String name;
	     int age;
		public Person(String name, int age) {
			this.name = name;
			this.age = age;
		}	
	@Override
		public String toString() {
			return "Person [name=" + name + ", age=" + age + "]";
		}
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Person p1 =new Person("a",20);
		Person p2 =new Person("a",12);
		List<Person> list = new ArrayList<Person>();
		list.add(p1);
		list.add(p2);
		Collections.sort(list,new MyComparator());
		System.out.println(Arrays.deepToString(list.toArray()));
	}
}
class MyComparator implements Comparator<Person> {
	// TODO Auto-generated method stub
	@Override
	public int compare(Person o1, Person o2) {
		// TODO Auto-generated method stub
		int i = o1.name.compareTo(o2.name);
		if(i== 0){
			return o1.age - o2.age;
		}else{
			return i;
		}
	}
}
Luckylau wechat
如果对您有价值,看官可以打赏的！