集合-高级_Java

1.集合

1.集合架构
集合的概念

本质上是一种可以存放任意类型对象的容器（可以结合泛型存储指定的类型）
说明：
1.Java集合的长度根据元素的大小可变化
2.Java集合只能存放引用类型数据，不能存放基本数据类型

3.Java可以通过包装类将基本数据类型转换为对象类型存放在集合中(自动封箱机制)
4.Java集合中实际存放的只是对象的引用，每个集合元素都是一个引用变量，实际内容都存放在堆内存或者方法区中

集合的架构

1.架构图：

2.架构说明：
集合按照其存储结构分为两大类，即：单列集合Collection，双列集合Map

2.Collection接口
1.Collection是单列集合类的根接口
2.其继承自Iterable接口(为对象使用迭代器Iterator提供统一调用)
3.Collection包含多个子接口，其中比较重要的有：（List,Set,Queue,AbstractCollection）

1.Iterable接口
public interface Iterable {
	//作用是为集合类提供for-each循环的支持
	//Implementing this interface allows an object to be the target of the "for-each loop" statement.
	Iterator iterator();	//返回一个内部元素为T类型的顺序迭代器
	// 对Iterable中的元素进行指定的操作
	default void forEach(Consumer action) {
    	Objects.requireNonNull(action);
    	for (T t : this) {
        	action.accept(t);
    	}
	}
	// 返回一个内部元素为T类型的并行迭代器
	default Spliterator spliterator() {
     	return Spliterators.spliteratorUnknownSize(iterator(), 0);
	}
}
1.Iterable接口的核心方法是iterator(),该方法的作用是返回一个Iterator对象，为Java对象提供forEach支持
2.Iterable接口提供forEach方法用来迭代元素，执行消费器的accept方法
3.Iterable接口提供获取Spliterator可分割迭代器方法，用以支持集合的并发遍历

2.Iterator接口

public interface Iterator {
	// 判断一个对象集合是否还有下一个元素
	boolean hasNext();
	// 获取下一个元素
	E next();
	// 删除最后一个元素。默认是不支持的，因为在很多情况下其结果不可预测
	default void remove() {
     	throw new UnsupportedOperationException("remove");
 	}
 	// 主要将每个元素作为参数发给action来执行特定操作
 	default void forEachRemaining(Consumer action) {
     	Objects.requireNonNull(action);
        while (hasNext())
        	 action.accept(next());
	 }
}

1.注意和Iterable接口的区分
2.Iterator提供了集合和流操作等的遍历方式，是迭代器模式的应用
3.迭代器接口的函数比较简单，具体的实现交给子类实现

1.List接口
1.List接口是Collection的子接口
2.List的存储特点
1.元素可以重复
2.元素可以为null
3.元素有序(存入和取出的顺序一致)
4.有下标(线性存储可以通过索引访问集合中的元素)

1.ArrayList
1.ArrayList继承了AbstractList抽象类实现了List接口，是一个长度可变的集合
2.集合中提供了增删改查的功能，集合允许null的存在
3.ArrayList类实现了RandomAccess接口，说明ArrayList可以对元素进行快速访问
4.ArrayList类实现了Serializable接口，说明ArrayList可以被序列化
5.ArrayList类实现了Cloneable接口，说明ArrayList可以被复制
6.ArrayList类在JDK1.2版本发布，线程不安全，但是效率高(线程安全和效率冲突)
public class ArrayList extends AbstractList
     implements List, RandomAccess, Cloneable, java.io.Serializable{
		private static final long serialVersionUID = 8683452581122892189L;
		//默认的容量大小（常量）
		private static final int DEFAULT_CAPACITY = 10;
		//定义的空数组（final修饰，大小固定为0）
		private static final Object[] EMPTY_ELEMENTDATA = {};
		//定义的默认空容量的数组（final修饰，大小固定为0）
		private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
		//定义的不可被序列化的数组，实际存储元素的数组
		transient Object[] elementData;
		// 数组中元素的个数
		private int size;
		//构造：根据传入的数值大小，创建指定长度的数组
		public ArrayList(int initialCapacity) {
	        if (initialCapacity > 0) {
			   //当initialCapacity > 0时，然后将其引用赋给elementData，此时ArrayList的容量为initialCapacity，元素个数size为默认值0
  		       this.elementData = new Object[initialCapacity];
   		  	} else if (initialCapacity == 0) {
   			//当initialCapacity = 0时，elementData被赋予了空数组，因为其被final修饰了，所以此时ArrayList的容量为0，元素个数size为默认值0
        	   this.elementData = EMPTY_ELEMENTDATA;
     		} else {
         		throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     		}
 		}
 		//无参的构造方法
 		public ArrayList() {
 			//直接创建ArrayList时，elementData被赋予了默认空容量的数组
    		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	   }
		//传入Collection元素列表的构造方法
	    public ArrayList(Collection c) {
			//将列表转化为对应的数组
     		elementData = c.toArray();
     		if ((size = elementData.length) != 0) {       
		         if (elementData.getClass() != Object[].class)
         		    elementData = Arrays.copyOf(elementData, size, Object[].class);
     		} else {
      		   this.elementData = EMPTY_ELEMENTDATA;
    		 }
	   }
 		public void trimToSize() {
   		  modCount++;
  		   if (size < elementData.length) {
  		       elementData = (size == 0)
 		          ? EMPTY_ELEMENTDATA
 		          : Arrays.copyOf(elementData, size);
 		    }
	  }
	  public void ensureCapacity(int minCapacity) {
  		   int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  		       ? 0
   		      : DEFAULT_CAPACITY;
   		  if (minCapacity > minExpand) {
    		     ensureExplicitCapacity(minCapacity);
    		 }
		 }
	 private void ensureCapacityInternal(int minCapacity) {
   		  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   		      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     	  }

    		 ensureExplicitCapacity(minCapacity);
	 }

 private void ensureExplicitCapacity(int minCapacity) {
     modCount++;

     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 private void grow(int minCapacity) {
     // overflow-conscious code
     int oldCapacity = elementData.length;
     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);
 }

 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 static void main(String[] args) {
     // 1.创建Student对象数组
     Student[] students = new Student[] {
             new Student("小明", 18),
             new Student("小李", 19),
             new Student("小张", 21)
     };

     // 2.将其赋值给Object对象数组
     Object[] objects = students;

     // 3.执行if语句前，打印数组的class
     System.out.println("执行前：" + objects.getClass());

     // 4.执行上面的代码
     if (objects.getClass() != Object[].class) {
         objects = Arrays.copyOf(objects, objects.length, Object[].class);
     }

     // 5.执行if语句后，打印数组的class
     System.out.println("执行后：" + objects.getClass());
 }
源码分析：
1.serialVersionUID：应用于JAVA序列化机制，Java序列化通过判断类的serialVersionUID来验证版本是否一致。在进行反序列化时，JVM会把传来的字节流中的serialVersionUID于本地相应实体类的serialVersionUID进行比较。如果相同说明是一致的，可以进行反序列化，否则会出现反序列化版本一致的异常，即是InvalidCastException。所以赋予它一个固定的serialVersionUID，反序列化后即使改变也不会改变serialVersionUID，即被认为是同一个class文件，不会出现版本不一致的情况
2.ArrayList容器底层是由数组实现，且这个数组的类型是Object类型，由transient修饰阻止它被序列化，DEFAULT_CAPACITY(默认容量)为10
3.对应不同的构造函数，ArrayList使用不同的数组，且使用int类型的size表示数组中元素的个数，其中EMPTY_ELEMENTDATA为含参构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA为无参构造函数。使用含参构造函数elementData中没有元素，size为0，但是elementData可能不相同，因为有初始化容量
5.对象数组也是有.class的，其中含有所存储元素的类型，上面的第二段代码的作用就是将原对象数组的数组类型转化为Object对象数组的数组类型，以便更好的存储
6.ArrayList提供了使用集合参数的构造函数，函数首先调用toArray方法将集合转换为数组，将其索引赋给elementData。然后检查数组中是否有元素，如果有元素判断转换的类型，如果不是Object[]类型，使用Arrays类中的copyOf方法进行复制，将其转换为Object类型，且元素个数为size，表明当前集合是满的。如果没有元素则使用EMPTY_ELEMENTDATA进行初始化
7.trimToSize()：由于表示集合中元素个数的size和表示集合容量的elementData.length可能不同，在不太需要增加集合元素的情况下容量有浪费，可以使用trimToSize方法减小elementData的大小，其中modCount是继承自AbstractList中的字段，用来记录数组修改的次数，数组每修改一次，modCount加一，然后判断集合中元素个数是否小于集合的容量，如果小于再判断元素个数是否为0，如果为0就使用EMPTY_ELEMENTDATA对elementData进行初始化，否则使用Arrays工具类中的copyof方法进行数组复制
8.ensureCapacity()：用于保证数组能够包含给定参数的个数，即如果有需要就扩大数组的容量，首先检查elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,如果是则说明长度为10，如果不是将minExpand设置为0，然后比较minCapacity和minExpand的大小，如果所需最小容量大于最小扩展，则需要调用私有方法进行数组扩容
9.ensureCapacityInternal()：首先minCapacity和默认大小(10)比较，如果需要扩大容量，则继续调用私有方法进行数组扩容
10.ensureExplicitCapacity()：比较所需最小容量和集合当前长度进行比较，如果需要扩容则调用grow方法进行扩容
11.grow()：具体的扩容方法，首先将容量增加为原来的1.5倍(位移运算符，左移一位代表乘以2，右移一位代表除以2)。如果还不够则用给定的容量minCapacity，同时ArrayList设置了数组的最大长度private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;如果新容量没有超过则使用Arrays进行复制，不够的元素使用null，如果超出最大长度，调用函数hugeCapacity(minCapacity)检查是否溢出
12.hugeCapacity()：首先判断最小容量是否小于0，如果小于0则OutOfMemoryError()报内存不足错误，如果没有溢出就得到合适的minCapacity值，然后复制

2.LinkedList
1.LinkedList继承了AbstractSequentialList抽象类实现了List接口，是一个长度可变的集合
2.集合中提供了增删改查的功能，集合允许null的存在
3.LinkedList实现了实现了Deque(双端队列)接口，说明LinkedList支持队列操作
4.LinkedList类实现了Serializable接口，说明LinkedList可以被序列化
5.LinkedList类实现了Cloneable接口，说明LinkedList可以被复制(克隆)
6.ArrayList类在JDK1.2版本发布，线程不安全，但是效率高(线程安全和效率冲突)
public class LinkedList
	 extends AbstractSequentialList
	 implements List, Deque, Cloneable, java.io.Serializable
{
	 transient int size = 0;
  	 transient Node first;
	 transient Node last;
 
 	public LinkedList() {
  	}

	 public LinkedList(Collection c) {
     	 this();
      	 addAll(c);
 	 }
	...
	private static class Node {
 	    E item;
  	    Node next;
 	    Node prev;

 	    Node(Node prev, E element, Node next) {
 	        this.item = element;
          this.next = next;
          this.prev = prev;
    	}
	}
}
源码分析：
1.LinkedList提供了三个无法被序列化的成员变量(size,first,last),其中size为链表的元素个数，first为链表的头节点，last为链表的尾节点，Node为节点对象，可用泛型修饰
2.Node是LinkedList的静态内部类，用来定义存储的数据结构，其中包含next和prev，代表前一个节点和后一个节点，属于典型的双向链表
3.LinkedList容器底层是由双向链表实现，插入删除效率高，查找效率低；不存在容量不足的问题，所以没有扩容的方法
4.LinkedList提供两个构造方法，LinkedList()和LinkedList(Collection c)，其中LinkedList()仅仅构造一个空的LinkedList集合，没有任何元素，size为0，first和last都为null；LinkedList(Collection c)构造一个包含指定Collection中所有元素的集合，该构造方法首先会调用空的构造方法，然后通过 addAll() 的方式把 Collection 中的所有元素添加进去

3.Vector
1.Vector继承了AbstractList抽象类实现了List接口，是一个长度可变的集合
2.Vector集合中提供了增删改查的功能，集合允许null的存在
3.Vector类实现了RandomAccess接口，说明Vector可以对元素进行快速访问
4.Vector类实现了Serializable接口，说明Vector可以被序列化
5.Vector类实现了Cloneable接口，说明Vector可以被复制(克隆)
6.Vector类在JDK1.0版本发布，线程安全，但是效率低(线程安全和效率冲突)
public class Vector
   extends AbstractList
   implements List, RandomAccess, Cloneable, java.io.Serializable
{
   protected Object[] elementData;
   protected int elementCount;
   protected int capacityIncrement;
   private static final long serialVersionUID = -2767605614048989439L;
   public Vector(int initialCapacity, int capacityIncrement) {
       super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       this.elementData = new Object[initialCapacity];
       this.capacityIncrement = capacityIncrement;
   }

   public Vector(int initialCapacity) {
       this(initialCapacity, 0);
   }
   public Vector() {
       this(10);
   }
   public Vector(Collection c) {
       elementData = c.toArray();
       elementCount = elementData.length;
       // c.toArray might (incorrectly) not return Object[] (see 6260652)
       if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
   }
   public synchronized void copyInto(Object[] anArray) {
       System.arraycopy(elementData, 0, anArray, 0, elementCount);
   }
   public synchronized void trimToSize() {
       modCount++;
       int oldCapacity = elementData.length;
       if (elementCount < oldCapacity) {
           elementData = Arrays.copyOf(elementData, elementCount);
       }
   }
   public synchronized void ensureCapacity(int minCapacity) {
       if (minCapacity > 0) {
           modCount++;
           ensureCapacityHelper(minCapacity);
       }
   }
   private void ensureCapacityHelper(int minCapacity) {
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       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);
   }

   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }
源码解析：
1.Vector底层也是由数组实现，这个数组也是Object类型，但是可以被序列化，Vector用elementCount表示实际存储的元素个数，新增capacityIncrement属性表示需要增加的容量
2.Vector提供了四种不同的构造函数，分别为无参构造，一个参数的构造函数，两个参数的构造函数和以集合为参数的构造函数，其中initialCapacity表示初始化容量，capacityIncrement表示每次扩充的容量。如果调用无参构造会调用初始化容量为10的一个参数的构造函数，然后再调用初始化容量为10，扩充容量为0的两个参数的构造函数，再判断初始容量是否小于0，如果小于0则抛出非法容量异常，否则新建一个Object数组，并初始化扩容变量，总结来说主要是调用两个参数的构造函数
3.ensureCapacity(int minCapacity)：确保容量，如果所需最小容量大于0，则修改次数加一，并且调用ensureCapacityHelper(minCapacity)方法，在ensureCapacityHelper方法中，如果所需最小容量大于当前集合的长度则调用grow()扩容方法
4.grow(minCapacity)：，如果扩容的容量大于0，则扩容后大小为原容量+所需扩容的容量；否则扩容后大小为原容量的两倍，如果新的容量还是小于所需最小容量，则把新的容量设置为所需最小容量，如果新的容量大于设置的最大数组容量则检查是否超过容量，即是否内存溢出

2.Set接口
1.Set接口是Collection的子接口，表示唯一对象的集合
2.Set的存储特点
1.元素不可以重复(因为内部基于Map的实现类)
2.元素可以存null
3.元素无序(存入和取出的顺序不一致)
4.无下标(不可以指定位置访问)

1.HashSet
1.HashSet继承了AbstractSet抽象类实现了Set接口，是一个长度可变的集合
2.集合中提供了增删改查的功能，集合允许null的存在
3.HashSet类实现了Serializable接口，说明HashSet可以被序列化
4.HashSet类实现了Cloneable接口，说明HashSet可以被复制
5.HashSet类在JDK1.2版本发布，线程不安全
public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
	//使用 HashMap 的 key 保存 HashSet 中所有元素 
    private transient HashMap map;
	//定义一个虚拟的 Object 对象作为 HashMap 的 value 
    private static final Object PRESENT = new Object();
	//构造方法，初始化 HashSet，底层会初始化一个 HashMap   
    public HashSet() {
        map = new HashMap<>();
    }
	
    public HashSet(Collection c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
	//以指定的 initialCapacity、loadFactor 创建 HashSet, 其实就是以相应的参数创建 HashMap
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
	//以指定的 initialCapacity创建 HashSet, 其实就是以相应的参数创建 HashMap
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

}
源码分析：
1.HashSet 的内部采用了HashMap作为数据存储，HashSet其实就是在操作HashMap的key。默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap
2.封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象
3.当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，需要重写该类的equals(Object obj)方法和 hashCode() 方法
4.HashSet底层使用了哈希表来支持的，往HashSet添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。如果算出的元素存储的位置目前没有任何元素存储，那么该元素可以直接存储在该位置上。如果算出的元素的存储位置目前已经存在有其他的元素了，那么还会调用该元素的equals方法与该位置的元素再比较一次，如果equals方法返回的是true，那么该位置上的元素视为重复元素，不允许添加，如果返回的是false，则允许添加
5.重写hashcode原因：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node 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);
        else {
            Node 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)p).putTreeVal(this, tab, hash, key, value);
            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;
                    }
					//比较对象的hashcode
                    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;
    }
通过HashMap中的源码可以看到HashSet在进行添加底层使用到了hash方法，而hash值的获取实际上是在hashCode基础上的一系列操作，如果不重写hashcode，用的则是从Object继承下来的hashCode，而这个hashCode每次new一个对象就会有不同的值；所以就造成了上面的对象中的内容即使一样但还是被认为是不同的元素，因为每次存入时都是new了一个新对象，就造成了hash值一直不同
6.重写equals原因：
因为hash值毕竟只是一个逻辑值，不同的对象有几率出现相同的hash值（称为哈希碰撞）。如果不同的对象出现了相同的hash值就需要使用equals进行再次判断，才能确保两个对象是否相同

2.LinkedHashSet
1.LinkedHashSet继承了HashSet类实现了Set接口，是一个长度可变的集合
2.集合中提供了增删改查的功能，集合允许null的存在
3.LinkedHashSet类实现了Serializable接口，说明HashSet可以被序列化
4.LinkedHashSet类实现了Cloneable接口，说明HashSet可以被复制
5.LinkedHashSet类在JDK1.4版本发布，线程不安全
public class LinkedHashSet
    extends HashSet
    implements Set, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

    @Override
    public Spliterator spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}
源码分析：
1.LinkedHashSet的内部采用了LinkedHashMap作为数据存储
2.LinkedHashSet具体内容同HashSet类似，只是HashSet是使用HashMap作为存储数据的容器，LinkedHashSet是使用LinkedHashMap作为存储数据的容器

3.TreeSet
1.TreeSet继承了AbstractSet抽象类实现了NavigableSet接口，是一个长度可变的集合
2.集合中提供了增删改查的功能，集合不允许null的存在
3.TreeSet类实现了Serializable接口，说明TreeSet可以被序列化
4.TreeSet类实现了Cloneable接口，说明HashSet可以被复制
5.TreeSet类在JDK1.2版本发布，线程不安全
public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable
{
    private transient NavigableMap m;

    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap());
    }

    public TreeSet(Comparator comparator) {
        this(new TreeMap<>(comparator));
    }

    public TreeSet(Collection c) {
        this();
        addAll(c);
    }

    public TreeSet(SortedSet s) {
        this(s.comparator());
        addAll(s);
    }
}
源码分析：
1.TreeSet的内部采用了TreeMap作为数据存储，TreeSet其实就是在操作TreeMap的key
2.TreeSet封装了一个 TreeMap对象来存储所有的集合元素，所有放入 TreeSet中的集合元素实际上由 TreeMap的 key 来保存，而 TreeMap的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象

3.Map接口
1.Map接口是双列集合的根接口，其中定义了一个内部接口Entry ，用于存储数据
2.Map 接口中键和值一一映射，可以通过键来获取值（给定一个键和一个值，你可以将该值存储在一个 Map 对象，之后可以通过键来访问对应的值）
3.Map的存储特点是
1.键(Key)无序，无下标，不可重复
2.值(Value)无序，无下标，可以重复
3.每个键至多对应一个值，如果重复上面的值会被下面的值覆盖
4.键可以为null，值也可以为null

