//容量检查 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }//容量确认 private void ensureExplicitCapacity(int minCapacity) { modCount++; //判断是否需要扩容，数组中的元素个数-数组长度，如果大于 0 表明需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }/*** Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. ** @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //扩容 1.5 倍 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); }3.5 Vector 容器类

Vector 底层是用数组实现的，相关的方法都加了同步检查，因此“线程安全,效率低”。比如，indexOf 方法就增加了 synchronized 同步标记。

Vector 的使用：

Vector 的使用与 ArrayList 是相同的，因为他们都实现了 List 接口，对 List 接口中的抽象方法做了具体实现。

package cn.pxy.generics;import java.util.List;import java.util.Vector;public class VectorTest {public static void main(String<> args) {//实例化VectorList<String> v=new Vector<>();v.add("a");v.add("b");v.add("c");for(int i=0;i<v.size();i++) {System.out.println(v.get(i));}System.out.println("***********");for(String str:v) {System.out.println(str);}}}运行结果：

Vector 源码分析：

初始化容器：

/*** The array buffer into which the components of the vector are * stored. The capacity of the vector is the length of this array buffer, * and is at least large enough to contain all the vector's elements.** <p>Any array elements following the last element in the Vector are null. ** @serial */ protected Object<> elementData;public Vector() { this(10); /** * Constructs an empty vector with the specified initial capacity and * capacity increment. * * @param initialCapacity the initial capacity of the vector * @param capacityIncrement the amount by which the capacity is * increased when the vector overflows * @throws IllegalArgumentException if the specified initial capacity * is negative */ public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object; this.capacityIncrement = capacityIncrement; }添加元素：

/** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector * @return {@code true} (as specified by {@link Collection#add}) * @since 1.2 */ public synchronized boolean add(E e) { modCount++; add(e, elementData, elementCount); return true; }数组扩容：

/*** This implements the unsynchronized semantics of ensureCapacity. * Synchronized methods in this class can internally call this* method for ensuring capacity without incurring the cost of an * extra synchronization. ** @see #ensureCapacity(int) */ private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code //判断是否需要扩容，数组中的元素个数-数组长度，如果大于 0 表明需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //扩容 2 倍 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); }3.6 Stack 容器

Stack 栈容器，是 Vector 的一个子类，它实现了一个标准的后进先出(LIFO：Last In Frist Out)的栈。

Stack 特点是：后进先出。它通过 5 个操作方法对 Vector 进行扩展，允许将向量视为堆栈。

操作栈的方法：

Modifier and Type

Method and Description

boolean

empty（）测试如果这个栈是不是空的

E

peek（）用于从此Stack中返回顶部元素

E

pop()删除这个栈堆的顶部的对象，并返回该对象的值函数

E

push（E item）把一个项目推到栈堆的顶部

int

search（Object o）传入一个对象,然后从上往下找到第一个该元素并返回该索引。

Stack 的使用

package cn.pxy.generics;import java.util.Stack;public class StackTest {public static void main(String<> args) {//实例化栈容器Stack<String> stack=new Stack<>();//将元素添加到栈容器，后进先出stack.push("a");stack.push("b");stack.push("c");//判断栈容器是否为空System.out.println("栈容器是否为空："+stack.empty());//查看栈顶元素System.out.println(stack.peek());//返回元素在栈容器中的元素System.out.println(stack.search("c"));//获取栈容器中的栈顶元素,返回并从栈里删除String p1=stack.pop();System.out.println(p1);String p2=stack.pop();System.out.println(p2);String p3=stack.pop();System.out.println(p3);System.out.println("栈容器是否为空："+stack.empty());}}运行结果：

示例：判断元素的对称性String str="...{.....<....(....)...>....}..(....)..<...>...";

package cn.pxy.generics;import java.util.Stack;public class StackTest {public static void main(String<> args) {symmetry();}//匹配符号的对称性public static void symmetry() {String str="...{.....<....(....)...>....}..(....)..<...>...";//实例化StackStack<String> stack=new Stack<>();//假设修正法boolean flag=true;//假设是匹配的//拆分字符串获取字符for(int i=0;i<str.length();i++) {char c=str.charAt(i);if(c=='{') {stack.push("}");}if(c=='<') {stack.push(">");}if(c=='(') {stack.push(")");}//判断符号是否匹配if(c=='}'||c=='>'||c==')') {if(stack.empty()) {//修正处理flag=false;break;}String x=stack.pop();if(x.charAt(0)!=c) {//修正处理flag=false;}System.out.println(flag);}}}}运行结果：

运行分析：利用循环将字符赋给c，再判断c的值，如果c是“（”就将它的对称符号“）”推入栈中，如果c是“）”，则将栈顶元素返回赋给x，并将该元素从栈中删除，如果c==x，就说明这个符号对称，同理，如果最后flag=true，说明符号全部对称。

3.7 LinkedList 容器类

LinkedList 底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

双向链表介绍

class Node<E>{E ietm; Node<E> next;Node<E> prev;}LinkedList 的使用（List 标准）

LinkedList 实现了 List 接口，所以 LinkedList 是具备 List 的存储特征的(有序，元素有重复)。

package cn.pxy.generics;import java.util.LinkedList;import java.util.List;public class LinkedListTest {public static void main(String<> args) {List<String> list=new LinkedList<>();//添加元素list.add("a");list.add("b");list.add("c");list.add("a");//获取元素for(int i=0;i<list.size();i++) {System.out.print(list.get(i)+"");}System.out.println();System.out.println("----------");for(String str:list) {System.out.print(str+"");}}}运行结果：

LinkedList 的使用（非 List 标准）

方法

说明

void addFirst(E e)

将指定元素插入到开头

void addLast(E e)

将指定元素插入到结尾

getFirst()

返回此列表的第一个元素

removeFirst()

移除此列表中的第一个元素，并返回这个元素

removeLast()

移除此列表中的最后一个元素，并返回这个元素

E pop()

从此列表所表示的堆栈处弹出一个元素，等效于removeFirst

void push(E e)

将元素推入此列表所在的栈堆，等效于addFirst（E e）

boolean isEmpty()

判断列表是否包含元素，如果不包含元素则返回true

package cn.pxy.generics;import java.util.LinkedList;public class LinkedListTest {public static void main(String<> args) {LinkedList<String> list=new LinkedList<>();list.add("a");list.add("b");list.add("c");for(String str:list) {System.out.println(str);}System.out.println("---------------");System.out.println(list.getFirst());System.out.println(list.getLast());System.out.println("------------------");list.removeFirst();list.removeLast();for(String str:list) {System.out.println(str);}System.out.println("----------------");list.add("c");list.pop();for(String str:list) {System.out.println(str);}System.out.println("---------------");list.push("h");for(String str:list) {System.out.println(str);}System.out.println(list.isEmpty());}}运行结果：

LinkedList 源码分析

节点类：

private static class Node<E>{E ietm;Node<E> next;Node<E> prev;Node(Node<E> prev,E element,Node<E> next){this.ietm=element;this.next=next;this.prev=prev;}}成员变量：

transient int size = 0; /** * Pointer to first node. */ transient Node<E> first; /** * Pointer to last node. */ transient Node<E> last;添加元素：

/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; }/** * Links e as last element. */ 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++; }头尾添加元素：

addFirst：

/** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); }/** * Links e as first element. */ 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++; }addLast：

/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { linkLast(e); }在指定位置添加元素：

/** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ 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)); }/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }/** * Inserts element e before non-null Node succ. */ 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++; }获取元素：

/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; }private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }/** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size; }删除指定位置元素：

/** * Removes the element at the specified position in this list. Shifts any * subsequent elements to the left (subtracts one from their indices). * Returns the element that was removed from the list. * * @param index the index of the element to be removed * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }/** * Unlinks non-null node x. */ 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; }3.8 Set 接口介绍

Set 接口继承自 Collection，Set 接口中没有新增方法，方法和 Collection 保持完全一致。我们在前面通过 List 学习的方法，在 Set 中仍然适用。因此，学习 Set 的使用将没有任何难度。

Set 接口特点：无序、不可重复。无序指 Set 中的元素没有索引，我们只能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新元素如果和 Set 中某个元素通过 equals()方法对比为 true，则只能保留一个。Set 常用的实现类有：HashSet、TreeSet 等，我们一般使用 HashSet。

HashSet 容器类：

HashSet 是一个没有重复元素的集合，不保证元素的顺序。而且 HashSet 允许有 null 元素。HashSet 是采用哈希算法实现，底层实际是用 HashMap 实现的（HashSet 本质就是一个简化版的 HashMap），因此，查询效率和增删效率都比较高。

Hash算法原理（也称为散列算法）：

模9运算：把26、15、22、24通过模9存放如容器中，步骤为：26除9余8，所以26放在索引为8的位置；15除9余6，所以15放在索引为6的位置；22除9余4，所以22放在索引为4的位置；24除9,余6，所以24放在索引为6的位置，但是索引为6的位置不为空，所以24向后移，直到找到一个空的位置（7）。

HashSet 的使用：

package cn.pxy.generics;import java.util.HashSet;import java.util.Set;public class HashSetTest {public static void main(String<> args) {//实例化HashSetSet<String> set=new HashSet<>();//添加元素set.add("a");set.add("b");set.add("c");set.add("d");set.add("a");//获取元素，由于在Set容器中没有索引，所以没有对应的get（int index）方法for(String str:set) {System.out.println(str);}System.out.println("---------------");//删除元素boolean flag=set.remove("c");System.out.println(flag);for(String str:set) {System.out.println(str);}System.out.println("**********");int size=set.size();System.out.println(size);}}运行结果：

HashSet 存储特征分析：

HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程不安全的。HashSet允许有 null 元素。

无序：在 HashSet 中底层是使用 HashMap 存储元素的。HashMap 底层使用的是数组与链表实现元素的存储。元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。

不重复：当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的 equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素。

通过 HashSet 存储自定义对象：

创建User对象：

package cn.pxy.generics;public class Users {private String username;private int userage;public Users(String username,int userage) {this.username=username;this.userage=userage;}public Users() {}/** * HashMap存储是不允许有重复值的，equals方法是通过hash取模16的值是否 * 相同来判断对象是否相同，为了能够准确的识别对象是否相同，这里重写 * equals方法。 */@Overridepublic boolean equals(Object obj) {System.out.println("equals...");//测试equals方法有没有执行if(this==obj) {return true;}if(obj==null||getClass()!=obj.getClass()) {return false;}Users users=(Users)obj;if(userage!=users.userage) {return false;}return username!=null?username.equals(users.username):users.username==null;}@Overridepublic int hashCode() {int result=username!=null?username.hashCode():0;result=31*result+userage;return result;}public String getUsername() {return username;}public void setUsername(String username) {this.username = username;}public int getUserage() {return userage;}public void setUserage(int userage) {this.userage = userage;}@Overridepublic String toString() {return "Users{"+"username='"+username+'\''+",userage="+userage+'}';}}在 HashSet 中存储 Users 对象：

package cn.pxy.generics;import java.util.HashSet;import java.util.Set;public class HashSetTest {public static void main(String<> args) {//实例化HashSetSet<Users> set=new HashSet<>();Users u1=new Users("胖咸鱼",18);Users u2=new Users("pxy",18);Users u3=new Users("胖咸鱼",18);set.add(u1);set.add(u2);set.add(u3);System.out.println(u1.hashCode());System.out.println(u2.hashCode());System.out.println(u3.hashCode());for(Users users:set) {System.out.println(users);}}}运行结果：

HashSet 底层源码分析：

成员变量：

private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();添加元素：

/** * Adds the specified element to this set if it is not already present. * More formally, adds the specified element {@code e} to this set if * this set contains no element {@code e2} such that * {@code Objects.equals(e, e2)}. * If this set already contains the element, the call leaves the set * unchanged and returns {@code false}. * * @param e element to be added to this set * @return {@code true} if this set did not already contain the specified * element */ public boolean add(E e) { return map.put(e, PRESENT)==null; }TreeSet 容器类：TreeSet 是一个可以对元素进行排序的容器。底层实际是用 TreeMap 实现的，内部维持了一个简化版的 TreeMap，通过 key 来存储 Set 的元素。 TreeSet 内部需要对存储的元素进行排序，因此，我们需要给定排序规则。

排序规则实现方式：1.通过元素自身实现比较规则；2.通过比较器指定比较规则。

TreeSet 的使用：

package cn.pxy.generics;import java.util.Set;import java.util.TreeSet;public class TreeSetTest {public static void main(String<> args) {//实例化TreeSetSet<String> set=new TreeSet<>();//添加元素set.add("c");set.add("a");set.add("d");set.add("b");set.add("a");//获取元素for(String str:set) {System.out.println(str);}}}运行结果：

通过元素自身实现比较规则：在元素自身实现比较规则时，需要实现 Comparable 接口中的 compareTo 方法，该方法中用来定义比较规则。TreeSet 通过调用该方法来完成对元素的排序处理。

创建Users类：

package cn.pxy.test;public class Users implements Comparable<Users>{private String username;private int userage;public Users(String username,int userage) {this.username=username;this.userage=userage;}public Users() {}@Overridepublic boolean equals(Object o) {System.out.println("equals...");if(this==o) {return true;}if(o==null||getClass()!=o.getClass()) {return false;}Users users=(Users) o;if(userage!=users.userage) {return false;}return username!=null?username.equals(users.username):users.username==null;}@Overridepublic int hashCode() {int result=username!=null?username.hashCode():0;result=31*result+userage;return result;}public String getUsername() {return username;}public void setUsername(String username) {this.username = username;}public int getUserage() {return userage;}public void setUserage(int userage) {this.userage = userage;}@Overridepublic String toString() {return "Users{"+"username='"+username+'\''+",userage="+userage+'}';}//定义比较规则//正数：大；负数：小；0：相等@Overridepublic int compareTo(Users o) {if(this.userage>o.getUserage()) {return 1;}if(this.userage==o.getUserage()) {return this.username.compareTo(o.getUsername());}return -1;}}在TreeSet中存放Users对象：

package cn.pxy.test;import java.util.Set;import java.util.TreeSet;public class Test {public static void main(String<> args) {Set<Users> set=new TreeSet<>();Users u1=new Users("胖咸鱼",18);Users u2=new Users("张三",21);Users u3=new Users("李四",21);set.add(u1);set.add(u2);set.add(u3);for(Users user:set) {System.out.println(user);}}}运行结果：

通过比较器实现比较规则：通过比较器定义比较规则时，我们需要单独创建一个比较器，比较器需要实现Comparator 接口中的 compare 方法来定义比较规则。在实例化 TreeSet 时将比较器对象交给TreeSet 来完成元素的排序处理。此时元素自身就不需要实现比较规则了。

创建比较器：

package cn.pxy.test;import java.util.Comparator;public class StudentComparator implements Comparator<Student>{public int compare(Student o1,Student o2) {if(o1.getAge()>o2.getAge()) {return 1;}if(o1.getAge()==o2.getAge()) {return o1.getName().compareTo(o2.getName());}return -1;}}创建Student类：

package cn.pxy.test;public class Student {private String name;private int age;public Student(String name,int age) {this.name=name;this.age=age;}public Student() {}@Overridepublic String toString() {return "Student {" + "name='" + name + '\'' + ", age=" + age + '}';}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object obj) {if(this==obj) {return true;}if(obj==null||getClass()!=obj.getClass()) {return false;}Student student=(Student) obj;if(age!=student.age) {return false;}return name!=null?name.equals(student.name):student.name==null;}@Overridepublic int hashCode() {int result=name!=null?name.hashCode():0;result=31*result+age;return result;}}在TreeSet中存储Student对象：

package cn.pxy.test;import java.util.Set;import java.util.TreeSet;public class Test2 {public static void main(String<> args) {Set<Student> set=new TreeSet<>(new StudentComparator());Student s1=new Student("胖咸鱼",18);Student s2=new Student("胖咸鱼先生",21);Student s3=new Student("胖咸鱼吖",21);set.add(s1);set.add(s2);set.add(s3);for(Student student:set) {System.out.println(student);}}}运行结果：

TreeSet 底层源码分析：

成员变量：

/** * Constructs a new, empty tree set, sorted according to the * natural ordering of its elements. All elements inserted into * the set must implement the {@link Comparable} interface. * Furthermore, all such elements must be <i>mutually * comparable</i>: {@code e1.compareTo(e2)} must not throw a * {@code ClassCastException} for any elements {@code e1} and * {@code e2} in the set. If the user attempts to add an element * to the set that violates this constraint (for example, the user * attempts to add a string element to a set whose elements are * integers), the {@code add} call will throw a * {@code ClassCastException}. */ public TreeSet() { this(new TreeMap<>()); }添加元素：

/** * Adds the specified element to this set if it is not already present. * More formally, adds the specified element {@code e} to this set if * the set contains no element {@code e2} such that * {@code Objects.equals(e, e2)}. * If this set already contains the element, the call leaves the set * unchanged and returns {@code false}. * * @param e element to be added to this set * @return {@code true} if this set did not already contain the specified * element * @throws ClassCastException if the specified object cannot be compared * with the elements currently in this set * @throws NullPointerException if the specified element is null * and this set uses natural ordering, or its comparator * does not permit null elements */ public boolean add(E e) { return m.put(e, PRESENT)==null; }3.9 单例集合使用案例

案例：产生【1,10】之间的随机数，将十个不重复的数放入容器中：

package cn.pxy.test;//使用List类型容器实现import java.util.ArrayList;import java.util.List;public class Test3 {public static void main(String<> args) {List<Integer> list=new ArrayList<>();while(true){//产生随机数int num=(int) (Math.random()*10+1);//判断容器中是否存在该数值if(!list.contains(num)) {list.add(num);}//结束循环if(list.size()==10) {break;}}for(Integer i:list) {System.out.println(i);}}}

package cn.pxy.test;//使用Set类型容器实现import java.util.HashSet;import java.util.Set;public class Test3 {public static void main(String<> args) {Set<Integer> set=new HashSet<>();while(true){//产生随机数int num=(int) (Math.random()*10+1);//将元素添加容器中，由于 Set 类型容器是不允许有重复元素的，所以不需 要判断set.add(num);//结束循环if(set.size()==10) {break;}}for(Integer i:set) {System.out.println(i);}}}运行结果：