Java两大集合：Collection 和 Map 源码及总结

Java两大集合：Collection 和 Map 源码及总结

---

---

一、纵览Collection与Map

1、数组与集合的优缺点

数组：

1. 长度固定、存储同一类型元素的一块连续的存储空间。（一旦指定不能更改，无法动态扩容）
2. 不利于频繁发生插入和删除操作。

集合：

1. 可以动态保存任意多个对象，比较方便。
2. 功能更丰富。

2、集合分类、类图

3、Collection与Map接口简介、线程安全性

|----Collection接口：单列集合，用来存储一个一个的对象
     |----List接口：存储有序的、可重复的数据。一种包含有序元素的线性表
                    可以存放多个null值。可称之为 “动态”数组
           |----ArrayList：作为List接口的主要实现类,多用于频繁的改查操作,**线程不安全,效率高**
           |----LinkedList:对于频繁的插入删除操作,**使用此类效率比ArrayList效率高,线程也不安全**                                     
           |----Vector(不咋用了)：作为List的古老实现类，**线程安全，效率低**
           
     |----Set接口：存储无序的、不可重复的数据   
           |----HashSet：作为Set接口主要实现类; **线程不安全**; 可以存null值
           		|----LinkedHashSet：作为HashSet的子类;遍历其内部数据时，可以按照添加顺序遍历;对于频繁的遍历操作，**LinkedHashSet效率高于HashSet**
           |----TreeSet：可以按照添加对象的指定属性，进行排序
 
|--------Map接口:存储key-value对的数据，双列数据
     	   |----HashMap:作为Map的主要实现类；**线程不安全，效率高**；
     	            可存储key和value可以为null,且值（value）可以存在多个null，键（key）只能出现一个null，若key中出现多个null，其结果是对第一个null的值进行覆盖
          		|----LinkedHashMap:保证在遍历时，可以照添加的顺序实现遍历。对于频繁的遍历操作，**此类执行效率高于HashMap**。
                    原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
           |----TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用红黑树
           |----Hashtable(不咋用了):作为古老的实现类；**线程安全，效率低**；不能存储null的key和value 
                |----Properties:常用来处理配置文件。key和value都是String类型

4、List、Set、Map底层结构

List

Arraylist ： Object[] 数组
Vector ： Object[] 数组
LinkedList ： 双向链表(JDK1.6之前为循环链表，JDK1.7 取消了循环)

Set（内部元素具有唯一性）

HashSet : 基于 HashMap 实现的，底层采? HashMap 来保存元素。（无序）
LinkedHashSet ： 是HashSet 的子类，并且其内部是通过LinkedHashMap 来实现的。
TreeSet：红黑树(自平衡的排序二叉树)（有序）

Map

HashMap ：JDK1.8 之前 HashMap = 数组+链表。JDK1.8 之后 HashMap = 数组+链表+红黑树。
LinkedHashMap ：LinkedHashMap 继承自 HashMap。但，LinkedHashMap = 数组+链表+红黑树+双向链表，使得上面的结构可以保持键值对的插入顺序。
Hashtable ： = 数组+链表
TreeMap ： 红黑树(自平衡的排序二叉树)

二、Collection接口

1、常用方法

方法	描述
add(Object obj)	添加
addAll(Collection coll)	添加整个集合
int size()	获取有效元素个数
void clear()	清空集合
boolean isEmpty()	判断是否为空集合
boolean contains(Object obj)	是否包含某个元素 （通过元素的equals方法来判断是否是同一个对象）
containsAll(Collection c)	调用元素的equals方法来比较的。用两个两个集合的元素逐一比较
boolean remove(Object obj)	通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll)	取当前集合的差集
boolean retainAll(Collection c)	取两个集合的交集，把交集的结果存在当前的集合中，不影响c
boolean equals(Object obj)	集合是否相等
Object [] toArray()	转换成对象数组
hashCode()	获取集合对象的哈希值
iterator()	返回迭代器对象，用于集合遍历

2、遍历之 Iterator迭代器

//通过调用collection接口的iterator()方法进行输出
        Iterator iterator = col.iterator(); //获取迭代器对象，通过使用迭代器来输出每一行元素
        while (iterator.hasNext()) { //hasNext():判断游标右边是否还有下一个元素，默认游标都在集合的第一个元素之前。注意：此时只是判断是否有下一个元素，并不移动指针。
            Object next =  iterator.next(); //next():①指针下移 ②将下移以后集合位置上的元素返回
            System.out.println("next="+next);
        }
        //当退出while后，iterator.hasNext()中next已经走到尾部，若继续调用iterator.hasNext()将会报错
        //可以通过 iterator=col.iterator(); 来重置迭代器

3、遍历之 增强for循环

//使用foreach（底层也是通过迭代器实现,可以理解为简化版的迭代器遍历。也可以直接在数组中使用;）
        for (Object book:col) {
            System.out.println("book="+book);
        }

三、Collection——>List接口

List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List接口底层以数组方式进行对象存储,允许存放null元素

1、常用方法

方法	描述
void add(int index, Object ele)	在index位置插入ele元素
boolean addAll(int index, Collection eles)	从index位置开始将eles中的所有元素添加进来
Object get(int index)	获取指定index位置的元素
int indexOf(Object obj)	返回obj在集合中首次出现的位置
int lastIndexOf(Object obj)	返回obj在当前集合中末次出现的位置
Object remove(int index)	移除指定index位置（0是第一个元素）的元素，并返回此元素
Object set(int index, Object ele)	设置指定index位置的元素为ele

2、实现类之一：ArrayList

• 线程不安全，执行效率高，多线程下不建议使用
• ArrayList 可以加入null,并目多个。permits all elements, including null
• ArrayList 是由Object类型数组来实现数据存储的
• ArrayList 基本等同于Vector，除了 ArrayList是线程不安全

扩容机制概述

1. ArrayList中维护了一个Object类型的数组 Object[] elementData.
2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍.
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

ArrayList 底层源码——添加数据
首先，创建一个ArrayList对象

ArrayList arrayList = new ArrayList();
三种构造器：
 1.ArrayList():构造一个默认大小为10容量的空列表。
 2.ArrayList(int initialCapacity):构造一个大小为指定int initialCapacity容量的空列表。
 3.ArrayList(Collection c):构造一个和参数c相同元素的ArrayList对象

ArrayList的JDK 1.8之前与之后的实现区别？
JDK 1.7：直接创建一个初始容量为10的数组
JDK 1.8：一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组

//无参构造器
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_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);
        }
    }
//创建了一个指定大小的elementData数组 this.elementData = new Object[capacity]
//如果是有参构造器,第一次扩容,就按照elementData的1.5倍扩容

添加元素，调用add(E e) 方法

 for (int i = 0; i < 10; i++) {
            arrayList.add(i);
}
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 第一次调用add()方法时，size=0
        elementData[size++] = e;
        return true;
    }

调用ensureCapacityInternal(int minCapacity)方法,对数组容量进行检查，不够时则进行扩容。

private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData为"{}"即第一次调用add(E e)，重新定义minCapacity的值，赋值为DEFAULT_CAPACITY=10
    // 即第一次调用add(E e)方法时，定义底层数组elementData的长度为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity 判断是否需要扩容

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
// 第一次进入时，minCapacity=10,elementData.length=0,对数组进行扩容
// 之后再进入时，minCapacity=size+1，elementData.length=10(每次扩容后会改变)，
// 需要minCapacity>elementData.length成立，才能扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); 
    }

grow(minCapacity) 对数组进行扩容

private void grow(int minCapacity) {
        // 将数组长度赋值给oldCapacity
        int oldCapacity = elementData.length;
    	// 将oldCapacity右移一位再加上oldCapacity，即相当于newCapacity=1.5oldCapacity(不考虑精度损失)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    	// 如果newCapacity还是小于minCapacity，直接将minCapacity赋值给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    	// 特殊情况：newCapacity的值过大，直接将整型最大值赋给newCapacity，
	// 即newCapacity=Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将elementData的数据拷贝到扩容后的数组。真正让数组容量发生改变的地方！
        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;
    }

3、实现类之二：Vector

• Vector底层也是一个对象数组，Object[] elementData
• Vector是线程同步的，即线程安全，是有synchronized修饰
• 开发中如果需要线程安全，考虑使用Vector

创建一个Vector对象

1.Vector():构造一个构造一个元素个数为0的Vector对象，为其分配默认大小的容量。
2.Vector(int size):构造一个构造一个元素个数为0的Vector对象，为其分配默认大小为size的初始容量。
3.Vector(Collection c):构造一个和参数c相同元素的ArrayList对象
4.Vector(int initalcapacity,int capacityincrement):构造一个构造一个元素个数为0的Vector对象，为其分配大小为 initalcapacity的初始容量。并指定vector中的元素个数达到初始容量时，vector会自动增加大小为capacityincrement的容量

Vector与ArrayList比较

	底层结构	安全/效率	扩容倍数
ArrayList	可变数组	不安全、效率高	如果有参构造1.5，如果无参，第一次10，第二次按照1.5倍
Vector	可变数组	安全、效率不高	如果无参，默认10，第二次按照2倍 如果指定大小，则每次按照2倍

4、实现类之三：LinkedList

• LinkedList底层是一个双向链表
• LinkedList中维护了两个属性first last 分别指向头结点和尾结点。每个结点（Node对象）中又有三个属性 prev next item
• 添加和删除时间复杂度低，效率高 。可以添加任意元素，可重复，可为null
• 线程不安全的

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

ArrayList 底层源码
首先，创建一个LinkList对象

1.LinkedList():构造一个空的LinkedList对象。
2.LinkedList(Collection c):构造一个和参数c相同元素的LinkedList对象

LinkedList新增方法

方法	功能说明
void addFirst(Object obj)	在链表头部插入一个元素
void addLast(Object obj)	在链表尾部添加一个元素
Object getFirst()	获取第一个元素
Object getlast)()	获取最后一个元素
Object removeFirst()	删除头元素
Object removeLast()	删除尾元素
Object peek()	获取但不移除第一个元素
Object poll()	获取并移除第一个元素

ArrayList和LinkedList比较

	底层结构	增删的效率	查改的效率
ArrayList	可变数组	较低，数组扩容	较高
LinkList	双向链表	较高，通过链表追加	较低

如何选择ArrayList和LinkedList:

1)如果我们改查的操作多，选择ArrayList
2如果我们增删的操作多，选择LinkedList
3一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList
4)在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList.

四、Map接口

1、Map概述及常用方法

• Map 接口没有从 Collection 接口继承。他俩是并列的。
• 一个 Map中键必须是唯一的，不能有重复的键，因为Map中的“键-值”对元素是通过键来唯一标识的。
• Map 的key 可以为 null, value 也可以为null ，注意 key 为null,只能有一个。
  value 为null ,可以多个。
• Map 的键是用 Set 集合来存储的,所以充当键元素的类必须重写hashCode和equals 方法。通过键元素key来检索对应的值元素value。

Map常用方法

方法	功能说明
put	添加
remove	根据键，删除映射关系
get	根据键获取值
size	获取元素个数
containsKey	查找键是否存在
keySet()	返回Map中所有的key键
entrySet()	返回Map中所有的键值对
values()	返回Map中所有的value值
replace()	替换Map中指定key对应的value
isEmpty	判断个数是否为0
clear	清除

2、Map遍历方式(6种)

		//1.通过keySet
        // (1)增强for
        for (Object key : map.keySet()){
            System.out.println(key + "-" + map.get(key));
        }
        // (2)迭代器
        Iterator iterator = map.keySet().iterator();
        while (iterator.hasNext()) {//快捷键itit
            Object key =  iterator.next();
            System.out.println(key + "-" + map.get(key));
        }
        //2.把所有的values取出
        Collection values = map.values();
        //这里可以使用所有collections使用的遍历方法
         //(1)增强for
        for (Object value:
             values) {
            System.out.println(value);
        }
         //(2)迭代器
        Iterator iterator1 = values.iterator();
        while (iterator1.hasNext()) {
            Object next =  iterator1.next();
            System.out.println(next);
        }
        //3.通过entrySet来获取k-v
        //(1)增强for
        Set entrySet = map.entrySet();
        for (Object o:
             entrySet) {
           //将entry转成Map.Entry
            Map.Entry entry = (Map.Entry) o;
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }
        //(2)迭代器
        Iterator iterator2 = entrySet.iterator();
        while (iterator2.hasNext()) {
            Object next =  iterator1.next();
            Map.Entry entry = (Map.Entry) next;
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }

3、实现类之一：HashMap

• 无序（添加顺序和取出顺序不一致），没有索引
• HashMap最多只能有一个记录的key为null，但可以有多个value为null。
• 虽然取出顺序和添加顺序不一致，但是取出顺序是固定的，每次都一样
• 遍历方式：迭代器、增强for，但是不能通过索引
• 是线程不安全的
• 对于存在HashSet集合中的元素需要重写equals()方法和HashCode()方法
• 如果添加相同的key，则会覆盖原来的key-val,等同于修改.(kev不会替换，val会替换)

构造方法

1.HashSet()构造一个新的空集合;HashMap实例具有默认初始容量(16) 和负载因子 (0.75)
2.Hashset(Collection<? extends E> c)构造一个包含指定集合中的元素的新集合
3.HashSet(int initialCapacity)构造一个新的空集合;实例具有指定的初始容量和默认负载因子 (0.75)
4.HashSet(int initialCapacity, float loadFactor)构造一个新的空集合;实例具有指定的初始容量和指定的负载因子.

扩容机制概述

1. HashMap底层维护了Node类型的数组table，默认为null。当创建对象时，将加载因子(loadfactor)初始化为0.75。
2. 当我们往HashMap中存储数据时，首先会利用hash(key)方法 计算出key的hash值，再利用该 hash值 与 HashMap数组的长度-1 进行 与运算，从而得到该key在数组中对应的下标位置。然后判断该索引处是否有元素。
3. 如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等，如果相等(equals方法)，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
4. 第1次添加，则需要扩容table容量为16，临界值(threshold)为12。
5. 以后再扩容则需要扩容table容量为原来的2倍，临界值为原来的2倍，即24，依次类推 。
6. 在Java8中，如果一条链表的元素个数超过 TREEIFY THRESHOLD(默认是 8)，并且table的大小>= MIN TREEIFY CAPACITY(默认64)，就会进行树化(红黑树)。

HashMap底层实现

其基本数据单元为Entry<K,V> 。（此时将hash值，作为了一个属性固定住）

那么为什么HashMap要采用数组+链表+红黑树这种存储方式呢？
数组的特点是查找快，长度有限，但使用hash来确定数组角标容易产生hash碰撞，这就不得不使用链表。在根据key查找value时，先对key进行hash计算，这样就可以快速的定位但数组的某个位置。但这个位置可能有多个节点，因此就需要沿着链表依次比对key。但当这个链表过长时，就会使得在链表上查找花费的时间过长。因此当链表数量达到8时，要么对数组进行扩容，减少hash碰撞的概率，要么将链表进行树化，提升key的查找效率。

HashMap底层源码——添加数据

package com.eveningliute.set_;
 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class SetDemo {
    public static void main(String[] args) {
        Set set = new HashSet();
        for(int i=0;i<13;i++){
            set.add(i);
        }
        System.out.println(set);
 
//以下为源码解读
        /**
         * 1、public HashSet() {
         *         map = new HashMap<>();
         *     }//HashSet的构造方法中可以看出，底层实际是实现了HashMap
		*/
         //添加元素，调用map.put()方法
         public boolean add(E e) {
             return map.put(e, PRESENT)==null;
         }
         //2、首先进行添加元素时，要先通过计算其hash值来确认要添加到数组位置索引
         public V put(K key, V value) {
         	return putVal(hash(key), key, value, false, true);
         }
         //这里是计算其hash值得方法
         //第一步：计算出key的hashCode值（key就是传进来的元素）
         //第二步：将计算出的hashCode值再无符号右移16位得到最终的hash值
         static final int hash(Object key) {
         	int h;
         	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
         }
         //!!!!!下面是上面putVal()方法的源码;
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
         //这里定义的都是一些辅助变量
             Node<K,V>[] tab; Node<K,V> p; int n, i;
         //3、第一步：第一次添加元素时先判断table表是否为null，
         //如果为null将通过resize()方法扩容给table赋初始容量（16）
            //接下来每一次都是当集合容量达到扩容阈值时调用resize()方法进行扩容
         	if ((tab = table) == null || (n = tab.length) == 0)
            	n = (tab = resize()).length;
         //第二步：每一次向集合中添加元素的时候，会调用该元素的hashCode()方法得到一个地址值，
         //接着将得到的地址值放进tab数组中进行查询，若当前位置为null直接将元素添加到当前位置。
         	if ((p = tab[i = (n - 1) & hash]) == null)
            	tab[i] = newNode(hash, key, value, null);
         //第三步：如果当前位置已经存放元素，那么会先判断当前传进来的对象和已有对象是否是同一对象
         //或者调用equals方法进行比较，如果满足其一，新的元素将会覆盖原先对象的值
         	else {
            	Node<K,V> e; K k;
         		if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
             		e = p;
         //这里主要是用来判断当前对象是否已经树化，如果树化将会调用红黑树的添加方法进行元素添加
         		else if (p instanceof TreeNode)
             		e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         //经过比较当前传入元素与当前元素所处tab数组位置处的元素不是同一对象，
         //则与当前位置对象next所以指的对象一一比较，如果p.next==null就直接将当前元素添加去。
         		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;
         				}
         				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;
         }
         //resize()数组扩容方法解析
         //第一步：判断table表是否为null，如果为null，则为table表进行容量开辟
         //newCap = DEFAULT_INITIAL_CAPACITY; 默认的初始值为DEFAULT_INITIAL_CAPACITY(16);
         //newThr = (int)(DEFAULT_LOAD_FACTOR (0.75)* DEFAULT_INITIAL_CAPACITY);
         //扩容阈值为：newThr=16*0.75=12;当集合容量达到12时再次调用resize()方法进行扩容
         //第二步：当进行第二次扩容，以及之后每一次扩容的时候，每次到达扩容阈值的时候,
         //容量扩容到原先的两倍
         //newCap = oldCap << 1
         //新的扩容阈值为：newThr=newCap*0.75=24，以此类推(12,24,36,48.....)
         final Node<K,V>[] resize() {
         	Node<K,V>[] oldTab = table;
         	int oldCap = (oldTab == null) ? 0 : oldTab.length;
         	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;
          
    	}
}