1.HashMap
1.HashMap继承了AbstractMap抽象类实现了Map接口
2.HashMap类实现了Cloneable接口，说明HashMap可以被复制(克隆)
3.HashMap类实现了Serializable接口，说明HashMap可以被序列化
4.HashMap类在JDK1.2版本发布，线程不安全，但是效率高(线程安全和效率冲突)
public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
	//默认初始容量 - 必须是 2 的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	//最大容量，2的30次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;
	//构造函数中未指定时使用的负载因子。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	//链表长度大于等于8时，转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
 	//如果节点小于6时，转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;
 
    static final int MIN_TREEIFY_CAPACITY = 64;

    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node 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; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    static Class comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    transient Node[] table;

    transient Set> entrySet;

    transient int size;
    
    transient int modCount;
 
    int threshold;

    final float loadFactor;

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
   	...
   	final Node[] resize() {
        Node[] 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;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
1.HashMap在JDK1.7用Table数组+Entry链表实现，JDK1.8用Table数组+Entry链表/红黑树实现。链表新节点插入链表的顺序不同（jdk7是插入头结点，jdk8因为要把链表变为红黑树所以采用插入尾节点）
2.HashMap中数组的默认初始容量DEFAULT_INITIAL_CAPACITY为16(数组容量必须为2的次幂)，数组最大容量MAXIMUM_CAPACITY为2的30次幂
3.HashMap的默认负载因子DEFAULT_LOAD_FACTOR为3/4(0.75f)，当元素的总个数>当前数组长度*负载因子，数组就会进行扩容，扩容大小为原来的两倍（例：使用无参构造方法创建的HashMap 对象，他初始长度默认是16 。阈值 = 当前长度 * 0.75 就能算出阈值，当当前长度大于等于阈值的时候HashMap就会进行自动扩容）
4.HashMap的默认链表树(红黑树)化的阙值TREEIFY_THRESHOLD为8,表示当在一个Node节点下的值的个数大于等于8时，会将链表转换为红黑树，提高查询效率
5.HashMap的默认红黑树链化阙值UNTREEIFY_THRESHOLD为6，表示在进行扩容期间，单个Node节点下的红黑树节点的个数小于6时，会将红黑树转换为链表
6.HashMap的最小树化阙值MIN_TREEIFY_CAPACITY，当数组的所有元素超过该值，才会进行树化（为了防止前期阶段频繁扩容和树化过程冲突）
7.HashMap采用Entry数组来存储key-value值，每一个键值对组成了一个Entry实体,Entry实际上是一个单向的链表结构，它具有Next指针，可以指向下一个Entry实体，当链表长度大于8时，链表会转换为红黑树
8.静态内部类Node实现Entry,其中可以有常量hash,key,和变量value，还有指向下一个Node节点的指针next，重写的hashCode返回值的hashCode和键的hashCode的异或值，重写的equals,首先判断自反性，再判断是否兼容，再强转后判断key和value是否相等
9.table数组，存放的类型为Node，其中Node继承自Entry接口，int类型的size代表大小
10.modCount代表修改的次数，threshold代表临界值，阙值，loadFactor负载因子
11.三种构造函数，无参，一个参数，两个参数，其中无参默认设置负载因子为默认负载因子为0.75f;一个参数的设置为初始容量，且负载因子为默认的，两个参数的一个为初始化容量，一个为负载因子，先判断初始化容量，如果小于0则抛出异常java.lang.IllegalArgumentException，然后初始化容量是否大于最大容量（2的30次方）,如果大于则让其等于最大容量，最后再判断负载因子是否大于0且是数字，如果不满足则抛出异IllegalArgumentException，如果以上都满足则对负载因子，和阙值进行初始化
12.第四个构造函数，参数为多态，即实现Map接口的实现类，将负载因子设置为默认值0.75f，然后调用putMapEntries（）方法把所有的参数加入到集合中
13.我们对key值进行hashcode以后，进行相与时候都是只用到了后四位，前面的很多位都没有能够得到使用,这样也可能会导致我们所生成的下标值不能够完全散列。
解决方案：将生成的hashcode值的高16位于低16位进行异或运算，这样得到的值再进行相与，一得到最散列的下标值。
14.HashMap 的扩容实现机制是将老table数组中所有的Entry取出来，重新对其Hashcode做Hash散列到新的Table中，可以看到注解Initializes or doubles table size. resize表示的是对数组进行初始化或进行Double处理。首先将老的table，旧的容量，旧的阙值起别名，如果旧的容量大于最大容量则将阙值设置为Integer的最大值，并返回旧数组；否则如果新的容量（旧容量的一两倍）还小于最大容量而且旧的容量大于默认的初始容量16，则将新的容量扩充为原来的两倍，否则如果旧阙值大于0，把新容量设置为旧阙值，否则将新容量设置为默认初始容量16，新的阙值设置为默认负载因子*默认初始容量
15.在多线程的使用场景中，尽量使用线程安全的ConcurrentHashMap
16.计算扩容后容量要采用位移运算呢，不直接乘以2的原因：因为cpu毕竟它不支持乘法运算，所有的乘法运算它最终都是再指令层面转化为了加法实现的，这样效率很低，如果用位运算的话对cpu来说就非常的简洁高效

2.LinkedHashMap
1.LinkedHashMap继承了HashMap类并且实现了Map接口
2.LinkedHashMap类再JDK1.4版本发布，线程不安全，效率高(线程安全和效率冲突)
public class LinkedHashMap
    extends HashMap
    implements Map
{
    static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

    private static final long serialVersionUID = 3801124242820219131L;

    transient LinkedHashMap.Entry head;

    transient LinkedHashMap.Entry tail;

    final boolean accessOrder;
 
    private void linkNodeLast(LinkedHashMap.Entry p) {
        LinkedHashMap.Entry last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
 
    private void transferLinks(LinkedHashMap.Entry src,
                               LinkedHashMap.Entry dst) {
        LinkedHashMap.Entry b = dst.before = src.before;
        LinkedHashMap.Entry a = dst.after = src.after;
        if (b == null)
            head = dst;
        else
            b.after = dst;
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

    void reinitialize() {
        super.reinitialize();
        head = tail = null;
    }

    Node newNode(int hash, K key, V value, Node e) {
        LinkedHashMap.Entry p =
            new LinkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    Node replacementNode(Node p, Node next) {
        LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;
        LinkedHashMap.Entry t =
            new LinkedHashMap.Entry(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    TreeNode newTreeNode(int hash, K key, V value, Node next) {
        TreeNode p = new TreeNode(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    TreeNode replacementTreeNode(Node p, Node next) {
        LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;
        TreeNode t = new TreeNode(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    void afterNodeRemoval(Node e) { // unlink
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMap.Entry e = head; e != null; e = e.after) {
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
1.LinkedHashMap可以有序的存储key-value,且默认为插入顺序
2.LinkedHaspMap提供了多个构造函数，无参构造函数，首先调用父类的无参构造方法，即根据默认初始容量和默认负载因子初始化构造Entry table,然后把accessOrder(访问顺序)设置为false,LinkedHashMap存储数据是有序的，且分为两种，一种是插入顺序，一种是访问顺序，这里accessOrder设置为false表示不是访问顺序而是插入顺序(默认)，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的，而访问顺序表示通过get方法访问的元素会被插入到表尾
3.LinkedHashMap类中有自己的静态内部类，且有before和after属性，表示该表采用的数据结构采用的是双向链表，而HashMap采用的只有一个next的单向链表。put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)
4.HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置。LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置。从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。
5.LinkedHashMap中，是通过双向链表的结构来维护节点的顺序的。head指向第一个插入的节点，tail指向最后一个节点。
6.与HashMap相比，LinkedHashMap增加了两个属性用于保证迭代顺序，分别是双向链表头结点header 和标志位accessOrder (值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)。
7.当链表长度超过阈值8时，并且数组总容量超过64时，将链表转换为红黑树。而当发生扩容或remove键值对导致原有的红黑树内节点数量小于6时，则又将红黑树转换成链表。

3.TreeMap

1.TreeMap继承了AbstractMap抽象类实现了NavigableMap接口，意味着拥有了更强的元素搜索能力
2.TreeMap类实现了Cloneable接口，说明TreeMap可以被复制(克隆)
3.TreeMap类实现了Serializable接口，说明TreeMap可以被序列化
4.TreeMap类在JDK1.2版本发布，线程不安全，但是效率高(线程安全和效率冲突)

5.TreeMap基于红黑树实现，根据键进行排序（默认比较器为升序），且可以根据自定义的比较器进行排序

public class TreeMap
     extends AbstractMap
     implements NavigableMap, Cloneable, java.io.Serializable {
 	//自定义的比较器：
	 private final Comparator comparator;

    //红黑树的根节点：
    private transient Entry root;

    //集合元素数量：
    private transient int size = 0;

    //对TreeMap操作的数量：
    private transient int modCount = 0;

    //无参构造方法：comparator属性置为null
 	//代表使用key的自然顺序来维持TreeMap的顺序，这里要求key必须实现Comparable接口
    public TreeMap() {
        comparator = null;
    }

    //带有比较器的构造方法：初始化comparator属性；
    public TreeMap(Comparator comparator) {
        this.comparator = comparator;
    }

    //带有map的构造方法：
    //同样比较器comparator为空，使用key的自然顺序排序
    public TreeMap(Map m) {
        comparator = null;
        putAll(m);
    }

    //带有SortedMap的构造方法:
    //根据SortedMap的比较器来来维持TreeMap的顺序
    public TreeMap(SortedMap m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}

//插入key-value:
public V put(K key, V value) {
    //根节点赋值给t:
   Entry t = root;
    //如果根节点为null，则创建第一个节点，根节点
    if (t == null) {
        //对传入的元素进行比较，若TreeMap没定义了Comparator，则验证传入的元素是否实现了Comparable接口；
        compare(key, key);
        //根节点赋值：
        root = new Entry<>(key, value, null);
        //长度为1：
        size = 1;
        //修改次数+1
        modCount++;
        //直接返回：此时根节点默认为黑色
        return null;
    }

    //如果根节点不为null:
    int cmp;
    Entry parent;
    Comparator cpr = comparator;

    //判断TreeMap中自定义比较器comparator是否为null：
    if (cpr != null) {
        // do while循环，查找新插入节点的父节点：
        do {
            // 记录上次循环的节点t，首先将根节点赋值给parent:
            parent = t;
            //利用自定义比较器的比较方法：传入的key跟当前遍历节点比较：
            cmp = cpr.compare(key, t.key);
            //判断结果小于0，处于父节点的左边 
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
            //判断结果大于0，处于父节点的右边 
                t = t.right;
            else
            //判断结果等于0，为当前节点，覆盖原有节点处的value：
                return t.setValue(value);
        // 只有当t为null，也就是找到了新节点的parent了
        } while (t != null);
    } else {
        //没有自定义比较器：
        if (key == null)
            //TreeMap不允许插入key为null，抛异常：
            throw new NullPointerException();
        //将key转换为Comparable对象：若key没有实现Comparable接口，此处会报错
        Comparable k = (Comparable) 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 e = new Entry<>(key, value, parent);

    //根据之前的比较结果，判断新增节点是在父节点的左边还是右边
    if (cmp < 0)
        // 如果新节点key的值小于父节点key的值，则插在父节点的左侧
        parent.left = e;
    else
        // 如果新节点key的值大于父节点key的值，则插在父节点的右侧
        parent.right = e;
    //核心方法：插入新的节点后，为了保持红黑树平衡，对红黑树进行调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
...
//对插入的元素比较：若TreeMap没有自定义比较器，则调用调用默认自然顺序比较，要求元素必须实现Comparable接口；
//若自定义比较器，则用自定义比较器对元素进行比较；
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
}

//核心方法：维护TreeMap平衡的处理逻辑；
private void fixAfterInsertion(Entry x) {
    //首先将新插入节点的颜色设置为红色
    x.color = RED;
    //TreeMap是否平衡的重要判断，当不在满足循环条件时，代表树已经平衡；
    //x不为null，不是根节点，父节点是红色（三者均满足才进行维护）：
    while (x != null && x != root && x.parent.color == RED) {
        //节点x的父节点 是 x祖父节点的左孩子：
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //获取x节点的叔叔节点y:
            Entry y = rightOf(parentOf(parentOf(x)));
         
            //叔叔节点y是红色：
            if (colorOf(y) == RED) {
                //将x的父节点设置黑色：
                setColor(parentOf(x), BLACK);  
                //将x的叔叔节点y设置成黑色：
                setColor(y, BLACK);
                //将x的祖父节点设置成红色：
                setColor(parentOf(parentOf(x)), RED);
                //将x节点的祖父节点设置成x(进入了下一次判断)：
                x = parentOf(parentOf(x));
            } else {
                 //叔叔节点y不为红色：
                //x为其父节点的右孩子：
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
					//左旋
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //右旋：
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //节点x的父节点 是x祖父节点的右孩子：

            //获取x节点的叔叔节点y:
            Entry y = leftOf(parentOf(parentOf(x)));
            //判断叔叔节点y是否为红色：
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);12
                setColor(y, BLACK);5
                setColor(parentOf(parentOf(x)), RED);10
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //左旋：
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
...
//获取节点的颜色：
private static  boolean colorOf(java.util.TreeMap.Entry p) {
    //节点为null,则默认为黑色；
    return (p == null ? BLACK : p.color);
}

//获取p节点的父节点：
private static  Entry parentOfEntry p) {
    return (p == null ? null: p.parent);
}

//对节点进行着色，TreeMap使用了boolean类型来代表颜色（true为红色，false为黑色）
private static  void setColor(Entry p, boolean c){
    if (p != null)
        p.color = c;
}

//获取左子节点：
private static  Entry leftOf(Entry p) {
    return (p == null) ? null: p.left;
}

//获取右子节点：
private static  Entry rightOf(Entry p) >	{
    return (p == null) ? null: p.right;
}

//左旋：
private void rotateLeft(Entry p) {
    if (p != null) {
        java.util.TreeMap.Entry r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

//右旋：
private void rotateRight(Entry p) {
    if (p != null) {
        Entry l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

public interface SortedMap extends Map {
 
    //返回元素比较器。如果是自然顺序，则返回null；
    Comparator comparator();
    
    //返回从fromKey到toKey的集合：含头不含尾
    java.util.SortedMap subMap(K fromKey, K toKey);

 	//返回从头到toKey的集合：不包含toKey
 	java.util.SortedMap headMap(K toKey);

    //返回从fromKey到结尾的集合：包含fromKey
    java.util.SortedMap tailMap(K fromKey);
 
    //返回集合中的第一个元素：
    K firstKey();

    //返回集合中的最后一个元素：
    K lastKey();
 
    //返回集合中所有key的集合：
    Set keySet();
 
    //返回集合中所有value的集合：
    Collection values();
 
    //返回集合中的元素映射：
    Set> entrySet();
}

public interface NavigableMap extends SortedMap {

    //返回小于key的第一个元素：
    Map.Entry lowerEntry(K key);

    //返回小于key的第一个键：
    K lowerKey(K key);

    //返回小于等于key的第一个元素：
    Map.Entry floorEntry(K key);

    //返回小于等于key的第一个键：
    K floorKey(K key);

    //返回大于或者等于key的第一个元素：
    Map.Entry ceilingEntry(K key);

    //返回大于或者等于key的第一个键：
    K ceilingKey(K key);

    //返回大于key的第一个元素：
    Map.Entry higherEntry(K key);

    //返回大于key的第一个键：
    K higherKey(K key);

    //返回集合中第一个元素：
    Map.Entry firstEntry();

    //返回集合中最后一个元素：
    Map.Entry lastEntry();

    //返回集合中第一个元素，并从集合中删除：
    Map.Entry pollFirstEntry();

    //返回集合中最后一个元素，并从集合中删除：
    Map.Entry pollLastEntry();

    //返回倒序的Map集合：
    java.util.NavigableMap descendingMap();

    NavigableSet navigableKeySet();

    //返回Map集合中倒序的Key组成的Set集合：
    NavigableSet descendingKeySet();

    java.util.NavigableMap subMap(K fromKey, boolean fromInclusive,
                                    K toKey, boolean toInclusive);

    java.util.NavigableMap headMap(K toKey, boolean inclusive);

    java.util.NavigableMap tailMap(K fromKey, boolean inclusive);

    SortedMap subMap(K fromKey, K toKey);

    SortedMap headMap(K toKey);

    SortedMap tailMap(K fromKey);
}

1.TreeMap是基于红黑树的实现，也是记录了key-value的映射关系，该映射根据key的自然排序进行排序或者根据构造方法中传入的比较器进行排序，也就是说TreeMap是有序的key-value集合。
2.TreeMap实现了NavigableMap接口，NavigableMap接口继承于SortedMap接口：对于SortedMap来说，该类是TreeMap体系中的父接口，也是区别于HashMap体系最关键的一个接口。主要原因就是SortedMap接口中定义的第一个方法Comparator comparator()；该方法决定了TreeMap体系的走向，有了比较器，就可以对插入的元素进行排序
3.NavigableMap接口是对SortedMap进一步的扩展：主要增加了对集合内元素的搜索获取操作；其实，NavigableMap的目的很简单、很直接，就是增强了对集合内元素的搜索、获取的功能。

4.TreeMap排序原理

1.使用元素自然排序：在使用自然顺序排序时候，需要区分两种情况：一种是Jdk定义的对象，一种是我们自己定义的对象

在自然顺序比较中，需要让被比较的元素实现Comparable接口，否则在向集合里添加元素时报："java.lang.ClassCastException: com.jiaboyan.collection.map.SortedTest cannot be cast to java.lang.Comparable"异常；
这是因为在调用put()方法时，会将传入的元素转化成Comparable类型对象，所以当你传入的元素没有实现Comparable接口时，就无法转换，遍会报错；

public class SortedTest implements Comparable {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    //自定义对象，实现compareTo(T o)方法：
    public int compareTo(SortedTest sortedTest) {
        int num = this.age - sortedTest.getAge();
        //为0时候，两者相同：
        if(num==0){
            return 0;
        //大于0时，传入的参数小：
        }else if(num>0){
            return 1;
        //小于0时，传入的参数大：
        }else{
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //自然顺序比较
        naturalSort();
    }
     //自然排序顺序：
    public static void naturalSort(){
        //第一种情况：Integer对象
        TreeMap treeMapFirst = new TreeMap();
        treeMapFirst.put(1,"jiabon");
        treeMapFirst.put(6,"jiabn");
        treeMapFirst.put(3,"jiabon");
        treeMapFirst.put(10,"jiabon");
        System.out.println(treeMapFirst.toString());

        //第二种情况:SortedTest对象
        TreeMap treeMapSecond = new TreeMap();
        treeMapSecond.put(new SortedTest(10),"joyan");
        treeMapSecond.put(new SortedTest(1),"jioyan");
        treeMapSecond.put(new SortedTest(13),"jioyan");
        treeMapSecond.put(new SortedTest(4),"jian");
        System.out.println(treeMapSecond.toString());
    }
}

2.使用自定义比较器排序：使用自定义比较器排序，需要在创建TreeMap对象时，将自定义比较器对象传入到TreeMap构造方法中；

自定义比较器对象，需要实现Comparator接口，并实现比较方法compare(T o1,T o2)；使用自定义比较器排序的话，被比较的对象无需再实现Comparable接口

public class SortedTest {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}
public class SortedTestComparator implements Comparator {
    //自定义比较器：实现compare(T o1,T o2)方法：
    public int compare(SortedTest sortedTest1, SortedTest sortedTest2) {
        int num = sortedTest1.getAge() - sortedTest2.getAge();
        if(num==0){//为0时候，两者相同：
            return 0;
        }else if(num>0){//大于0时，后面的参数小：
            return 1;
        }else{//小于0时，前面的参数小：
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //自定义顺序比较
        customSort();
    }
    //自定义排序顺序:
    public static void customSort(){
        TreeMap treeMap = new TreeMap(new SortedTestComparator());
        treeMap.put(new SortedTest(10),"hello");
        treeMap.put(new SortedTest(21),"my");
        treeMap.put(new SortedTest(15),"name");
        treeMap.put(new SortedTest(7),"JON");
        System.out.println(treeMap.toString());
    }
}

5.红黑树必须满几点要求：
- 1.树中每个节点必须是有颜色的，要么红色，要么黑色；
- 2.树中的根节点必须是黑色的；
- 3.树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；
- 4.树中任意一个节点如果是红色的，那么它的两个子节点一点是黑色的；
- 5.任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同
说明：NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针（均是指向null的）
6.除了给节点赋颜色之外，还会对节点进行左旋、右旋操作，以来维持树的平衡。对于树的操作，最常见的就是添加、删除。不过在添加或者删除之后，红黑树发生了改变，可能就不满足以上的5点要求，也就不是一颗红黑树了。于是我们需要通过对节点的旋转，使其重新成为一颗红黑树。
- 1.左旋：顾名思义就是对节点进行向左旋转处理
- 对节点X进行向左进行旋转，将其变成了一个左子节点；
- 这个左旋中的左，就是将被旋转的节点变成一个左节点；
- 其中，如果Y的的左子节点不为null，则将其赋值X的右子节点；
- 2.右旋：就是对节点进行向右旋转处理
- 对节点Y进行向右进行旋转，将其变成了一个右子节点；
- 这个右旋中的右，就是将被旋转的节点变成一个右节点；
- 其中，如果X节点的右子节点不为null，则赋值给Y的左子节点
7.与HashMap不同，TreeMap底层不是数组结构，成员变量中并没有数组，而是用根节点root来替代，所有的操作都是通过根节点来进行的

4.Hashtable
1.Hashtable是也是一种key-value结构，它继承自Dictionary,实现了Map接口和Cloneable以及Serializable接口。
2.Hashtable的操作几乎与HashMap一致，主要区别在于Hashtable为了实现线程安全，在几乎所有的方法上都加上了synchronized锁，从而导致Hashtable的效率十分低下
3.Hashtable不允许键或值为null,容量：HashMap底层数组长度必须为2的幂，这样做是为了hash准备，默认为16；而HashTable底层数组长度可以为任意值，这就造成了hash算法散射不均匀，容易造成hash冲突，默认为11；
4.Hash映射：HashMap的hash算法通过非常规设计，将底层table长度设计为2的幂，使用位与运算代替取模运算，减少运算消耗；而HashTable的hash算法首先使得hash值小于整型数最大值，再通过取模进行散射运算；
5.扩容机制：HashMap创建一个为原先2倍的数组，然后对原数组进行遍历以及重哈希；HashTable扩容将创建一个原长度2倍的数组，再使用头插法将链表进行反序
6.结构区别：HashMap是由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树；而HashTable一直都是数组+链表
7.继承关系：HashTable继承自Dictionary类；而HashMap继承自AbstractMap类
8.迭代器：HashMap是fail-fast；而HashTable不是。不建议使用HashTable，建议在多线程环境下使用ConcurrentHashMap类。

5.Properties

1.Properties继承于Hashtable,表示一个持久的的属性集，注意：属性列表中每个键及其对应值都是一个字符串
2.Properties类定义了两个构造方法. 第一个构造方法没有默认值。第二个构造方法使用propDefault 作为默认值。
3.Properties 类位于 java.util.Properties ，是项目配置文件所使用的类， Xxx.properties 为Java 语言常见的配置文件。（例：数据库的配置 jdbc.properties，系统参数配置 system.properties，SpringBoot配置文件application.properties）
4.Properties 类以key=value 的键值对的形式进行存储值，key值不能重复。

5.Properties继承了Hashtable 类，以Map 的形式进行放置值。输出时如果getProperty() 有当前的key值，则输出Key值对应的value 值；如果没有key值，则输出 null 值。

public class Properties extends Hashtable {
 
    private static final long serialVersionUID = 4112578634029874840L;

    protected Properties defaults;

    public Properties() {
        this(null);
    }

    public Properties(Properties defaults) {
        this.defaults = defaults;
    }
 
    public synchronized Object setProperty(String key, String value) {
        return put(key, value);
    }
 
    public synchronized void load(Reader reader) throws IOException {
        load0(new LineReader(reader));
    }

    public synchronized void load(InputStream inStream) throws IOException {
        load0(new LineReader(inStream));
    }

    private void load0 (LineReader lr) throws IOException {
        char[] convtBuf = new char[1024];
        int limit;
        int keyLen;
        int valueStart;
        char c;
        boolean hasSep;
        boolean precedingBackslash;

        while ((limit = lr.readLine()) >= 0) {
            c = 0;
            keyLen = 0;
            valueStart = limit;
            hasSep = false;

            //System.out.println("line=<" + new String(lineBuf, 0, limit) + ">");
            precedingBackslash = false;
            while (keyLen < limit) {
                c = lr.lineBuf[keyLen];
                //need check if escaped.
                if ((c == '=' ||  c == ':') && !precedingBackslash) {
                    valueStart = keyLen + 1;
                    hasSep = true;
                    break;
                } else if ((c == ' ' || c == 't' ||  c == 'f') && !precedingBackslash) {
                    valueStart = keyLen + 1;
                    break;
                }
                if (c == '\') {
                    precedingBackslash = !precedingBackslash;
                } else {
                    precedingBackslash = false;
                }
                keyLen++;
            }
            while (valueStart < limit) {
                c = lr.lineBuf[valueStart];
                if (c != ' ' && c != 't' &&  c != 'f') {
                    if (!hasSep && (c == '=' ||  c == ':')) {
                        hasSep = true;
                    } else {
                        break;
                    }
                }
                valueStart++;
            }
            String key = loadConvert(lr.lineBuf, 0, keyLen, convtBuf);
            String value = loadConvert(lr.lineBuf, valueStart, limit - valueStart, convtBuf);
            put(key, value);
        }
    }

2.线程安全的集合

CopyOnWriteArrayList CopyOnWriteArraySet ConcurrentSkipListSet ConcurrentHashMap ConcurrentSkipListMap ConcurrentLinkedQueue ConcurrentLinkedDeque

集合-高级

Java相关栏目本月热门文章