目录

 

目录

一、集合基本框架结构

二、collection接口

1、collection常用方法

2、Iterator接口的使用（以及JDK 5.0新特性–增强for循环：(foreach循环)的使用）

3、Irerator()方法细节解释 

三、Collection子接口：List接口 

（一）List接口常用方法 

 (二)List接口常用三种遍历方式

（三）实现类之一：ArrayList接口

（四）实现类之一：LinkedList接口 

（五）实现类之一：Vector接口

四、Collection子接口：Set接口 

(一)、Set接口概述

(二)、 Set接口常用方法 

(三)、Set实现类之一：HashSet

(四)、Set实现类之一：LinkedHashSet 

(五)、Set实现类之一：TreeSet

(六)、总结-开发中如何选择集合实现类

五、 Map接口 

(一)、概述

(二)、Map常用方法

 (三)、Map实现类之一：HashMap

---

---

一、集合基本框架结构

java集合基本结构可分为两大类：collection和Map两种体系、

1、collection接口:单列数据，定义了存取一组对象的方法的集合。

2、Map接口：双列数据，保存具有映射关系“key-value对”的集合。

1、collection常用子接口：List接口（其中List常用子接口又有ArrayList、LinkedList、Vector...  ）、Set接口（其中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接口的使用（以及JDK 5.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、Irerator()方法细节解释 

 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接口

1、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);
        }
    }
}