java容器

f10566b1c77e28727ac7c89fd009c64.jpg

20190329152944924.png

ArrayList

底层是基于动态数组，随机访问数组元素的效率高，向数组尾部添加元素的效率高，但是删除数组中的数据以及向数组中间添加数据效率低，因为会产生数组移位。

构造方法：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
    }
}

在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0
在用有参构造来创建对象的时候其实就是根据传入参数的值来确定创建数组的大小

Arraylist扩容机制

1470032-20181024160424125-1533989062.png

1470032-20181024160424806-854947488.png

在添加的时候如果原数组是空的，就直接给一个10的长度，否则的话就+1。
所以我们可以认定创建arraylist的时候数组长度为0，当添加时数组长度会变为10
调用grow(minCapacity)方法时进行扩容

1470032-20181024160425606-521804483.png

oldCapacity >> 1 右移运算符，指的是原来长度的一半再加上原长度也就是每次扩容是原来的1.5倍

总结：扩容步骤：
新增数据空间判断
新增数据的时候需要判断当前是否有空闲空间存储
扩容需要申请新的连续空间
把老的数组复制过去
新加的内容
回收老的数组空间

所以ArrayList在初始化的时候指定长度肯定是要比不指定长度的性能好很多, 这样不用重复的申请空间, 复制数组, 销毁老的分配空间了

LinkedList

LinkedList 是通过一个双向链表来实现的，它允许插入所有元素，包括 null，同时，它是线程不同步的

2019111142359355.png

双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个 first 指针，指向头节点，和 last 指针，指向尾节点。

向头部插入

2019111142457099.png

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点，源码的实现如下：

private void linkFirst(E e) {
 final Node<E> f = first;
 //当前节点的前驱指向 null，后继指针原来的头节点
 final Node<E> newNode = new Node<>(null, e, f);
 //头指针指向新的头节点
 first = newNode;
 //如果原来有头节点，则更新原来节点的前驱指针，否则更新尾指针
 if (f == null)
 last = newNode;
 else
 f.prev = newNode;
 size++;
 modCount++;
}

向尾部插入

2019111142546294.png

当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点，源码的实现如下：

void linkLast(E e) {
 final Node<E> l = last;
 //当前节点的前驱指向尾节点，后继指向 null
 final Node<E> newNode = new Node<>(l, e, null);
 //尾指针指向新的尾节点
 last = newNode;
 //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针
 if (l == null)
 first = newNode;
 else
 l.next = newNode;
 size++;
 modCount++;
}

向中间节点插入

2019111142620872.png

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点，源码的实现如下：

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++;
}

Vector

Vector和Arraylist实现方式基本类似，区别在两点：
1：扩容时当Vector或ArrayList中的元素超过它的初始大小时，Vector会将它的容量翻倍，而ArrayList只增加50%的大小，这样ArrayList就有利于节约内存空间
2：Vector线程安全但是效率低

如果想在多线程下使用Arraylist，可以考虑JUC

Stack（栈）

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。
堆栈只定义了默认构造函数，用来创建一个空栈。堆栈包括由Vector定义的所有方法

import java.util.*;
 
public class StackDemo {
 
    static void showpush(Stack<Integer> st, int a) {
        st.push(new Integer(a));
        System.out.println("push(" + a + ")");
        System.out.println("stack: " + st);
    }
 
    static void showpop(Stack<Integer> st) {
        System.out.print("pop -> ");
        Integer a = (Integer) st.pop();
        System.out.println(a);
        System.out.println("stack: " + st);
    }
 
    public static void main(String args[]) {
        Stack<Integer> st = new Stack<Integer>();
        System.out.println("stack: " + st);
        showpush(st, 42);
        showpush(st, 66);
        showpush(st, 99);
        showpop(st);
        showpop(st);
        showpop(st);
        try {
            showpop(st);
        } catch (EmptyStackException e) {
            System.out.println("empty stack");
        }
    }
}

stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack

HashSet

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。
对于HashSet而言，基本上都是直接调用底层HashMap的相关方法来完成。

LinkedHashSet

LinkedHashSet直接继承于HashSet，维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

TreeSet

TreeSet的底层是用TreeMap实现的，它是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。，它是根据实际的值的大小来排序，TreeSet也支持两种排序方式：自然排序，自定义排序

自然排序：
自然排序需要Student类实现Comparable接口，并重写Compareto方法：

1495080-20190507095816071-1585498105.jpg

1495080-20190507095922512-519434682.jpg

1495080-20190507100347042-1111886901.jpg

比较器排序：
创建一个比较类，实现Comparator接口，并重写compare(T o1, T o2)方法

1495080-20190507103411055-43890792.jpg

1495080-20190507103651627-724729469.jpg

1495080-20190507103759634-1698820543.jpg

HashMap

HashMap底层的数据结构是哈希表，哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点，元素的存放位置一般是通过hash(key)%len来获得的，在jdk1.8中链表的长度达到8以后就会形成红黑树，增加检索效率。

3801213fb80e7becc2f5933286b2223e9a506b5d.jpeg

map.put实现原理：
第一步首先将k,v封装到Node对象当中（节点）
第二步它的底层会调用K的hashCode()方法得出hash值
第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖

map.get实现原理：
第一步：先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标
第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

HashMap增删是在链表上完成的，而查询只需扫描部分，再加上1.8对链表的优化，所以总体来说效率很高。

HashMap扩容（resize ）：
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容

当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数（哈希冲突）超过16X0.75=12的时候，就把数组的大小扩展为2X16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能，一般来说，数组初始化大小都是2的次方大小时，hashmap的效率最高，主要原因是因为2的次方大小的二进制每一位都是1，这个时候在进行&运算时可以有效地把索引位置给分散开，减少哈希冲突

LinkedHashMap

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表+红黑树在此基础上LinkedHashMap 增加了一条双向链表，他重新定义了数组中保存的元素Entry（继承于HashMap.node)，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表，用next获取该链表下一个Entry，也可以通过双向链接，通过after完成所有数据的有序迭代

TreeMap和SortMap

TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据key值进行升序排序，也可以重写comparator方法来根据value进行排序具体取决于使用的构造方法。不允许有null值null键。TreeMap是线程不安全的
TreeMap基于红黑树（Red-Black tree）实现。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n)

比较器：

import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

/**
 * 自定义TreeMap的比较器
 */
public class MapTest6
{
    public static void main(String[] args)
    {
        // 利用TreeMap的有序性,存储数字及其出现次数，key为数字，value为次数
        TreeMap<Integer, Integer> map = new TreeMap<>(new MapComparator());
    
        /**
         * 随机生成[10,50]间的40个数字，并统计每个数字出现的次数
         */
        Random random = new Random();
        for (int i = 0; i < 40; i++)
        {
            int num = random.nextInt(41) + 10;

            if (map.get(num) == null)
            {
                map.put(num, 1);
            }
            else
            {
                int count = map.get(num);
                map.put(num, count + 1);
            }
        }

        // 遍历map，按照key的逆序输出
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        for (Iterator<Map.Entry<Integer, Integer>> iterator = set.iterator(); iterator.hasNext();)
        {
            Map.Entry<Integer, Integer> entry = iterator.next();
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + "的出现次数为：" + value);
        }
    }
}

//自定义比较器根据键的逆序排列
class MapComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer o1, Integer o2)
    {
        return o2 - o1;
    }
}

HashTable

HashTable和HashMap两种集合非常相似，Hashtable继承自Dictionary类，Dictionary在1.8中已经弃用，Hashtable底层是一个哈希表，它是一个线程安全的集合，单线程集合，速度慢，Hashtable集合不能存储null值，null键
HashTable在不指定容量的情况下的默认容量为11，Hashtable不要求底层数组的容量一定要为2的整数次幂
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍
HashTable目前很少用，如果考虑多线程环境的话可以使用JUC