3.1、HashMap的实现类：LinkedHashMap

LinkedHashMap继承了HashMap类。
将Node<k_v>这种单链表的基础上，多了个before，after指针，一个节点指向单向链表下一个节点的同时，还指向了它的上一个插入元素和下一个要插入的元素。

这样就使得map的插入能有先后顺序，能在原数组和链表的基础上，通过第一个插入的节点顺着链表能一直找到最后一个节点。

static class Entry<K,V> extends HashMap.Node<K,V> {
    // 可以看到 它继承了 HashMap中的 Node结点（有一个next指针）
    // 同时又新增了两个指针，前驱指针before，后继指针after
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

4、实现类之二：TreeMap

底层使用的是红黑树，我们暂时可以不用分析，重点要注意存储的对象Entry<K,V>是进行保存键值对的

5、实现类之三：HashTable

哈希表、散列表
底层结构：数组+链表

存放的是键值对 k - v， 键和值都不能为null
hashTable是线程安全的，hashMap是线程不安全的
整体扩容机制与HashMap类似
已经不太用了

5.1、HashTable的实现类：Properties

properties主要用于 从 .properties 文件中，加载数据到properties类对象，并读取和修改。
key和value都是String类型。

五、Set接口

基本都继承了Map

1、实现类之一：HashSet

HashSet底层其实是 HashMap，HashMap底层是数组+链表+红黑树

1.1、HashSet的实现类：LinkedHashSet

• LinkedHashSet底层是LinkedHashMap，底层是 数组 + 双向链表
• LinkedHashSet同时使用双向链表维护元素的次序，因此，加入顺序和取出元素的顺序是一致的

底层扩容机制
与上面HashSet HashMap扩容机制相同

2、实现类之二：TreeSet

底层使用的是红黑树，我们暂时可以不用分析。

1.当我们使用无参构造器创建TreeSet时,仍然是无序的
2.如果想要添加的元素按照一定规则排序,可以使用有参构造,传入比较器(匿名内部类)

但是TreeSet仅是单列数据，不是键值对，所以规定 K表示所要保存的数据，而V用一个new object固定占位符替代；
跟上面分析HashSet和HashMap异曲同工

---

总结

1. 开发中如何选择集合的实现类

1. 先判断存储的数据类型（是一组对象、还是一组键值对）

2. 一组对象，选择Collction接口下的List或Set

   1. 允许数据重复，则选择List

      • 增删频繁，选择LinkedList（底层使用双向链表实现）
      • 修改查询频繁，选择ArrayList（底层使用的是Object类型的可变数组）

   2. 不允许数据重复，则选择Set

      • 允许无序排列，选择HashSet（底层使用HashMap，使用数组+链表+红黑树）
      • 要求排序，选择TreeSet(底层使用TreeMap，使用红黑树)
      • 只要求插入和取出顺序一致，则选择LinkedHashSet（底层使用
        数组+双向链表）

3. 一组键值对，选择Map接口下的实现类

   1. 键无序排列，则选择HashMap（在JDK8中，使用数组+链表+红黑树）
   2. 键要排序，则选择TreeMap（底层使用红黑树）
   3. 键插入顺序和取出顺序一致，选择LinkedHashMap