集合

2023-08-28 11:31 由 xashould 发表于 #后端开发

集合

一、概念

java中集合类似容器一样，专门存储java对象（对象的引用），对象可以为任意的数据类型，长度可变。

按照存储结构分为两大类：单例集合（collection）与双列集合（Map）

collection：单列集合的父接口，有俩个子接口:List、Set
- List 接口：
  - 特点：元素有序，可重复
  - 实现类：ArrayList、LinkedList
- set 接口：
  - 特点：元素无序，不可重复
  - 实现类：HashSet、TreeSet
Map:双列集合父接口，用于存储 key、value 映射关系的元素；集合中每一个元素都包含一对键值对（key、value）值，且 key 唯一，通过 key 即可找到对应的 value。
- 实现类：HashMap、TreeMap。

单例集合：

双列集合：

二、Collection接口

因为 Collection 是所有单例集合的父接口，所以其内部定义的方法都可适用其下子接口

方法如下：

int size();//获取该集合中元素个数

boolean isEmpty();//判断该集合是否为空

boolean contains(Object o);//判断集合中是否包含某个元素

Iterator<E> iterator();//返回迭代的迭代器，用于遍历元素

boolean add(E e);//添加元素

boolean remove(Object o);//移除指定元素

boolean containsAll(Collection<?> c);//判断集合是否包含指定集合中的所有元素

boolean addAll(Collection<? extends E> c);//将集合 c 的元素全都添加到集合中

boolean removeAll(Collection<?> c);//移除集合中集合c的全部元素

void clear();//删除集合中所有元素

default Stream<E> stream() //将集合转换为有序元素的流对象

三、List 接口与实现类

3.1、List接口简介

该集合中允许出现重复元素，有序
元素以线性存储，可通过索引（类似数组中的下标）来访问集合中元素

方法：

boolean add(E e) //添加元素

void add(int index, E element)//将元素插入指定位置 

boolean addAll(Collection<? extends E> c) //添加所有集合c元素

boolean addAll(int index, Collection<? extends E> c) //将集合c的元素添加到指定位置

void clear() //清除所有元素

boolean contains(Object o)//判断是否包含 o 元素 

boolean containsAll(Collection<?> c) //判断是否包含集合c的所有元素
 
boolean equals(Object o) //判断是否与 o 元素相等

E get(int index) //获取指定下标的元素

int hashCode() //hash值码

int indexOf(Object o) //返回元素在集合中首次出现的位置

boolean isEmpty() //判断是否为空

Iterator<E> iterator() //返回迭代器，遍历元素

int lastIndexOf(Object o) //返回元素最后出现的位置
 
 
E remove(int index) //移除指定位置的元素

boolean remove(Object o) //移除指定元素

boolean removeAll(Collection<?> c) //移除集合c中的所有元素
 
 
E set(int index, E element) //将指定位置元素替换为 element 并将替换后的元素返回

int size() //集合的元素个数

default void sort(Comparator<? super E> c)//指定比较器对元素排序 


List<E> subList(int fromIndex, int toIndex) //返回下标属于 [formIndex,toIndex) 的子集合

Object[] toArray() //将集合变为数组

3.2、ArrayList

ArryaList 是 list 接口的一个实现类，是程序中最常见的一种集合。
其内部封装了一个长度可变的数组对象，当存储元素大于数组长度时，其会在内存中分配更大的数组存储元素。
存储结构：数组，因为在进行增删操作时会创建新的数组，所以不适合大量的增删操作，而通过索引访问元素，所以遍历与查找比较高效
常用方法：因为父类为 list 、collection，所以可直接使用父类中的方法。

案例：

public class ListTest {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("v");
        list.add("a");
        System.out.println("集合中的元素个数为：" + list.size());//4
        System.out.println("集合中的最后元素为：" + list.get(list.size() -1 ));//a
        System.out.println("集合中的第一个元素为：" + list.get(0));//a
    }
}

3.2.1、源码分析：

