Java-集合框架

Java-集合框架

集合框架概括

集合可以看作是一种容器，用来存储对象信息。一些优秀的算法和数据结构被封装到了Java的集合框架中。

• Collection 接口存储一组不唯一，无序的对象
• List 接口存储一组不唯一，有序的对象。
• Set 接口存储一组唯一，无序的对象
• Map 接口存储一组键值对象，提供key到value的映射

Collection

public interface Collection extends Iterable {
    //返回集合中元素的数量，如果集合中的元素个数超过了Integer.MAX_VALUE(整型最大值)，返回Integer.MAX_VALUE
    int size();
 
    //返回这个集合是否为空
    boolean isEmpty();
 
    //返回集合是否包含元素o
    boolean contains(Object o);
 
    //返回一个可以遍历集合的迭代器，这里没有办法保证返回的元素有序(除非这个类的实例提供了有序的保证)
    Iterator iterator();
 
    //返回一个包含集合中所有元素的数组，返回的数组中不会包含任何引用（相当于分配了一个新数组，即使该集合由数组支持。）
    Object[] toArray();
 
    //返回一个T类型的数组；如果数组是T类型的可以直接返回T，否则，将以运行时类型分配新的数组。
     T[] toArray(T[] a);
    
    //添加一个单例到集合中
    boolean add(E e);
    
    //如果此对象在集合中，删除此对象
    boolean remove(Object o);
 
    //如果此集合包含指定集合中的所有元素，返回true 
    boolean containsAll(Collection c);
 
    //将指定集合中的所有元素都添加到当前集合中
    boolean addAll(Collection c);
 
    //移除此集合中c集合也包含的所有元素
    boolean removeAll(Collection c);
 
    //删除除集合c之外的所有元素
    boolean retainAll(Collection c);
 
    //删除此集合中的所有元素
    void clear();
 
    //比较此集合和指定对象是否相等
    boolean equals(Object o);
 
    //返回此集合的哈希值
    int hashCode();
}

Array

// 数组定义
String[] strs = new String[]{"111","222","333"};
// 数组定义
String[] strs2 = new String[3];
strs2[0] = "111";
strs2[1] = "222";
strs2[2] = "333";

• Java中的数组长度不可改变。长度一旦被固定下来，就不能添加超过长度的元素，负责出现数组越界异常。
• 不能动态的对元素进行追加。

List

• ArrayList

(1).动态数组，解决java动态数组的扩容问题,数组元素类型为Object类型，即可以存放所有类型数据

Object[] elementData;

(2).ArrayList数组长度的最大极限？

// 扩容的最大边界值
// 1.防止栈溢出和越界  2.提前达到最大，减少扩容一次机会
// 数据在集合中存储达到极限，任何一次数据迁移和复制都会引发内存溢出
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 扩容的方法
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

(3).ArrayList的初始化长度?

private static final int DEFAULT_CAPACITY = 10;

(3)ArrayList的无参构造问题?

但是new ArrayList<>()或者new HashMap<>()都是采用一种延迟加载的方式来完成初始化(JDK1.8之后)。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

在JDK1.8之前的初始化长度为10的数组:

this.elementData = new Object[initialCapacity];

这样是为了节约空间，长度为10的数组定义了但不使用。那么JDK1.8是在什么时候初始化的呢?
在add()方法的时候进行初始化。

(4)ArrayList是如何动态扩容?扩容时机是什么?

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

(5)ArrayList的删除remove?

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);
   	//将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

• linkedList

1）是通过链表实现的
2）如果在频繁的插入，或者删除数据时，就用linkedList性能会更好。

linkedList类的结构:

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;// 实际元素个数
    
    transient Node first;// 头结点
    
    transient Node last;// 尾结点
}

linkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

Node内部类

private static class Node {
    E item;// 数据域（当前节点的值）
    Node next;// 后继（指向当前一个节点的后一个节点）
    Node prev;// 前驱（指向当前节点的前一个节点）

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

核心方法add的实现:

public boolean add(E e) {
    linkLast(e);
    return true;
}

add函数用于向linkedList中添加一个元素，并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。

void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);//将e封装为节点，并且e.prev指向了最后一个节点
    last = newNode;//newNode成为了最后一个节点
    if (l == null)//判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它
        first = newNode;
    else//正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点
        l.next = newNode;
    size++;//添加一个节点，size自增
    modCount++;
}

Set

public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap map;

    private static final Object PRESENT = new Object();

    // 构造方法的底层是HashMap
    public HashSet() {
        map = new HashMap<>();
    }

核心方法add方法:

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashSet底层是HashMap。
TreeSet底层是TreeMap()。在构造函数中可以传入排序的规则

TreeSet objects = new TreeSet<>(new Comparator() {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge()-o2.getAge();
    }
});

Map

Map接口专门处理键值映射数据的存储，可以根据键实现对值的 *** 作。
最常用的实现类是HashMap。

1.HashMap概述以及原理
HashMap是基于哈希表的Map接口实现的，它存储的是内容是键值对映射。此类不保证映射的顺序，假定哈希函数将元素适当的分布在各桶之间，可为基本 *** 作(get和put)提供稳定的性能。

• HashMap在JDK1.8以前数据结构和存储原理

HashMap的数据结构就是用的链表散列(HashMap的数据结构就是用的链表散列)。

1.默认情况下，HashMap的长度是16的头部数组元素Entry，存储链表的头部元素节点。
2.通过类似于hash(key%hashCode())%len的哈希算法，来确定元素存储在哪个位置。

HashMap底层是怎么样使用这个数据结构进行数据存取的？
第一步：HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。

static class Entry implements Map.Entry {    
	final K key;    //map的key    
	V value;    //value  
	Entry next;//指向下一个entry对象    
	int hash;//通过key算过来的你hashcode值。
}

第二步：构造好了entry对象，然后将该对象放入数组中。
通过key、value封装成一个entry对象，然后通过key的值来计算该entry的hash值，通过entry的hash值和数组的长度length来计算出entry放在数组中的哪个位置上面。

• JDK1.8后HashMap的数据结构

底层基于:数组+链表+红黑树,桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。

HashMap的长度是16的头部数组元素Node(JDK1.8之前叫Entry，1.8改了名)

 static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
}

2.HashMap的构造方法

HashMap一共有四个构造方法，构造方法中并没有初始化数组，数组在一开始就已经被创建了，构造方法只做两件事情，一个是初始化加载因子，另一个是用threshold记录下数组初始化的大小。

HashMap的无参构造方法采用的是延迟加载的方式进行初始化数组，长度默认是16,。

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

初始化是在HashMap的put方法中。

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[] tab; Node p; int n, i;
        // table未初始化或者长度为0，进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 桶中已经存在元素
        else {
            Node 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)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;
                }
            }
            // 表示在桶中找到key值、hash值与插入元素相等的结点
            if (e != null) { // existing mapping for key
            	// 记录e的value
                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;
    }

点击进入resize()方法:

final Node[] resize() {
	// 当前table保存
    Node[] oldTab = table;
    // 保存table大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存当前阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 之前table大小大于0
    if (oldCap > 0) {
    	// 之前table大于最大容量
        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
    }
    // 之前阈值大于0
    else if (oldThr > 0) 
    	// oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
        newCap = oldThr;
    else {              
    	// 无参方法初始化
        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"})
    // 初始化table
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // 之前的table已经初始化过
    if (oldTab != null) {
    	// 复制元素，重新进行hash
        for (int j = 0; j < oldCap; ++j) {
            Node 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)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
}

2.HashMap的底层数组的默认值是多少？极限值是多少?

默认值是16，最大值是2的30次方

static final int MAXIMUM_CAPACITY = 1 << 30;

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
     // 初始容量不能大于最大值，否则为最大值
    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);
}

tableSizeFor(initialCapacity):这个方法的作用是保证哈希桶的数目是2的n次幂，将initialCapacity转化成比它大的最小的2的n次幂。

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

当n=1<<30的时候:
01 00000 00000 00000 00000 00000 00000 (n)   
01 10000 00000 00000 00000 00000 00000 (n |= n >>> 1)    
01 11100 00000 00000 00000 00000 00000 (n |= n >>> 2)    
01 11111 11000 00000 00000 00000 00000 (n |= n >>> 4)    
01 11111 11111 11111 00000 00000 00000 (n |= n >>> 8)    
01 11111 11111 11111 11111 11111 11111 (n |= n >>> 16)    

3.threshold(扩容因子)的作用？

• capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。
• loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。
• threshold = capacity * loadFactor：当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准(从性能和稳定度来考虑扩容)。
• 默认的无参构造函数的扩容因子是16*0.75=12，扩容的临界判断是通过数组的长度是否大于扩容因子threshold，扩容的大小是原数组的两倍。
  

// 数组扩容两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
        oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // 因子扩容两倍

3.Node是通过hash计算找到存放在哪个位置的？

追求细粒度的ConCurrentHashMap

• HashMap是线程不安全的，通过Collections.synchronizedMap(new HashMap<>())创建一个线程安全的集合，或者使用HashTable，其原理都是使用synchrinized(一种串行的方式)来实现，都是属于重量级的锁。
• ConcurrentHashMap是J.U.C(java.util.concurrent包)的重要成员，它是HashMap的一个线程安全的、支持高效并发的版本。在默认理想状态下，ConcurrentHashMap可以支持16个线程执行并发写 *** 作及任意数量线程的读 *** 作。
• JDK1.8之前:容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术。
• JDK1.8之后: