Collection Framework

数据扩容

数据表示同种数据类型固定长度在内存中连续存放的数据类型，与基本数据类型不同，数据在内存中有两块空间，一块空间存放实际内容，一块空间存放实际内容的引用。

  1. int[] arr1 = {1, 2, 3};
  2. int[] arr2 = {1, 2, 3, 4};
  4. arr1 = arr2;

上述代码中将arrw赋值给了arr1，如果数组只有一块空间，那么将不能存放arr2的内容。如果数据有两块内存空间那么可以直接将arr1存放内容引用的空间值改为arr1的内容引用，由于arr1的内容没有被引用，会被垃圾回收机制回收。虽然数据一经定义就不能变更长度，但是可以通过将数组指向不同的内容空间从而让数组实现扩容。

  1. public Object[] copy(Object[] oldValue){
  2.     // 1.5 倍扩容
  3.     int newLen = oldValue.length+(oldValue.length >>> 1);
  4.     // 实例化一个新数组
  5.     Object[] newValue = new Object[newLen]; 
  6.        // 值拷贝
  7.     for(int i = 0; i < oldValue.length; i++){
  8.         newValue[i] = oldValue[i];
  9.     }
  10.     // 返回
  11.     return newValue;
  12. }

集合框架继承关系

集合框架有两个主要的顶级接口分别是collection和map。

Collection的主要子接口是List和Set，List表示有序可重复的集合，而Set表示的是无序不重复的接口。

Map不是地图的意思map全称应该是mapping映射的意思，表示从一个值到另一个值的映射关系。

List

List是一个有序可重复的集合。

ArrayList

  1. public class ArrayListTest(){
  2.     public static void main(String[] args){
  3.         ArrayList list = new ArrayList();
  4.         list.add("a");
  5.         list.add("b");
  6.         list.add("c");
  7.     }
  8. }
  1. ArrayList底层是数组，可以通过索引访问，实现了RandomAcces随机访问接口。
  2. ArrayList默认容量是10，每次扩容后的容量是原容量的1.5倍。

我们通过查看源代码来看看当我们创建ArrayList对象并且调用了add方法，内部做了哪些事情。再次之前我们需要介绍ArrayList中一些常见属性关于Arrays请自行查看API。

  1. // 默认初始化容量
  2. private static final int DEFAULT_CAPACITY = 10;
  3. // 空数组
  4. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  5. // 存储实际的值
  6. Object[] elementData;
  7. // 实际存放元素的个数
  8. private int size;
  1. 默认构造方法
  1. /**
  2. * 1. 将实际存放元素的数组初始化为一个空数组
  3. */
  4. public ArrayList() {
  5.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  6. }
  1. add方法
  1. public boolean add(E e) {
  2.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  3.     elementData[size++] = e;
  4.     return true;
  5. }
  1. 确保容量ensureCapacityInternal方法
  1. /**
  2. * @param minCapacity 添加元素需要的最小容量 在add方法中为size+1
  3. */
  4. private void ensureCapacityInternal(int minCapacity) {
  5.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  6. }
  1. 容量计算calculateCapacity方法
  1. /**
  2. * @param elementData this.elementData
  3. * @param minCapacity 需要的容量在add方法中为size+1
  4. * 1. 当实际存放内容的属性elementData 为数组时
  5. * 2. 返回需要的容量和默认容量之间的最大值
  6. * 3. 当实际存放内容的属性elementData不为空时(已经存放元素)返回需要的容量
  7. */
  8. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  9.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  10.         return Math.max(DEFAULT_CAPACITY, minCapacity);
  11.     }
  12.     return minCapacity;
  13. }
  1. 确保实际容量ensureExplicitCapacity方法
  1. /**
  2. * @param minCapacity 需要的最小容量
  3. * 1. 当需要的最小容量大于实际存放元素的长度时候，调用扩容方法
  4. */
  5. private void ensureExplicitCapacity(int minCapacity) {
  6.     modCount++;
  8.     // overflow-conscious code
  9.     if (minCapacity - elementData.length > 0)
  10.         grow(minCapacity);
  11. }
  1. 扩容grow方法
  1. /**
  2. * @param minCapacity 需要的最小容量
  3. * 1. oldCapacity 表示存放内容数组的长度
  4. * 2. newCapacity = oldCapacity + (oldCapacity >> 1)
  5. * 3. 当新容量小于需要的最小容量时 新容量等于需要的最小容量
  6. * 4. 当新容量大于数组容纳长度时......
  7. * 5. 数组扩容
  8. */
  9. private void grow(int minCapacity) {
  10.     // overflow-conscious code
  11.     int oldCapacity = elementData.length;
  12.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  13.     if (newCapacity - minCapacity < 0)
  14.         newCapacity = minCapacity;
  15.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  16.         newCapacity = hugeCapacity(minCapacity);
  17.     // minCapacity is usually close to size, so this is a win:
  18.     elementData = Arrays.copyOf(elementData, newCapacity);
  19. }

