一、集合基本框架结构
java集合基本结构可分为两大类：Collection和Map两种体系
1、collection接口：单列数据，定义了存取一组对象的方法和集合
2、Map接口：双列数据，保存具有映射关系的“key-value对”的集合
1、conllection常用子接口
List接口：常用的有ArrayList、LinkedList、Vector...
Set接口：分为HashSet、TreeSet、LinkedHashSet
2、Map常用子接口
Hashtable、LinkedHashMap、HashMap、TreeMap、Properties
|----Collection接口：单列集合，用来存储一个一个的对象
|----List接口：一种包含有序元素的线性表，可存储有序的、可重复的数据。
可以存放多个null值。 -->“动态”数组
|----ArrayList：作为List接口的主要实现类,多用于频繁的改查操作,线程不安全的,效率高;
底层采用Object[] elementData数组存储。
|----LinkedList:对于频繁的插入删除操作,使用此类效率比ArrayList效率高,线程也不安全
底层采用双向链表存储
|----Vector：作为List的古老实现类，线程安全的，效率低;
底层采用Object[]数组存储
|----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:保证在遍历map元素时，可以照添加的顺序实现遍历。
原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，此类执行效率高于HashMap。
|----TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用红黑树
|----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
|----Properties:常用来处理配置文件。key和value都是String类型
二、collection接口
1、collection常用方法
1、添加
add(Object obj)
addAll(Collection coll)
2、获取有效元素个数
int size()
3、清空集合
void clear()
4、判断是否为空集合
boolean isEmpty()
5、是否包含某个元素
boolean contains(Object obj):是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c):也是调用元素的equals方法来比较的。用两个两个集合的元素逐一比较
6、删除
boolean remove(Object obj):通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll):取当前集合的差集
取两个集合的交集
boolean retainAll(Collection c):把交集的结果存在当前的集合中，不影响c
7、集合是否相等
boolean equals(Object obj)
8、转换成对象数组
Object [] toArray()
9、获取集合对象的哈希值
hashCode()
10、遍历
iterator()：返回迭代器对象，用于集合遍历
2、Iterator接口的使用（以及JDK5.0新特性-增强for循环：（foreach循环）的使用）
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionIterator {
public static void main(String[] args) {
Collection col=new ArrayList();
col.add(new Book1("许贯中","三国演义",40));
col.add(new Book1("曹雪芹","红楼梦",10));
col.add(new Book1("吴承恩","西游记",50));
//Iterator迭代器的使用
//第一种输出方式，通过调用collection接口的iterator()方法进行输出
Iterator iterator = col.iterator();//通过使用迭代器来输出每一行元素
while (iterator.hasNext()) { //快捷键：itit
Object next = iterator.next();
System.out.println("next="+next);
}
//当退出while后，iterator.hasNext()中next已经走到尾部，若继续调用iterator.hasNext()将会报错
//可以通过 iterator=col.iterator(); 来重置迭代器
//第二种输出方式
//使用foreach（底层也通过迭代器实现）
for (Object book:col) {
System.out.println("book="+book);
}
}
}
class Book1{
private String name;
private String bookName;
private int price;
public Book1(String name,String bookName,int price){
this.name=name;
this.bookName=bookName;
this.price=price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getBookName() {
return bookName;
}
public void setBookName(String bookName) {
this.bookName = bookName;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
@Override
public String toString() {
return "{" +
"name='" + name + '\'' +
", bookName='" + bookName + '\'' +
", price=" + price +
'}';
}
}
3、Iterator()方法细节解释
Iterator iterator = col.iterator();//获取迭代器对象
//hasNext():判断游标右边是否还有下一个元素，默认游标都在集合的第一个元素之 前。注意：此时只是判断是否有下一个元素，并不移动指针。
while(iterator.hasNext()){
//next():①指针下移 ②将下移以后集合位置上的元素返回
Object next = iterator.next();
System.out.println("next="+next);
}
1、 如果iterato.next()指向的内存中如果没有元素会抛出异常
2、当退出while后，iterator.hasNext()中next已经走到尾部，若继续调用iterator.hasNext()将会报错（若要继续遍历，可通过重置迭代器解决）
3、void remove()方法 ：删除当前指针所指向的元素，一般和next方法一起用，这时候的作用就是删除next方法返回的元素，如果当前指针指向的内存中没有元素，那么会抛出异常
三、Collection子接口：List接口
List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引
List接口底层以数组方式进行对象存储，允许存放null元素
（一）List接口常用方法
| 方法 | 描述 |
|---|---|
| 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 |
import java.util.ArrayList;
import java.util.List;
public class list {
public static void main(String[] args) {
List lst=new ArrayList();
lst.add("jack");
lst.add("Tom");
lst.add("Sick");
lst.add("jack");
System.out.println(lst);
System.out.println(lst.size());//获取集合元素的个数
System.out.println(lst.isEmpty());//判断集合是否为空
System.out.println(lst.contains("xxx"));//判断lst集合是包含指定元素
System.out.println(lst.get(0));//获取指定下标位置的元素
System.out.println(lst.indexOf("jack"));//获取指定元素在集合中第一次出现位置下标
System.out.println(lst.lastIndexOf("jack"));//获取指定元素在集合中最后一次出现的下标
System.out.println(lst.remove(1));//移除指定元素，并且返回该元素
System.out.println(lst.set(0, "yyy"));//将指定下标的元素替换，并返回原先指定下标的元素
}
}
（二）List接口常见三种遍历方式
package com.eveningliute.list_;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Arraylist {
public static void main(String[] args) {
List list = new ArrayList();
for(int i=0;i<10;i++){
list.add(i);
}
list.add(100);
//普通for循环进行遍历
System.out.println("-----第一种遍历方式------");
for(int i=0;i<list.size();i++){
System.out.println("list="+list.get(i));
}
//增强for进行遍历
System.out.println("-----第二种遍历方式------");
for (Object o :list) {
System.out.println("o="+o);
}
//Iterator迭代器进行遍历
System.out.println("-----第三种遍历方式------");
Iterator iterator=list.iterator();
while(iterator.hasNext()){
Object next=iterator.next();
System.out.println("next="+next);
}
}
}
（三）实现类之一：ArrayList接口
一） ArrayList():构造一个默认大小为10容量的空列表。
二） ArrayList(int initialCapacity):构造一个大小为指定int initialCapacity容量的空列表。
三） ArrayList(Collection c):构造一个和参数c相同元素的ArrayList对象
ArrayList的JDK 1.8之前与之后的实现区别？
JDK 1.7：直接创建一个初始容量为10的数组
JDK 1.8：一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
package com.eveningliute.list_;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Arraylist {
public static void main(String[] args) {
//无参构造
List list2=new ArrayList();
//构造一个大小为指定int initialCapacity容量的空列表。
List list1=new ArrayList(6);
// ArrayList(Collection c):构造一个和参数c相同元素的ArrayList对象
List list =new ArrayList();
List list0 = new ArrayList(list);
for(int i=0;i<10;i++){
list.add(i);
}
Iterator iterator=list.iterator();
while(iterator.hasNext()){
Object next=iterator.next();
System.out.println("next="+next);
}
2、ArrayList扩容机制（底层源码解析）
第一步：第一次添加元素的时候，底层会为Object[] elementData开辟一个默认大小为DEFAULT_CAPACITY(10)的容量。
-->DEFAULT_CAPACITY==10;
第二步：每次当数组容量到达最大值的时候，底层都会调用grow(minCapacity)方法进行扩容;
--》minCapacity为 elementData.length+1;
当数组容量超过初始容量的时候，接下来每次扩容都是前一次容量+前一次容量的二分一
（例如：10,15（10+10/2）,22（15+15/2）.....）
int newCapacity = oldCapacity + (oldCapacity >> 1); //此处是真正进行扩容的地方， 例如:第一次oldCapacity为10，执行oldCapacity >> 1相当于oldCapacity/2
此时newCapacity=15；
第三步：调用Arrays.copyOf()方法，也就是真正让数组容量发生改变的地方
elementData = Arrays.copyOf(elementData, newCapacity);
package com.eveningliute.list_;
import java.util.ArrayList;
import java.util.List;
public class ArraylistScore {
public static void main(String[] args) {
List list = new ArrayList();
list.add("jack");
for(int i=0;i<20;i++){
list.add(i);
}
}
/*
底层扩容机制源码解析：
第一步：第一次添加元素的时候，底层会为Object[] elementData开辟一个默认大小为DEFAULT_CAPACITY(10)的容量。
-->DEFAULT_CAPACITY==10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;//如果元素个数没有达到数组最大容量时，直接返回
}
第二步：当数组容量到达10的时候，进行第二次扩容，调用grow(minCapacity);
----->minCapacity为 elementData.length+1;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//如果数组元素的个数没有达到数组最大容量的时候,不调用此扩容方法
grow(minCapacity);
}
第三步：当数组容量超过初始容量的时候，接下来每次扩容都是前一容量+前一次容量的二分一
(例如：10,15（10+10/2）,22（15+15/2）.....)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//此处是真正进行扩容的地方，例如:第一次oldCapacity为10，执行oldCapacity >> 1相当于
oldCapacity/2,------>newCapacity=15；
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);
//此处将新开辟出的数组赋给原始数组完成数组扩容。
}
*/
}
（四）实现类之一：LinkedList接口
1、LinkedList二种构造方法：
一） LinkedList():构造一个空的LinkedList对象。
二） LinkedList(Collection c):构造一个和参数c相同元素的LinkedList对象
2、LinkedList新增方法：
| 方法 | 功能说明 |
|---|---|
| void addFirst(Object obj) | 在链表头部插入一个元素 |
| void addLast(Object obj) | 在链表尾部添加一个元素 |
| Object getFirst() | 获取第一个元素 |
| Object getlast)() | 获取最后一个元素 |
| Object removeFirst() | 删除头元素 |
| Object removeLast() | 删除尾元素 |
| Object peek() | 获取但不移除第一个元素 |
| Object poll() | 获取并移除第一个元素 |
3、LinkedList底层源码解析
一）LinkedList底层通过双向链表添加数据
源码解析：
第一次数据添加时，first和last都指向第一个结点，next和prev都等于null；
之后添加数据时前一个数据的next域(l.next)指向下一个结点，下一个几点的prev域(l.prev)指向前一个结点
（五）实现类之一：Vector接口
1、Vector四种构造方法：
一） Vector():构造一个构造一个元素个数为0的Vector对象，为其分配默认大小的容量。
二） Vector(int size):构造一个构造一个元素个数为0的Vector对象，为其分配默认大小为size的初始容量。
三） Vector(Collection c):构造一个和参数c相同元素的ArrayList对象
四） Vector(int initalcapacity,int capacityincrement):构造一个构造一个元素个数为0的Vector对象，为其分配大小为 initalcapacity的初始容量。并指定vector中的元素个数达到初始容量时，vector会自动增加大小为capacityincrement的容量
2、vector底层源码解析
vector底层源码绝大数和ArrayList相同，但扩容机制略有区别，每次扩容是前一次容量的二倍
如图所示箭头处为Vector与ArrayList的扩容机制区别 ：
四、Collection子接口：Set接口
（一）、Set接口概述
- Set接口是Collection的子接口，Set集合中的元素是无序，同时不可重复的
- 可以存放null元素
- Set接口的实现类有HashSet、treeSet、LinkedHashSet
（二）、Set接口常用方法
代码示例：
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();
set.add(null);
set.add("jack");
set.add("Tom");
set.add("milan");
set.add("smith");
System.out.println(set);
Set set1=new HashSet();
set1.addAll(set);
System.out.println(set);
set.remove(null);
System.out.println(set);
set.toArray();
System.out.println(set);
set.removeAll(set1);
System.out.println(set);
}
}
（三）、Set实现类之一：HashSet
- HashSet是为了优化查询速度而设计的Set，允许存放null值。元素不可重复且无序
- 对于存在HashSet集合中的元素需要重写equals()方法和HashCode()方法
- HashSet是线程不安全的
一）、HashSet常用的构造方法
负载因子：比如说当前的容器容量是16，负载因子是0.75,16*0.75=12，也就是说，当容量达到了12的时候就会进行扩容操作。简单来说相当于扩容机制的一个阈值，当超过这个阈值的时候就会触发扩容。
二）、HashSet底层源码解析
1、底层扩容机制源码解析
/*
//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;
2、添加数据底层源码解析
底层实现图解：链表+数组+红黑树
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;
}
}
（四）、Set实现类之一：LinkedHashSet
- LinkedHashSet中的元素没有重复
- LinkedHashSet中的元素有顺序，维护了添加顺序
- LInkedHashSet可以存储null值
- LinkedHashSet是一个线程不安全的容器
一）、LinkedHashSet常用的构造方法
二）、底层实现机制
1、概述：
LinkedHashSet底层是一个 LinkedHashMap，底层维护了一个数组+双向链表。
它根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序, 也就是LinkedHashSet的遍历顺序和插入顺序是一致的。
2、添加元素底层源码分析
1、在LInkedHashSet中维护了一个hash表和双向链表，LinkedHashSet中有head和tail,分别指向链表的头和尾
2、每一个节点有before和after属性，这样可以形成双向链表
3、在添加一个元素时，先求hash值，再求索引，确定该元素在table表中的位置，然后将添加的元素加入到双向链表（如果该元素已经存在，则不添加）
p.next= newElement
newElement.pre =p
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
package com.eveningliute.set_;
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetScore {
public static void main(String[] args) {
Set set = new LinkedHashSet();
for(int i=0;i<13;i++){
set.add(i);
}
//底层源码解析
/**
* 1、
* public boolean add(E e) {
* return map.put(e, PRESENT)==null;
* }
*第一步：LinkedHashSet的底层大多实现原理与HashSet相同，同时实现了LinkedHashMap
* 1、table[]数组的类型为HashMap$Node[],且数组里每一个结点的类型为LinkedHashMap$Entry
*因此当传进元素时，会先将元素创建为Node<K,V>，然后将Node<K,V>里的K-V封装到数据类型为Entry<k,v>的entrySet<Entry<k,v>>集合中去
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// LinkedHashMap 的静态内部类 Entry 继承自 HashMap 的静态内部类 Node
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//底层Node是没有任何直接遍历方法，因此会将Node<k,v>实现Entry<k,v>接口，
//通过Entry<k,v>里的getKey()和getValue()方法来获取元素
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
*/
}
}
3、底层扩容机制与上面HashSet扩容机制相同，这里就不在进行分析
（五）、Set实现类之一：TreeSet
- 集合中的元素没有重复
- 集合中的元素不保证插入顺序，而是默认使用元素的自然排序，不过可以自定义排序器
- jdk8以后，集合中的元素不可以是null(如果为空，则会抛出异常 java.lang.NullPointerException)
- 集合不是线程安全
- 相对于HashSet, 性能更差
1、TreeSet构造方法
2、TreeSet底层元素添加与扩容机制源码解析 - TreeSet底层使用的是红黑树实现，对于元素之间排序，如果不指定自定义的外部比较器 ——Comparator，那么插入的对象必须实现内部比较器——Comparable 接口，元素按照实现此接口的 compareTo() 方法去排序。
- TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
- 在不使用默认排序测情况下，可以重写compare()方法来实现自定义排序
compare()方法底层源码：
public final class Integer extends Number implements Comparable<Integer> {
//省略其他代码
//......
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
自定义排序：Comparator接口解析
import java.util.TreeSet;
public class TreeSetScore {
public static void main(String[] args) {
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String)o2);
}
/*
* 根据自己的理解就是o2是第一个传进去的参数，o1为第二个传进去的参数，
* ((String)o1).compareTo((String)o2)比较的是Ascall码值，如果o1<o2返回负数(-1)，所以第二次添加的元素比第一次添加的元素
* Ascall码值大，这时候由于返回的是负数，会先将两者的位置进行交换，因此遍历输出的结果为升序，如果o1>o2返回正数(1),这个时候说明
* 第二次添加的元素比第一次添加的元素 Ascall码值小，这里不会进行两者位置交换，遍历输出的时候大的值排在前面，因为遍历结果为降序
*/
});
/* for (int i = 0; i < 13; i++) {
treeSet.add(i);
}*/
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("sss");
treeSet.add("aaaaa");
System.out.println(treeSet);
如果传入元素为null，则会抛出空指针异常
//第一步：创建一个Entry<K,V>类型的root(根)结点，之后每次添加的子结点类型都为Entry<K,V>
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//第一步：创建一个Entry<K,V>类型的root(根)结点，之后每次添加的子结点类型都为Entry<K,V>
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//第二步：每次添加元素的时候，都会调用compare()方法判断当前添加的元素与集合中已有元素是否为同一元素 如果不是则直接添加，同时根据compare()方法返回值来判断添加的位置
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//第三步:当我们将一个对象加入treeset中，treeset会将第一个对象作为根对象，然后调用对象的compareTo方法拿第二个对象和第一个比较，当返回值等于0时，说明2个对象内容相等，treeset就不把第二个对象加入集合。返回>1时，说明第二个对象大于第一个对象，将第二个对象放在右边，返回-1时，则将第二个对象放在左边，依次类推
// 第四步：传入元素与双亲结点进行比较，如果大于双亲结点添加到右子树，如果小于双亲结点，则添加到左子树，否则直接返回值
//第三步：传进来的子节点先与根结点进行判断，如果大于根结点，则让结点与根结点的子结点进行比较，如果传入元素小于任意子结点的左右结点其中一个结点，则让该结点作为该元素的双亲结点
//第四步：传入元素与双亲结点进行比较，如果大于双亲结点添加到右子树，如果小于双亲结点，则添加到左子树，否则直接返回值
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//这里是将传进来的值封装成Entry<K,V>类型，然后根据判断放进双亲结点的子节点中
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
（六）、总结-开发中如何选择集合实现类
在开发中，遊择什么集合实现美，主要取决于业务操作特点，然后根据集合安现类特性进行
选择，分析如下：
1）先判断存储的类型（一组对象或一组键值对）
2) 一组对象：Collection接口
允许重复：List
增删多：LinkedList [底层维护了一个双向链表]
改查多：Arraylist[底层维护 Object类型的可变数组]
不允许重复: Set
无序：Hashset[席层是HashMap，维护了一个哈希表 即（数组＋链表＋红黑树）】
排序：TreeSet
插入和取出顺序一致：LinkedHashSet，维护数组＋双向链表
3) 一组键值对：Map接口
键无序：HashMap[底层是：哈希表 jdk7：数组＋链表，jdk8：数组＋链表＋红黑树]
键排序：TreeMap
鍵插入和取出順序一致： LinkedHashMap
读取文件 Properties
五、Map接口
(一)、概述
- Map 接口没有从 Collection 接口继承。
- Map接口用于维护“键值”对(Key-Value Pairs)数，这个“键一值”对就是Map 中的元素。
- Map提供“键(Key)”到“值(Value)”的映射。
- 一个 Map中键值必须是唯一的,不能有重复的键,因为Map中的“键-值”对元素是通过键来唯一标识的。
- Map 的键是用 Set 集合来存储的,所以充当键元素的类必须重写hashCodeO和equals方法。通过键元素来检索对应的值元素
(二)、Map常用方法
(三)、Map实现类之一：HashMap
HashMap底层实现机制和HashSet一样，这里就不在进行描述，详细可见上述HashSet底层源码分析下面是对HashSet没有提到的点的一个补充 ：
package com.eveningliute.set_;
import java.util.*;
public class hashmap {
public static void main(String[] args) {
Map map = new HashMap();
//第一步：创建一个数据类型为Entry table[]的数组，初值为null
map.put("jack",18);
map.put("milan",20);
map.put("jack",100);
//第二步：将map里的K-V封装到数据类型为Entry<k,v>的entrySet<Entry<k,v>>集合中去
Set set = map.entrySet();
//第三步：通过Entry接口提供的getKey(),getValue()方法来遍历对象的键或值
for (Object o :set) {
Map.Entry entry=(Map.Entry)o;
System.out.println(entry.getKey()+"-"+entry.getValue());
}
//将map里的k值封装到keySet集合中去,
// final class KeySet extends AbstractSet<K>继承Set接口
Set set1 = map.keySet();
for (Object o :set1) {
System.out.println(o);
}
Iterator iterator = set1.iterator();
while(iterator.hasNext()){
Object next = iterator.next();
System.out.println(next);
}
// final class Values extends AbstractCollection<V> 继承Collection接口
Collection values = map.values();
for (Object o :values) {
System.out.println(o);//增强for输出
}
iterator=values.iterator();//迭代器输出
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
}
}