java集合学习

1.概述

集合是一种存储数据的容器，较数组而言，集合可以存储不同类型的数据，且集合的容量是动态的，并且提供了一系列方法便于数据的操作。

2.集合体系

在Java中，集合可分为两大类，Collection接口下的单列集合和Map接口下的双列集合（存储键值对）

单列集合体系图（部分）

Collection接口继承了Iterable接口，所以其接口的实现类都是可迭代的对象。

 Collection接口中规定的方法

 双列集合体系图（部分）

 

3.list接口及实现类

List接口的特点

• 允许存储重复值
• 允许存储多个空值
• 存取是有序的，支持通过索引操作元素
• JDK中已知实现子类

 List接口的常用方法

 常见子类介绍

1.ArrayList

构造方法

存储数据的方式：数组

扩容机制

eg.
ArrayList<Integer> arr  = new ArrayList();
        arr.add(1);
执行过程（源码）：
1.执行构造方法
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
2.执行add()
   public boolean add(E e) {
// 判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
3. 执行ensureCapacityInternal(int minCapacity)
  private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
4.执行calculateCapacity，确认最小需要的容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
5.执行ensureExplicitCapacity（），判断当前数组长度和所需最小容量之间的关系，决定是否进行扩容
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
6.grow(int minCapacity)，扩容
 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);

2.Vector

Vector与AraayList都是通过数据进行数据的存储，不同的地方在于Vector是线程安全的，在多线程环境能够保证数据的一致性。

除此之外的一些不同之处

构造方法的不同:

eg.  Vector<Integer> vec = new Vector<>();
过程如下：
1.     public Vector() {
          this(10);
    }
2.     public Vector(int initialCapacity) {
          this(initialCapacity, 0);
    }
3.      public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

扩容机制的不同

// 前面确认是否需要扩容的步骤类似ArrayList
// 实现扩容
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
// Vector 的扩容取决于capacityIncrement,在capacityIncrement不大于0情况下扩容为原来的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.LinkedList

linkedlist使用双向链表实现

构造方法

在序列末尾添加元素

eg.在序列末尾添加一个元素
源码：
1.  public boolean add(E e) {
        linkLast(e);
        return true;
    }
2.   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++;
    }

图解（此处箭头为双向箭头）

 

 

 因为使用的是链表，所以不存在扩容问题。（删除元素以及在指定位置插入元素原理相同）

List接口常见实现类小结

ArrayList使用数组存储数据，适合查询较多的场景。LinkedList使用的是来链表，在遍历上效率较低，但增加或删除元素效率较高。如果是在多线程环境下，且需要考虑线程安全问题，则选择Vector.

注意事项

• LinkedList增加（删除）元素的效率一定高于ArrayList么？事无绝对，数组增加（删除）元素效率低的本质原因是会对增加（删除）之后位置元素的影响，需要将元素前移（后移）。所以，当增加（删除）的元素位于序列的末尾，不需要移动任何元素时，ArrayList的效率是高于LinkedList的。

4.set接口及实现类

set接口的特点

• 不允许存储重复值
• 仅且允许存储一个空值
• 存取是无序的（不能通过索引访问，另外linkedHashSet看起来是有序的）

 set接口已知方法

常见子类介绍

HashSet

构造方法

public HashSet() {
// HashSet 底层实现为HashMap
// jdk8之前HashMap通过哈希表实现（数组+链表）
// jdk之后通过数组+链表+红黑树实现
    map = new HashMap<>();
}

public HashMap() {
// loadFactor加载因子，用于计算threshold（扩容阈值） = 容量 * 加载因子  
 this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
}

扩容机制

容量变为原来的2倍数，且扩容阈值也变为原来的2倍数 

 eg.

源码：
1.方法入口
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
 
2.
   public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
3. 通过特定算法计算对象的hash值
  static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
4. 
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
// 辅助变量
        Node<K,V>[] tab; Node<K,V> p; int n, i;
// 是否进行第一次扩容，初始容量16，初始加载因子0.75
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
// 通过计算出的hash值与table表当前最大索引值进行计算得出元素放置的位置
// 如果该位置为空，直接存入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
// 如果该位置有元素
        else {
            Node<K,V> e; K k;
// 首先与头节点进行比较，如果与头节点相同，则不添加
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
// 与头节点不同，判断表的这个位置存储的是链表还是树，如果已转化为树，则调用putTreeVal（...）
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 以上都不满足，与头节点不同且还未转化为树结构
//  与链表的每个节点进行比较，有相同或到达末尾就结束比较
            else {
                for (int binCount = 0; ; ++binCount) {
// 判断添加后是否会触发链表转化为红黑树
// 转化机制  单条链表元素个数为 TREEIFY_THRESHOLD（8） ，
// 且table表的容量达到MIN_TREEIFY_CAPACITY（64）
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
// 依次比较，存在重复就跳出
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
// 存在重复元素
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

简图

遍历元素顺序探究

预期：按照table表顺序进行遍历，如果某个位置链表元素超过1，则将该位置链表遍历结束后 再访问table表的下一个元素。

测试代码：

package Test;
 
import java.util.Collections;
import java.util.HashSet;
import java.util.Objects;
 
public class HashSetDemo {
    public static void main(String[] args) {
        HashSet<TestPreparation> hs = new HashSet<>();
        Collections.addAll(hs, new TestPreparation(1), new TestPreparation(2),  new TestPreparation(3), new TestPreparation(4), new TestPreparation(5) , new TestPreparation(6), new TestPreparation(null));
        System.out.println(hs);
    }
}
// 测试类
class TestPreparation{
    Integer value;
 
    public TestPreparation(Integer value) {
        this.value = value;
    }
// 通过value进行比较
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TestPreparation that = (TestPreparation) o;
        return value.equals(that.value);
    }
// 重写hashCode()，只会返回 1，2，3更容易发生哈希冲突
    @Override
    public int hashCode() {
        if (value % 3 == 0 )
            return 3;
        else if (value % 2 == 0)
            return 2;
        else
            return 1;
    }
 
    @Override
    public String toString() {
        return  value.toString() ;
    }
}

过程：

 如预期元素都集中在table的1，2，3位置

1号位元素

 

2号位元素

 

3号位元素

 

通过上图可推断输出结果为 1，5，2，4，3，6

实际结果为

 所以HashSet遍历元素的顺序为按照table表索引，依次遍历每个位置的链表

补充依据

 @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

 注意事项

• HashSet的去重与元素在内部的排序与hashCode()和equals(Object object)方法相关，可根据需求对两个方法进行重写。

TreeSet

构造方法

无参构造执行顺序
public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeMap() {
    comparator = null;
}

Tree的底层实现为TreeMap

 TreeSet添加元素

通过传入的比较器进行比较或通过对象实现comparable接口重写的compareTo方法进行比较，根据返回值进行元素排序和判断是否添加，返回0就认为是重复元素不进行添加，返回值不为0则按照比较规则进行元素排序。

注意事项：

1.TreeSet添加的元素通常为可进行比较的一些对象，要么满足传入比较器的比较规则，要么实现了Comparable接口。

2.TreeSet存储的通常是一类元素，或能够通过比较器进行比较的元素。

3.常见异常

• java.lang.ClassCastException

eg.

 异常根源

 public int compareTo(String anotherString)

5.Map接口及实现类

Map接口的特点

• 存储键值对，键唯一对应值，可以通过键寻找对应的值，反之则不行
• 键不能重复，允许值重复
• 部分实现类一个键为空

实现类

 Map接口方法

 常用实现类学习

HashMap、TreeMap和HashTable

HashMap、TreeMap的数据存储方式，以及添加元素时的执行过程可见上文HashSet和TreeSet处介绍

HashTable特点：

• 键和值都不能为null
• 线程安全
• 效率较低

构造方法

eg. Hashtable<String, Integer> ht = new Hashtable<>();

ht.put("1",100);

执行过程：
1.
     public Hashtable() {
        this(11, 0.75f);
    }
2.
     public Hashtable(int initialCapacity, float loadFactor)
3.判断是否添加元素（省略部分代码）
     public synchronized V put(K key, V value){
// 值不能为空
         if (value == null) {
            throw new NullPointerException();
        }
// ... 省略代码为判断键是否已经存在，方式为计算hash值，确认放在table表的位置
//  为空直接放入
//  不为空对该位置的链表元素依次进行判断
         addEntry(hash, key, value, index);
         return null;
}
4. 添加元素（省略部分代码）
 private void addEntry(int hash, K key, V value, int index) {
//  判断是否进行扩容
// 如果扩容，需要重新计算元素存放的位置
      if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
 
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
//  将元素放置在指定位置
    tab[index] = new Entry<>(hash, key, value, e);
    
}
 
5.扩容部分（省略部分代码）
    protected void rehash() {
// 扩容倍数为 
// 不超过最大值new = old*2 + 1；
// 超过则等于
      int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
// 重新确定阈值
// 将已经存放的元素按照之前的流程重新计算位置添加
 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
 
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;
 
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }

6.适用场景分析