LinkedList

  1. LinkedList底层是双向链表，内部使用Node表示。
  2. Node有三个属性，分别是prev，item，next含义分别是：上一个元素的引用，当前值，下一个元素的引用。

LinkedList的常用属性。

  1. // 实际存放元素的个数
  2. int size;
  3. // 存放第一个节点
  4. Node first;
  5. // 存放最后一个节点
  6. Node last;
  1. 无参构造方法
  1. // 1. 创建对象
  2. public LinkedList() {
  3. }
  1. add方法
  1. // 1. 
  2. public boolean add(E e) {
  3.     linkLast(e);
  4.     return true;
  5. }
  1. linkLast方法
  1. /**
  2. * @param e
  3. * 1. 将最后一个节点存放到变量l
  4. * 2. 创建一个对象newNode
  5. * 2.1 参数上一个节点指向最后一个节点
  6. * 2.2 item存放实际的值也就是e
  7. * 2.3 指向下一个节点的引用为null
  8. * 3. 将指向最后一个节点的引用指向新创建的节点
  9. * 4. 判断最后一个是否为空，如果最后一个节点为空 那么就是第一次添加元素
  10. * 4.1 如果为空 将指向第一个节点的引用指向新创建的节点
  11. * 4.2 否则的话将最后一个节点的引用的下一个属性指向新创建的节点
  12. * 5. 实际存放元素的个数+1
  13. * 6. 修改次数+1
  14. */
  15. void linkLast(E e) {
  16.     final Node<E> l = last;
  17.     final Node<E> newNode = new Node<>(l, e, null);
  18.     last = newNode;
  19.     if (l == null)
  20.         first = newNode;
  21.     else
  22.         l.next = newNode;
  23.     size++;
  24.     modCount++;
  25. }
  1. Node类
  1. private static class Node<E> {
  2.         /* 存放节点的值 */
  3.         E item;
  4.         /* 存放上一个节点的引用 */
  5.         Node<E> next;
  6.         /* 存放下一个节点的引用 */
  7.         Node<E> prev;
  9.         Node(Node<E> prev, E element, Node<E> next) {
  10.             this.item = element;
  11.             this.next = next;
  12.             this.prev = prev;
  13.         }
  14.     }

迭代方式

  1. for循环
  2. foreach循环
  3. lambda表达式
  4. 迭代器
  1. ArrayList list = new ArrayList();
  2. list.add(1);
  3. list.add(2);
  4. list.add(3);
  6. for(int i = 0; i < list.size(); i++){
  7.     print(list.get(i));
  8. }
  10. foreach(Object element : list){
  11.     print(element);
  12. }
  14. list.foreach(element -> {
  15.     print(element);
  16. });
  18. Iterator iterator = list.iterator();
  19. while(iterator.hasNext()){
  20.     print(iterator.next());
  21. }

foreach本质

foreach本质上是迭代器。

  1. // 编译前
  2. for (Object element : arrayList) {
  3.     System.out.println(element);
  4. }
  6. // 编译后
  7. Iterator var4 = arrayList.iterator();
  9. while(var4.hasNext()) {
  10.     Object element = var4.next();
  11.     System.out.println(element);
  12. }

Vector

Vector也是一个动态数组，和ArrayList很相似，主要区别在于：

  1. Vector是一个线程安全的容器
  2. Vector比Collection早实现，因此在API上面与其他Collection实现类不同
  1. Vector vector = new Vector();
  2. vector.add("a");
  3. vector.addElement("b");
  4. vector.addElement("b");
  6. Enumeration elements = vector.elements();
  7. while (elements.hasMoreElements()) {
  8.     System.out.println(elements.nextElement());
  9. }

Stack

Stack是一个模拟栈的集合，特点是先进后出FILO，Stack继承了Vector。

  1. Stack stack = new Stack();
  2. stack.push("a");
  3. stack.push("b");
  4. stack.push("c");
  5. System.out.println(stack.size());
  6. System.out.println("----------------------");
  8. while (!stack.empty()) {
  9.     System.out.println(stack.pop());
  10. }
  11. System.out.println(stack.size());
  12. System.out.println("----------------------");

pop方法具体实现

push方法实现

迭代器

迭代器Iterator是Collection的父接口，Collection所有实现类都必须重写迭代器接口方法。迭代器专门服务于Collection即线性队列。

  1. ArrayList arrayList = new ArrayList();
  2. arrayList.add("a");
  3. arrayList.add("b");
  4. arrayList.add("c");
  5. arrayList.add("d");
  6. // 1. for 循环
  7. for (int i = 0; i < arrayList.size(); i++) {
  8.     System.out.println(arrayList.get(i));
  9. }
  11. // 2. for-each 迭代
  12. // 2.1 for-each 本质上是迭代器操作,编译之后是迭代器
  13. // 2.2 本质上说迭代其更快,因为for-each需要经过编译
  14. for (Object element : arrayList) {
  15.     System.out.println(element);
  16. }
  17. // 编译后的结果
  18. Iterator var4 = arrayList.iterator();
  20. while(var4.hasNext()) {
  21.     Object element = var4.next();
  22.     System.out.println(element);
  23. }
  25. // 3. 迭代迭代
  26. // 3.1 不要在迭代中多次使用next 否则会有 NoSuchElementException 异常
  27. Iterator iterator = arrayList.iterator();
  28. while (iterator.hasNext()) {
  29.     Object element = iterator.next();
  30.     System.out.println(element);
  31. }
  33. // 4. Java8 Stream

从效率上来说使用迭代器，别其他迭代要快，因此，如果使用collection实现类，可以使用迭代器。

泛型

泛型即类型参数化，将一个类型作为参数传递，可应用于方法、返回值、参数。

Set

Set是一个无序不重复的集合，每一个Set实现类底层都对应一个Map，例TreeSet -> TreeMap，HashSet -> HashMap。

TreeSet

TreeSet表示一个有序不重复的接口。

如何实现有序

TreeSet内部使用自然排序或比较器来实现有序。

自然排序和比较器

使用自然排序需要在类中实现Comparable接口重写compareTo方法。使用比较器需要新建一个类实现Comparator接口重写compare方法，将比较器对象作为参数传递给TreeSet的构造方法。对于自己维护的类可以使用自然排序，而对于在不修改类的内容的情况下可以使用比较器。

  1. // 比较器
  2. @Override
  3. public int compare(User o1, User o2) {
  4.     if(o2.getId() != o1.getId()){
  5.         return o1.getId() - o2.getId();
  6.     }
  7.     return o2.getAge() - o1.getAge();
  8. }
  10. // 自然排序
  11. @Override
  12. public int compareTo(Person anotherPerson) {
  13.     if (this.id != anotherPerson.id) {
  14.         return anotherPerson.id - this.id;
  15.     } else {
  16.         return this.age > anotherPerson.age ? 1 : -1;
  17.     }
  18. }

实现

TreeSet使用平很二叉树中的红黑树表示有序的集合，在内部使用了Entry来表示对应的结构。

  1. K key;
  2. V value;
  3. Entry<K,V> left;
  4. Entry<K,V> right;
  5. Entry<K,V> parent;
  6. boolean color = BLACK;

具体的添加方法：

  1. Entry<K,V> t = root;
  2. if (t == null) {
  3.     compare(key, key); // type (and possibly null
  4.     root = new Entry<>(key, value, null);
  5.     size = 1;
  6.     modCount++;
  7.     return null;
  8. }
  9. int cmp;
  10. Entry<K,V> parent;
  11. // split comparator and comparable paths
  12. Comparator<? super K> cpr = comparator;
  13. if (cpr != null) {
  14.     do {
  15.         parent = t;
  16.         cmp = cpr.compare(key, t.key);
  17.         if (cmp < 0)
  18.             t = t.left;
  19.         else if (cmp > 0)
  20.             t = t.right;
  21.         else
  22.             return t.setValue(value);
  23.     } while (t != null);
  24. }
  25. else {
  26.     if (key == null)
  27.         throw new NullPointerException();
  28.     @SuppressWarnings("unchecked")
  29.         Comparable<? super K> k = (Comparable<? super K>) key;
  30.     do {
  31.         parent = t;
  32.         cmp = k.compareTo(t.key);
  33.         if (cmp < 0)
  34.             t = t.left;
  35.         else if (cmp > 0)
  36.             t = t.right;
  37.         else
  38.             return t.setValue(value);
  39.     } while (t != null);
  40. }
  41. Entry<K,V> e = new Entry<>(key, value, parent);
  42. if (cmp < 0)
  43.     parent.left = e;
  44. else
  45.     parent.right = e;
  46. fixAfterInsertion(e);
  47. size++;
  48. modCount++;
  49. return null;
  1. TreeSet内部使用比较器或自然排序来保证有序
  2. 使用自定义的类作为key需要实现比较器或者自然排序
  3. TreeSet不允许key为null

HashSet

线性队列

队列是一种先进先出FIFO的集合，与栈相反。

  1. Queue queue = new SimpleLinkedList();
  2. queue.offer("a1");
  3. queue.offer("a2");
  4. queue.offer("a3");
  5. queue.offer("a4");
  6. queue.offer("a5");
  7. System.out.println(queue.size());
  9. System.out.println(queue.poll());
  10. System.out.println(queue.poll());
  11. System.out.println(queue.size());

具体实现

Collections

Collections是专门服务于Collection接口，内部封装了针对Collection的一些常用API。

Map

map表示key到value的映射。

TreeMap

HashMap

HashMap是一个允许key为null，线程不安全的Map实现类。在JDK1.7使用数组+链表表示，从JDK1.8之后使用数组+链表+红黑树表示。HashMap的默认容量是16，在>=LOADFATOR的情况下会实现扩容，容量为原来的两倍。

HashTable

  1. HashTable线程安全
  2. HashTable不允许key为null

集合作业

  1. ArrayList图
  2. LiknedList图
  3. 模拟LinkedList
  4. 模拟Vectory pop push方法
  5. TreeSet
  6. 队列