按照上述案例分析：当创建 ArrayList<>() 对象时，加载如下变量，且通过构造方法将默认存放数据的空数组赋值给存放元素的数组

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	private static final int DEFAULT_CAPACITY = 10;//默认的容量大小，但是没有添加任何元素时，容量为 0 
    
    Object[] elementData;//存放元素的数组
    
    private int size;//实际集合中元素的个数
    
    //默认存放数据的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    //上述案例中调用的构造方法，将
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

当进行添加元素时：调用 add 方法，来进行添加元素

 //添加元素
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!! ；size = 0，所以 ensureCapacityInternal(1);
        elementData[size++] = e;
        return true;
    }

而 add（）方法内部又调用了 ensureCapacityInternal（）方法用于确定数组的大小（容量）

private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//elementData：添加的元素
    }

在 ensureCapacityInternal（）方法中又调用了 ensureExplicitCapacity（）来确定真正容量。其中 ensureExplicitCapacity（）又调用calculateCapacity（）方法计算容量.

private void ensureExplicitCapacity(int minCapacity) {//minCapacity = 10
        modCount++;

        if (minCapacity - elementData.length > 0)//minCapacity = 10；elementData.length = 0，所以为true
            grow(minCapacity);
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {//minCapacity = 1
    	//创建对象时，通过构造方法已经将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值 elementData
    	//所以为 true
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//true
            //计算最大的：DEFAULT_CAPACITY = 10；minCapacity = 1
            return Math.max(DEFAULT_CAPACITY, minCapacity);//所以这里返回的是 DEFAULT_CAPACITY
        }
        return minCapacity;
}

通过 calculateCapacity（）方法计算的容量的返回值，传递给 ensureExplicitCapacity（）方法。

所以 ensureExplicitCapacity(int minCapacity)中的 minCapacity = 10，而当开始时 elementData.length 是为 0 的，所以条件为 true，从而又调用了 grow(minCapacity)方法来进行数组扩容

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //MAX_ARRAY_SIZE大约10几亿，所以很大

private void grow(int minCapacity) {//minCapacity = 10
        
        int oldCapacity = elementData.length;//elementData.length = 0，所以 oldCapacity = 0
        
        int newCapacity = oldCapacity + (oldCapacity >> 1);// oldCapacity >> 1 相当于 0 / 2 = 0，即 newCapacity = 0
        
        if (newCapacity - minCapacity < 0)//0 - 10 < 0 条件成立
            newCapacity = minCapacity;	//newCapacity = 10
    
        if (newCapacity - MAX_ARRAY_SIZE > 0)//条件不成立
            newCapacity = hugeCapacity(minCapacity);
    
    
        //相当于创建数组长度为 10 的空数组，赋值给 elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    	
}

到此，数组容量确定，所以返回 add（）方法中，进行元素的添加。

总结：

1、当集合没有添加元素时，数组默认容量为 0 的，添加元素后（调用 add（）方法）数组容量变为 10

2、当添加元素为超过 10 时，在 grow（）方法中，对数组进行扩容，即 10 / 2 = 5 ，newCapacity = 15，内部条件判断都不成立，直接执行：

elementData = Arrays.copyOf(elementData, newCapacity); 所以扩容为原来的 1.5 倍

3.3、LinkedList

适合增删
底层结构：两个 Node 类型的 first、last 属性维护一个双向循环链表，元素都会记住前一个元素和后一个元素。

特有方法：

void add(int index, E element) //指定位置添加元素

void addFirst(E e)  //将指定元素添加到集合的开头

void addLast(E e) //将指定元素添加到集合的结尾

E getFirst()  //返回集合的第一个元素

E getLast() //返回集合的最后元素
 
boolean offer(E e) //将指定元素添加到集合的结尾

boolean offerFirst(E e)  //将指定元素添加到集合的开头
 
boolean offerLast(E e) //将指定元素添加到集合的结尾

E peek() //获取集合的第一个元素

E peekFirst() //获取集合的第一个元素

E peekLast() //获取集合的最后一个元素

E poll() //移除并返回集合的第一个元素

E pollFirst() ////移除并返回集合的第一个元素

E pollLast() //移除并返回集合的最后一个元素

E pop() //移除并返回集合的第一个元素
 
void push(E e) //将指定元素添加到集合开头

E remove() 

E remove(int index) //移除指定下标的元素
 
boolean remove(Object o) //移除指定元素

E removeFirst() //移除并返回第一个元素

E removeLast() //移除并返回最后一个元素 
    
E set(int index, E element) //将指定下标的元素替换为 element

int size() //集合元素个数

案例：

public class ListTest {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("a");
        list.add("c");
        list.add("v");
        list.add("a");
        System.out.println(list);//[a, c, v, a]

        list.offer("e");
        list.push("q");
        System.out.println(list);//[q, a, c, v, a, e]

        System.out.println(list.peek());//q
        System.out.println(list);//[q, a, c, v, a, e]

        list.removeFirst();
        list.pollLast();
        System.out.println(list);//[a, c, v, a]
    }
}

源码分析：

首先 LinkedList 类有如下变量：

public class LinkedList<E> extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;//元素个数
    
    transient Node<E> first;//头节点
  
    transient Node<E> last;//尾节点
	//构造方法
    public LinkedList() {
    }
}

其中 Node 类如下：

 private static class Node<E> {
        E item;//元素
        Node<E> next;//后指针
        Node<E> prev;//前指针
		//构造方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

到目前为止，通过上述可知 LinkedList底层是基于双向链表实现的。接下来看添加元素过程：

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

调用 add（）方法进行添加元素时，调用了 linkLast(e) 返回一个布尔类型值，其中 linkLast(e) 如下：

    void linkLast(E e) {
        //当第一次添加元素时：last = null，所以 l = null
        final Node<E> l = last;
        //第一次添加元素时：newNode 内部为：
        /*
            prev = l = null
            item = e；
            next = null；
        */
        final Node<E> newNode = new Node<>(l, e, null);
        //尾指针（尾节点）指向 新节点：newNode
        last = newNode;
        if (l == null)//第一次添加元素时，条件成立
            //头指针（头节点）指向新节点：newNode
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

上述方法过程如图：

按照数据结构中过程如下：

Vector

相对于 ArrayList 与 LinkedList 二者都线程不安全，线程安全的 Vector，

ArrayList 与 Vector 唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用 ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

四、泛型与工具类

4.1、泛型

1、简介

有时候除了元素的类型不确定，其他的部分是确定的，例如关于这个元素如何保存，如何管理等是确定的，因此此时把元素的类型设计成一个参数，这个类型参数叫做泛型。Collection，List，ArrayList 这个就是类型参数，即泛型。

就是允许在定义类、接口时通过一个标识表示类中某个属性的类型或者是某个方法的返回值及参数类型。这个类型参数将在使用时（例如，继承或实现这个接口，用这个类型声明变量、创建对象时）确定（即传入实际的类型参数，也称为类型实参）。

2、泛型声明

interface List<T> 和 class GenTest<K,V> 
其中，T,K,V不代表值，而是表示类型。这里使用任意字母都可以。
常用T表示，是Type的缩写。
//实例化时
//一定要在类名后面指定类型参数的值（类型）。如：
List<String> strList = new ArrayList<String>();
Iterator<Customer> iterator = customers.iterator();
//T只能是类，不能用基本数据类型填充。但可以使用包装类填充
//把一个集合中的内容限制为一个特定的数据类型，这就是generics背后的核心思想

注意：泛型如果不指定，将被擦除，泛型对应的类型均按照Object处理，但不等价于Object。经验：泛型要使用一路都用。要不用，一路都不要用。

3、自定义泛型

//类
class Person<T> {
    // 使用T类型定义变量
    private T info;
    // 使用T类型定义一般方法
    public T getInfo() {
    	return info;
    }
    public void setInfo(T info) {
    	this.info = info;
    }
    // 使用T类型定义构造器
    public Person() {
    }
    public Person(T info) {
    	this.info = info;
    }
}
//方法：[访问权限] <泛型> 返回类型 方法名([泛型标识 参数名称]) 抛出的异常
public class DAO {
    public <E> E get(int id, E e) {
        E result = null;
        return result;
    }
}
/*
注意： 
1、static的方法中不能声明泛型
2、不能在try-catch中使用泛型定义
3、静态方法中不能使用类的泛型。
4、父类使用通用泛型，则子类要么部分泛型指定，或全部指定，否则泛型会被擦除
*/

4.2、常用工具类

1、collections工具类

Collections 是一个操作 Set、List 和 Map 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

常用方法：

//排序操作：（均为static方法）
reverse(List)：//反转 List 中元素的顺序
shuffle(List)：//对 List 集合元素进行随机排序
sort(List)：//根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List，Comparator)：//根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：//将指定 list 集合中的 i 处元素和 j 处元素进行交换

//查找、替换
Object max(Collection)：//根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection，Comparator)：//根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：//返回指定集合中指定元素的出现次数
void copy(List dest,List src)：//将src中的内容复制到dest中
boolean replaceAll(List list，Object oldVal，Object newVal)：//使用新值替换List 对象的所有旧值

2、Arrays工具类

是操作数组的工具类

常用方法：

static <T> List<T> asList(T... a) //返回由指定数组支持的固定大小的列表。  
static boolean[] copyOf(........) // 复制数组
static void sort(........) //数组排序。

五、Set 接口与实现类

5.1、简介

因为继承自 Collection，且没有对 Collection 接口进行功能上的扩充，所以 collection 中的方法依然适用于 set

特点：元素无序，不重复
实现类：HashSet、TreeSet
- HashSet:根据对象的哈希值来确定元素在集合中的位置。适合的存取和查找操作
- TreeSet:以平衡二叉树的形式存储元素，可以对元素进行排序操作

5.2、HashSet

无序且不重复
添加元素时，会先调用该元素的 hashCode（）方法来确定元素的存储位置，再调用元素的 equals（）方法确保该位置上没有重复的元素

案例：

public class ListTest {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("a");
        set.add("b");
        set.add("c");
        set.add("a");
        set.forEach(e-> System.out.println(e));//a b c
    }
}

添加元素的过程：

通过上述可知，当向 HashSet 集合添加元素是，需要注意该元素是否已重写 equals（）与 hashcode（）方法。否则添加元素时会出现重复的元素

HashSet底层是通过 HashMap 实现的，所以源码可看 HashMap。

HashSet源码：从源码可证明 HashSet 底层是通过 HashMap 实现的。

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

    private transient HashMap<E,Object> map;

    
    private static final Object PRESENT = new Object();
	//构造方法
    public HashSet() {
        map = new HashMap<>();
    }
    //添加元素
	public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

规律总结：1、底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32，依次为64,128....等）

2、数组加链表方式，当同一位置有元素时，会以链表方式连在数组下方。

5.3、TreeSet

有序且不重复
底层为使用红黑树结构存储数据
使用红黑树结构存储数据：左 < 根 < 右
有序，查询速度比List快

特有方法：

E first() //返回集合中首个元素

E floor(E e) //返回集合 >= 指定元素 e 的 最大元素，如果没有返回 null

E higher(E e) //返回集合 > 指定元素 e 的 最小元素，如果没有返回 null

E last() //返回集合最后一个元素

E lower(E e) //返回集合 > 指定元素 e 的 最大元素，如果没有返回 null

E pollFirst() //移除并返回集合的第一个元素

E pollLast() //移除并返回集合的最后一个元素

E ceiling(E e) //返回集合 >= 指定元素 e 的 最小元素，如果没有返回 null

案例：

public class ListTest {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("a");
        treeSet.add("b");
        treeSet.add("c");
        treeSet.add("a");
        treeSet.forEach(e-> System.out.println(e));// a b c
        
    }
}

注意：如果添加的是自定义对象的话，需要在其内部自定义排序规则。可通过实现 comparable 接口或 comparator 接口

5.4、自然排序

TreeSet 集合中需要添加自定义的对象时，可通过实现 Comparable 接口，重写其中的 compareTo（）方法。

这样当向 TreeSet 集合中添加该对象时，集合会对该类型的对象调用 compareTo（）方法进行比较。默认升序排序

案例：

class Anilam implements Comparable{
    private Integer id;
    private String name;
    private Integer age;

    @Override
    public int compareTo(Object o) {
        Anilam anilam = (Anilam) o;
        if (this.age - anilam.age > 0){
            return -1;
        }
        if (this.age - anilam.age == 0){
            return this.name.compareTo(anilam.name);
        }
        return 1;
    }
}

5.5、自定义排序

通过 Comparator 接口中的 compare（）方法可进行自定义排序。不过在创建 TreeSet 集合时，需要把自定义的排序传入。

public class ListTest {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>(new MyComparator());
        String [] str = new String[]{"sa","fa","df"};
        System.out.println(str.length);
    }
}
class MyComparator implements Comparator{

    @Override
    public int compare(Object o1, Object o2) {
        String s = (String) o1;
        String s2 = (String) o2;
        return s.length()-s2.length();
    }

}

5.6、linkedHashSet

LinkedHashSet 是 HashSet 的子类
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。
LinkedHashSet 不允许集合元素重复。
底层也是数组加链表，不过链表为双向链表

六、Collection 遍历

6.1、iterator 遍历

iterator：迭代器，用于迭代访问集合中的元素。

常用方法：

 boolean hasNext() //判断集合是否还有下一元素

E next() //取出元素
     
void remove()//移除集合元素

首先有指针指向集合第一个元素的前一个位置上，当通过 hasNext() 判断是否还有下一元素时，有则调用 next（）方法指向第一个元素，再次调用 next（）方法时，指向第二个元素，依次类推，直到指针指向最后元素的后一位置时，hasNext（）返回 false，循环结束。

案例：

public class ListTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("s");
        list.add("ab");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);//a s ab
        }

    }
}

6.2、foreach 遍历

类似 for 循环，不过是 for 循环的简写版。

语法：

for(类型 变量 : 集合变量){
}

//jdk8的循环
集合.forEach(e->System.out.println(e));

七、Map 接口与实现类

7.1、简介

Map与Collection并列存在。用于保存具有映射关系的数据:key-value
Map 中的 key 和 value 都可以是任何引用类型的数据
Map 中的 key 用 Set 来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value
Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和 Properties。其中，HashMap是 Map 接口使用频率最高的实现类
key 不允许重复（唯一），value 允许重复

常用方法：

//添加、删除、修改操作：
Object put(Object key,Object value)	//：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m)	//:将m中的所有key-value对存放到当前map中
Object remove(Object key)	//：移除指定key的key-value对，并返回value
void clear()	//：清空当前map中的所有数据
    
//元素查询的操作：
Object get(Object key)		//：获取指定key对应的value
boolean containsKey(Object key)	//：是否包含指定的key
boolean containsValue(Object value)	//：是否包含指定的value
int size()	//：返回map中key-value对的个数
boolean isEmpty()	//：判断当前map是否为空
boolean equals(Object obj)	//：判断当前map和参数对象obj是否相等

//元视图操作的方法：
Set keySet()	//返回所有key构成的Set集合
Collection values()	//返回所有value构成的Collection集合
Set entrySet()//：返回所有key-value对构成的Set集合

案例：

public class ListTest {
    public static void main(String[] args) {
        Map<String, Object> map = new HashMap<>();
        map.put("1001", 20);
        map.put("1002", 20);

        //获取所有key
        Set<String> keySet = map.keySet();
        keySet.forEach(e-> System.out.println(e));//1002 1001

        //获取全部value
        Collection<Object> values = map.values();
        Iterator<Object> iterator = values.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//20 20
        }

        //获取 Entry
        Set<Map.Entry<String, Object>> entries = map.entrySet();
        for (Map.Entry<String, Object> entry : entries) {
            System.out.println("key=" + entry.getKey() + ",value="+entry.getValue());//key=1002,value=20 key=1001,value=20
        }
    }
}

7.2、HashMap

HashMap 是 Map 接口使用频率最高的实现类。
允许使用null键和null值，与 HashSet 一样，不保证映射的顺序。
所有的 key 构成的集合是 Set:无序的、不可重复的。所以，key 所在的类要重写： equals()和hashCode()
所有的 value 构成的集合是 Collection:无序的、可以重复的。所以，value 所在的类要重写：equals()
一个 key-value 构成一个entry
所有的 entry 构成的集合是 Set:无序的、不可重复的
HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true， hashCode 值也相等。
HashMap 判断两个 value 相等的标准是：两个 value 通过 equals() 方法返回 true。

常用方法见 Map

7.2.1、底层源码

HashMap 底层是哈希表（数组 + 链表 + 红黑树）

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    //HashMap的默认容量
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
	// HashMap的最大支持容量
    static final int MAXIMUM_CAPACITY = 1 << 30; //2 ^ 30: 2的 30次方
	//HashMap的默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//
	//当链表长度大于 该默认值 时，链表转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
	//当树长度小于 6 ，转为链表
    static final int UNTREEIFY_THRESHOLD = 6;
	//最小树容量大小，即当 数组长度大于 64，链表长度大于 TREEIFY_THRESHOLD ，将链表转为 红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    transient Node<K,V>[] table; //存储元素的数组，总是2的n次幂，刚创建集合时，为null，添加元素后才有值
    
	transient Set<Map.Entry<K,V>> entrySet;	//存储具体元素的集
    
    transient int size;		//HashMap中存储的键值对的数量，刚创建集合时，为0，添加元素后才有值

    transient int modCount;		//HashMap扩容和结构改变的次数。
    
    int threshold;		//扩容的临界值，=容量*填充因子

    final float loadFactor;//填充因子
    //无参构造
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 
    }
}

当数组添加的元素 > 16（DEFAULT_INITIAL_CAPACITY）乘以 0.75（加载因子）时，数组大小扩容为原来 2 倍。证明如下：

首先，调用 put 方法时，又调用了 putVal（）方法，在 putVal（）方法中第五行又调用了 resize() 方法。在 resize() 方法中第三行将 oldCap 赋值为 0 后，执行第 18 行将 newCap 赋值为 16 ，又在第 28~29行为数组初始化。到此数组初始化完成，又到 putVal（）方法中第 6~7行进行添加元素。

又当添加元素（putVal（）第11~12 行）的个数大于默认容量乘以加载因子时，又调用 resize() 方法。在 resize() 方法中第11~13行中进行扩容变为两倍即16-----》32

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<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //................
    	//................
        ++modCount;
        if (++size > threshold)// threshold=16 * 加载因子= 12
            resize();
        afterNodeInsertion(evict);
        return null;
    }

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap = 0
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            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
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        
        return newTab;
    }

总结:

1、HashMap 刚创建时，table 数组为 null，size = 0（为了节省空间），当添加第一个元素时，table数组容量变为 16

2、当添加元素个数大于阈值（16 * 0.75）时，会进行扩容，扩容大小为原来的 2 倍。目的是减少元素个数

3、当每个链表长度大于 8 ，且元素个数大于等于 64 时，会调整为红黑树。目的是提高效率

4、当链表长度小于 6 时，调整为链表

5、jdk 8以前，链表是头插法，后改为尾插法

7.3、LinkedHashMap

LinkedHashMap 是 HashMap 的子类
在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
与 LinkedHashSet 类似，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致

一般来说进行插入、删除、定位元素，HashMap常用。而需要迭代顺序则使用其。

7.4、TreeMap

TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序,可以保证所有的 Key-Value 对处于有序状态。
TreeSet底层使用红黑树结构存储数据
具体的与TreeSet类似，需要排序（自然排序与自定义排序）见 TreeSet

7.5、Hashtable

Hashtable是线程安全的。是个古老的 Map 实现类，
Hashtable是线程安全的。
Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value
与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序
Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。

7.6、Properties

Properties 类是 Hashtable 的子类，该对象用于处理属性文件
由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型
存取数据时，建议使用 setProperty(String key,String value)方法和 getProperty(String key)方法

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);