JAVA集合框架

Collection

类图

List接口

有序的：有序插入，可以通过下标访问元素，元素可以重复。

ArrayList

基于数组结构实现，查询快，增加删除效率慢。

源码分析：

//首先继承
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    
    
 	/**
     * Default initial capacity.//默认初始容量为10
     */
    private static final int DEFAULT_CAPACITY = 10;

	transient Object[] elementData; //基于这个数组来存储元素

 	private int size;//实际元素数量

	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//默认初始化的数组

	//初始化时，默认容量为0
	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
	
	//add方法
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

	private void ensureCapacityInternal(int minCapacity) {//确保容量大小能够容纳新的元素
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

	private static int calculateCapacity(Object[] elementData, int minCapacity) {//计算容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果是刚初始化的时候
            return Math.max(DEFAULT_CAPACITY, minCapacity);//则取minCapacity和默认初始化容量中的最大值即 10
        }
        return minCapacity;//否则直接返回minCapacity  例如此时不是初始化的时候，向list中添加第11个元素
    }

	private void ensureExplicitCapacity(int minCapacity) {//确保显示容量
        modCount++;

        // 容量扩容判断
        if (minCapacity - elementData.length > 0)//如果元素的容量大于数组中的元素的个数 
            //此时minCapacity = 11，而elementData.length = 10
            grow(minCapacity);//进行扩容
    }

	//增加容量以确保它至少可以容纳由最小容量参数指定的元素数量
	private void grow(int minCapacity) {// minCapacity = 11
        int oldCapacity = elementData.length;//保存数组的长度	例如现在为10
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量是原来容量的1.5倍 15
        if (newCapacity - minCapacity < 0)//如果新的容量小于minCapacity 
            newCapacity = minCapacity;//则新的容量就是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);//然后进行数组元素的复制
    }

	private static int hugeCapacity(int minCapacity) {//继续扩大到最大容量
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

}


public class Arrays {
	public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

	public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
}

public final class System {
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
}

Set接口

Map接口

类图

HashMap 和 HashTable

方面	区别
线程安全	HashMap非线程安全，HashTable内部方法使用了 synchronized 修饰，线程安全。推荐使用 ConcurrentHashMap
效率	因为线程安全问题，HashMap 效率更高一点，不推荐使用 HashTable。
对空键和空值的支持	HashMap可以存储 null 的 key 和 value，但是只能存在一个键为 null，null 作为值可以有多个；HashTable不允许null key 和null value，否则会抛出 NullPointerException。
初始容量和扩容大小	HashTable默认初始容量大小为 11，每次扩容大小为原来的两倍加一（2n + 1）；HashMap默认初始容量为 16，每次扩容大小为原来的两倍（2n），HashMap的容量始终是2的幂次方大小（tableSizeFor() 方法保证）。
底层数据结构	JDK1.8以后，HashMap底层数据结构变为 数组 + 链表 + 红黑树，当链表长度大于阈值（8）时，如果数组长度小于64，那么会先进行数组的扩容，否则就会将链表转换成红黑树，从而减少搜索时间，提高效率。HashTable 始终是 数组 + 链表。

HashMap

常用方法

方法	描述
put(K key,V value)	向HashMap集合中添加元素
get(Object key)	返回指定键所映射的值，没有该key对应的值则返回null
size()	返回HashMap集合中的元素数量
clear()	清空HashMap集合
isEmpty()	判断HashMap集合中是否有数据，如果没有则返回true，否则返回false
remove(Object key)	删除HashMap集合中键为key的数据并返回其所对应value值
values()	返回HashMap集合中所有value组成的以Collection数据类型格式数据例如：Collection con = map.values();
getOrDefault()	获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
keySet()	返回 hashMap 中所有 key 组成的集合视图。

遍历方式

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();    //创建一个HashMap
        for (int i = 0; i < 10; i++) {                        //为HashMap存储键值对
            map.put(i, i);
        }
        /**
         *  keySet()方法获取键 Set集
         */
        Set<Integer> keySets = map.keySet();                //获取键 的Set集合
        for (Integer keySet : keySets) {                    //迭代输出键
            System.out.print(keySet + " ");
        }

        /**
         *  values()方法获取值的 Collection集
         */
        Collection<Integer> values = map.values();            //获取HashMap值
        for (Integer value : values) {                    //遍历输出HashMap值
            System.out.print(value + " ");
        }

        /**
         *  entrySet() 获取键值对的 Set集
         */
        Set<Map.Entry<Integer, Integer>> sets = map.entrySet();        //获取HashMap键值对
        for (Map.Entry<Integer, Integer> set : sets) {                //遍历HashMap键值对
            System.out.println("Key:" + set.getKey() + "    value:" + set.getValue());
        }

    }
}

底层数据结构

/**
    * Basic hash bin node, used for most entries.  (See below for
    * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
    */
   static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       V value;
       Node<K,V> next;

       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }