认识集合

在java程序中 **集合是存放数据的容器**，它数组一样。但是但是 是存在差异的，从使用上说，集合更为方便，因为集合容量会随着元素的增减自动变化，而且集合提供丰富的方法来操作元素。而数组是一种非常基础的数据容器，直接使用不是很方便。

数组=它是语法层面提供的数据存储的简单容器，几乎所有的语言都提供了这个数组。
**集合=数据结构+算法**，不同的集合一般都依托于某种数据结构，比如ArrayList 底层使用的数组。

List集合

认识List接口

List接口是Collection的一个子接口，它代表的是有序集合（ 元素有序 有下标 可以重复 ），它在Collection基础上新增了一些个与下标操作相关的方法。

List接口实现类

其主要的实现类有

1. ArrayList
2. LinkedList
3. Vector

疑问？都是做相同的事情，为什么要搞个实现呢？
答案：因为他们底层的数据结构和算法乃至于线程安全性问题不同。

List接口常用方法

List方法来自两个部分，继承Collection的和自己的。

Collection集合常用方法

public static void main(String[] args) {
        //实例化集合
       Collection list  = new ArrayList();
        Actress a1 = new Actress("苍井空",30,'F',"上班的第一天.AVI");
        Actress a2 = new Actress("小泽玛利亚",31,'G',"坐轻轨去上班.AVI");
        Actress a3 = new Actress("波多野结衣",33,'C',"回家的诱惑.AVI");
        Actress a4 = new Actress("武藤兰",25,'D',"在学校的一天.AVI");
       //1 添加一个元素  add(Object obj):void
       list.add(a1);
       list.add(a2);
       list.add(a3);
       list.add(a4);
       //声明一个国产明星集合
       Collection other = new ArrayList();
       other.add( new Actress("白百何",40,'F',"失恋33天")  );
       other.add( new Actress("马蓉",41,'G',"宝强块回来")  );
       //2 添加一个集合 add(Collection obj):void
       list.addAll(other);
       //3 获得元素个数  size()
       System.out.println(list.size());
       //4 清空全部元素 clear():void
       //list.clear();
       //System.out.println(list.size());
       //5 判断是否包含指定元素
       System.out.println(list.contains(a4));
       System.out.println(list.containsAll(other));
       //6 判断集合是否为空集合 isEmpty():boolean
       System.out.println(list.isEmpty());
       //7 移除元素  remove(Object obj)   removeAll(Collection obj)
       //list.remove(a1);
       list.removeAll(other);
       //8 集合转数组  toArray()
       Object[] arr = list.toArray();
       System.out.println(Arrays.toString(arr));
       //9 集合求交集 retainAll(Collection list)
        Collection s1 = new ArrayList();
        s1.add("A");
        s1.add("B");
        s1.add("C");
        Collection s2 = new ArrayList();
        s2.add("A");
        s2.add("B");
        s2.add("f");
        s1.retainAll( s2);
        System.out.println(s1);
        //10 集合的遍历：foreach   快捷键：iter
        for (Object o : list) {
            System.out.println(o);
        }
    }
}

自身扩展的方法

public static void main(String[] args) {
        List list = new ArrayList();
        list.add("唐僧");
        list.add("八戒");
        list.add("小明");
        list.add("晓东");
        //1 插入方法 add(int index , Object obj)
        list.add(1,"悟空");
        //2 获取元素的方法 get(int index):Object
        System.out.println(list.get(0));
        //3 移除元素 remove(int index):Object
        list.remove(2);
        //4  截取一段元素 subList( int index , int end )
        List sonList =   list.subList(1, 3);
        System.out.println(sonList);
        //5 修改指定位置的元素 set(int index , Object obj)
        list.set(0,"唐三藏");
        //6  查找元素下标 indexOf(Object obj)
        int n = list.indexOf("晓东");
        System.out.println(n);
        System.out.println("-------- 遍历 -----------");
        for( Object e : list){
            System.out.println(e);
        }
}

List集合遍历方式【掌握】

1. 普通for循环

   public static void main(String[] args) {
       Actress a1 = new Actress("苍井空",30,'F',"上班的第一天");
       Actress a2 = new Actress("小泽玛利亚",31,'G',"坐轻轨去上班");
       Actress a3 = new Actress("波多野结衣",33,'C',"回家的诱惑");
       Actress a4 = new Actress("武藤兰",25,'D',"在学校的一天");
       //实例化一个集合
       List list = new ArrayList();
       //核心中的核心方法 添加元素
       list.add(a4);
       list.add(a2);
       list.add(a1);
       list.add(a3);
       System.out.println("------------------- 有序集合遍历方式 1： 普通for --------------------");
       for( int i=0; i< list.size() ; i++   ){
           Object obj = list.get(i);//根据下下标找元素
           Actress actress = (Actress) obj;
           System.out.println( actress.getProduct()  );
       }
   }

2. 增强for循环

• 用来遍历集合和数组

格式：

for（集合/数组数据类型  变量名：集合名/数组名）{
            循环体
          sout（变量名）
    }

   public static void main(String[] args) {
        Actress a1 = new Actress("苍井空",30,'F',"上班的第一天");
        Actress a2 = new Actress("小泽玛利亚",31,'G',"坐轻轨去上班");
        Actress a3 = new Actress("波多野结衣",33,'C',"回家的诱惑");
        Actress a4 = new Actress("武藤兰",25,'D',"在学校的一天");
        //实例化一个集合
        List list = new ArrayList();
        //核心中的核心方法 添加元素
        list.add(a4);
        list.add(a2);
        list.add(a1);
        list.add(a3);
        System.out.println("-------------------  有序集合遍历方式 2： 增强for -------------------  ");
        for( Object obj : list ){
            Actress actress = (Actress) obj;
            System.out.println(actress.getName());
        }
   }

List实现类区别【掌握】

ArrayList 特点

ArrayList 它底层依靠**数组**实现的 使用 Object[] elementData 存储数据。**查询快** ，**增删慢**。每次扩容增长0.5倍。ArrayList 是线程不安的，多线程环境下不保证数据一致性。

ArrayList 细节补充

• 1 可以加入null，并且可以加入多个
• 2 arrayList 是由数组来实现数据存储的

• 3 arrayList 基本等同于vector 除了arrayList 是线程不安全 （执行效率高）在多线程情况下不建议使用arrayList

  底层源码分析

• arrayList 提供两个构造器进行初始化

  • 无参构造 ```java public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 点进去是一个空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   - 有参构造
```java
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

• 两种方式区别
  • 无参数构造初始化的容量为10，之后扩容按照 1.5倍扩容
  • 当进行了arrayList.add操作 ```java public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! size为类中声明int类型变量 elementData[size++] = e; return true; } // 进入ensureCapacityInternal， 入参为 最小容量，上面的size +1 private void ensureCapacityInternal(int minCapacity) { // elementData 数组底层用来存放数据的 object 类型数组 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

// calculateCapacity 进行计算 // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组为空，前面提到过 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 判断，如果底层数组为空 返回 10 与最小容量的对比，返回最大的一个值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // math.max 取最大值 并返回 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } // ensureExplicitCapacity 入参为前面比较的结果，这个方法来确定是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 记录扩容次数

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)  // 如果数组内部元素个数 已经大于原数组长度，调用grow进行扩容
        grow(minCapacity);
}

// grow 扩容的关键 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 每次扩容为 旧容量向右位移1位，即除以2，所以是按照1.5倍进行扩容。 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: // 扩容之后吧新的容量copy到老的数组底层中 elementData = Arrays.copyOf(elementData, newCapacity); }

<a name="SzxOV"></a>
#### ArrayList总结

- ArrayList的此层操作机制源码分析，重难点
   - 1 arrayList 中维护了一个Object 类型的数组 <br />elementData 所以可以塞入任何类型的数据
   - 2 当创建 ArrayList 对象时，如果使用的时午餐构造器，<br />则初始 elementData容量为0 第一次添加，则扩容elementData容量为10 <br />如果需要再次扩容，则扩容为1.5倍<br />    int newCapacity = oldCapacity + (oldCapacity >> 1);  扩容主要代码<br />   主要涉及方法 ensureCapacity  ensureExplicitCapacity  grow  <br />   第一此扩容为 10的 1.5倍，因为初始化容量为 10 ，后续则以当前容量进行1.5倍扩容
   - 3 如果使用的时指定大小的构造器，则出事容量为 指定大小，如果需要扩容，则直接扩容为1。5倍
<a name="N803y"></a>
#### Vector 特点
它和ArrayList实现原理一样。默认每次扩容增长1倍，这个类是一个古老的集合类，JDK1.O提供的有序集合类，他是**线程安全**的，效率低，在JDK1.2推出的ArrayList 代替它的功能，这个类几乎不用了。

- 废话不说，直接上源码
```java
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  # 如果面试闻到为什么 vctor 就可以说
     public synchronized void ensureCapacity(int minCapacity) {
        if (minCapacity > 0) {
            modCount++;
            ensureCapacityHelper(minCapacity);
        }
    } 
方法有synchronized进行修饰，扩容相关方法与前面arraylist接近，但是核心点不同，下面看核心点，直接决定了扩容的倍数


    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);
    }
    //  看源码得知，vector是简单粗暴的就容量大小 + 新容量大小，所以他的扩容是2倍
    那么 vector的初始化的时候容量大小为多少呢？还是去源码中查看
     /**
     * Constructs an empty vector with the specified initial capacity and
     * with its capacity increment equal to zero.
     *
     * @param   initialCapacity   the initial capacity of the vector
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
     // 有参数构造，指定容量
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     */
     // 无参数构造，默认10
    public Vector() {
        this(10);
    }

arrayList 与 vector比较

* vector 和 arrayList 的比较
arrayList | 可辨数组 ｜ jdk1.2 | 不安全 效率高 ｜ 有参数构造 扩容1.5倍，无参构造 第一次10 第二次开始1.5倍扩容
vector    | 同上     | jdk1.0 | 安全 效率不高  ｜ 如果午餐，默认10，满后，2倍扩容，如果指定大小，则每次直接按照2倍扩容

LinkedList 特点

**链表**这种数据结构，**查询慢**，**增删快**，当然他还是实现了队列相关功能，同时它也不保证线程安全。

LinkedList底层结构

• 底层维护了一个双向链表，，简单来说，链表中的元素，既有 prev 向前的指向，也有 next 向后的指向，所以叫做双向。
• linkedList 中维护了两个属性 first 和 last 分别指向，首节点和尾节点
• 每个节点 node对象 ，里面又维护了 prev next item 3个属性，其中通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表

• 所以linkedList的额元素的添加和删除，不是通过数组完成的，相对而言效率较高 ```java

  进入源码，可以看到 linkedList 中静态成员类

  private static class Node {

            E item;
            Node<E> next;
            Node<E> prev;
  
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;  # 元素本身
                this.next = next;     # 元素的下一个指向
                this.prev = prev;     # 元素的前一个指向
            }
        }
        # 对node类进行理解有助于理解双向链表
  

看图来进行理解<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/1608527/1630024788327-1ad3c814-fb00-454b-8e83-cb89ae1992d8.png#clientId=u82c1025e-864d-4&from=paste&id=ua67a6cf3&margin=%5Bobject%20Object%5D&name=image.png&originHeight=292&originWidth=660&originalType=binary&ratio=1&size=60884&status=done&style=none&taskId=u70a2a009-cc88-4877-898a-45582bb466b)

- 每一个节点既有向前的一个指向，也有向后的一个指向，那么现在把他们连起来的话
- ![image.png](https://cdn.nlark.com/yuque/0/2021/png/1608527/1630024865751-7aee0528-9c98-482f-9ff5-912c64638afa.png#clientId=u82c1025e-864d-4&from=paste&id=u5ad07f25&margin=%5Bobject%20Object%5D&name=image.png&originHeight=222&originWidth=610&originalType=binary&ratio=1&size=45397&status=done&style=none&taskId=u93e8bd2b-3c8c-42b2-bf82-6129ec9732a)

在图片理解的基础之上进入源码的分析
```java
       public LinkedList() {
       }   // 首先调用构造方法

        transient Node<E> first;  // first = null   
        transient Node<E> last;  // last = null 

// 接着当我们进行一个插入操作的时候，来看看源码层面发生了什么
    public boolean add(E e) {
        linkLast(e);  // 调到了 linkLast ，追进去
        return true;
    }
// linkLast 就是 add的核心方法了，接下来进行分析
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
// 还记得前边提到过的吗，节点中存在last 和 first
        final Node<E> l = last;  // 首先节点 l 设置为last 而last 为null
        final Node<E> newNode = new Node<>(l, e, null);  // 这一步要参照前面的node类来看
// 创建一个newNode对象，这个对象的 prev 为 l，即null， item 为 e 即元素本身， next 为null
// 新创建的节点付给 last节点进行保存，同时判断 l 是否为 null，其实际意义在于判断 链表中的last是否为null
        last = newNode;
        if (l == null)
            // 为null 则吧 newNode 设置为 first
            first = newNode;
        else
            // 不为null 则吧 最后一个节点的next指向增加的节点。
            l.next = newNode;
        size++;
        modCount++;
    }
// 其实在第一次进行添加的时候，节点的前后指向都是null，因为只有一个节点存在
// 在添加了第二个元素的时候，就会发生变化
// 第一个   item1.prev = first ,item1.next = item2 
// 第二个   item2.prev = item1， item2.next = null

增删改查

• 删除方法需要知道的是 remove() 底层调用的实际上是 removeFirst ，拿掉双向链表的第一个节点。
• 这其实比较有有意思，前面加入节点是在链表的末尾进行添加，而对链表进行删除则是从第一个节点开始删除，

• 下面看源码

  remove();   将f指向的双向链表的第一个节点拿掉 
       public E remove() {
                         return removeFirst();
     remove 方法实际底层调用为removeFirst
     在向下底层为  unlinkFirst        
        private E unlinkFirst(Node<E> f) {
             // assert f == first && f != null;
             final E element = f.item;        // 首先吧元素的值取出来 用element保存
             final Node<E> next = f.next;     // 取得 节点.next 并用next变量保存 next 当前为元素的next指向
             f.item = null;                   // 吧节点元素 置为null
             f.next = null; // help GC        // 节点.next 指向 置为null
             first = next;                    // first = 节点的.next 即 吧节点的next付给first 
             if (next == null)                // 如果节点的next 为null，即如果当前元素的next指向为null，即是 元素之后没有任何元素，，就吧last设为null
                 last = null;                 // 那么last 也置为null
             else                             // 如果节点的 next 不为null
                 next.prev = null;            // 如果节点的next指向不为null，即代表元素后面仍然有其他元素，吧下一个元素的prev指向定为null
             size--;
             modCount++;
             return element;
         }
        set（index,value） 修改
        get(1) 得到某个节点的对象
        因为linkedList 实现了list接口，所以可以使用迭代器，增强for来进行遍历
  

• remove中做的事情。

• 迭代不在进行赘述，因为实现了collection接口，所以底层支持 foreach遍历 iterator遍历。

  Iterator迭代器

  java.util.Iterator接口：迭代器（对集合进行遍历）
  两个常用的方法
  **boolean hasNext()**：判断集合中还有没有下一个元素，有就返回true，没有就false
  **E next()**：取出集合中的下一个元素

迭代器的使用步骤（重点）

• 先获取集合上的迭代器：**Iterator it = list.iterator**_**()**_**;**
• 先判断迭代器后是否有数据：**it.hasNext**_**()-->boolean**_

• 通过迭代器获取集合的元素：**it.next**_**()**_**;** ```java public class CollectionDemo { public static void main(String[] args) {

    Collection list = new ArrayList();
    list.add(123);
    list.add(true);
    list.add("hello");
  
    //迭代器
    //step1
    Iterator it = list.iterator();
    //step2
    while (it.hasNext()){
    //step3
        Object next = it.next();
        System.out.println(next);
  }
  

  } }

<a name="jkzSK"></a>
## 泛型
<a name="GQoWz"></a>
### 泛型概念
泛型指的是类型参数化的一个技术，在设计类/接口的时候，如果他们内部某些地方的类型无法确定，可以使用一个占位符，先站位，使用这个类或接口的时候再指定（把类型的确定推迟到这个类具体使用的时候）。
<a name="okgYH"></a>
#### 
<a name="QV9Tx"></a>
### 泛型集合使用
```java
//泛型集合 使用
public class GenericCollectionDemo {
    public static void main(String[] args) {
        Actress a1 = new Actress("苍井空",30,'F',"上班的第一天");
        Actress a2 = new Actress("小泽玛利亚",31,'G',"坐轻轨去上班");
        Actress a3 = new Actress("波多野结衣",33,'C',"回家的诱惑");
        Actress a4 = new Actress("武藤兰",25,'D',"在学校的一天");

        //实例化集合指定泛型参数
        List<Actress> list = new ArrayList<>();
        //添加对象
        list.add(a1);
        list.add(a2);
        list.add(a3);
        list.add(a4);

        //遍历
        for( Actress o : list){ //不用Object 用泛型指定的类型就可以了,不用转型方便
            System.out.println(o.getName());
        }
    }
}

开发中通常都是使用泛型集合，保证元素的单一性，同时元素类型不会提升，使用时无需转型

泛型类/接口定义/泛型方法

比如定义一个位置类，但是不想把x y 坐标的类型定死，这是使用X,Y字母 来占位，通常使用的有**E** **K** **V** **T** 这些。

//定义带有泛型的类
public class Position<X,Y> {
    X x;
    Y y;
    public Position(X x, Y y) {
        this.x = x;
        this.y = y;
    }
    public X getX() {
        return x;
    }
    public void setX(X x) {
        this.x = x;
    }
    public Y getY() {
        return y;
    }
    public void setY(Y y) {
        this.y = y;
    }
}

//泛型原理
public class GenericPrinciple {
    public static void main(String[] args) {
        //使用类时 必须指定具体X Y字母的类型
        Position<Integer,Integer> position = new Position<>(10,20);
        System.out.println(position.getX());
        System.out.println(position.getY());
        System.out.println("----------------------------");
        //使用类时 必须指定具体X Y字母的类型
        Position<String,String> position2 = new Position<>("东经30","北纬50");
        System.out.println(position2.getX());
        System.out.println(position2.getY());
    }
}

使用泛型技术可以让代码更灵活，一个类当无数个类使用，需要注意的是 基本数据类型不支持泛型，需要使用其包装类

泛型限定

指的是设计泛型方法的时候，方法参数存在的一些泛型类型要求

public static void m1(List<Integer> obj ){  // 接收一个特定泛型的集合 参数

}

public static void m2( List<?> obj   ){ // 接收一个任意泛型的集合 参数 ？不限定

}
public static void m3(List< ? super Integer > obj ){ // 接收一个特定泛型及其父类类型 的集合参数

}
public static void m4(List< ?extends Number > obj ){ // 接收一个特定泛型及其子类类型 的集合参数

}

泛型擦除

java中泛型是一种伪泛型，编译效果，一旦编译泛型就没有泛型信息了，所以需要注意就是不同的泛型类型不可重载。

public static void m1(List<Integer> obj ){

}
public static void m1(List<Double> obj ){ // 报错不可重载

} 
//--------------------泛型擦除后------------------------
public static void m1(List obj ){ // 参数一样了

}
public static void m1(List obj ){ // 参数一样了

}

泛型不支持多态

public static void main(String[] args) {
    List<Integer> brr = new ArrayList<>();

    List<Number> arr ;

    arr= brr; //报错 不可直接赋值,不考虑多态问题，泛型类+   具体类型完全是一个全新类型。
}

泛型通配符

**<？>**不确定接受的类型就用通配符

public class Test02 {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");

        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(12);
        list2.add(23);
        list2.add(56);

        print(list1);
        print(list2);
    }
   // 不确定接受的类型就用通配符 ArrayList<?>
    public static void print(ArrayList<?> list){
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

}

Set集合

Set接口的特点

Set表示的是 **无序 无下标 元素不可重复** ,它也是一个子接口但是没有扩展新的方法，也就是说只有Collection接口中的方法。

Set接口的实现类

1. HashSet：底层是（**哈希表+红黑树**）实现的，无索引、不可存储重复元素
2. LinkedHashSet：底层是 (**哈希表+链表**)实现的，无索引、不可存储重复元素，可以保证存取顺序
3. TreeSet：底层是**二叉树**实现，一般用于排序，可以有序，去重

   HashSet底层机制说明

   hashSet底层机制说明
   - 分析hashSet的添加元素底层是如何实现 hash() + equals()
   _- _hashSet底层是hashMap ，hashMap 底层是(数组 + 链表 + 红黑树)

1 hashSet 底层是HashMap
2 添加一个元素的时候 先得到hash值，会转成 索引值
3 找到存储数据表table，看这个索引位置是否已经存放的有元素
4 如果没有，直接加入
5 如果有，调用equals 比较，如果相通，就放弃添加，如果不相同，则添加到最后
6 在java8中，如果一条链表的元素个数超过 TREEIFY——THRESHOLD 默认是8 并且table的大小 >=
MIN_TREEIFY_CAPACITY 默认为64 就会进行树化 即 红黑树�

HashSet源码层面解读

• hashSet 是 set接口的一个实现类，而hashSet的底层是hashMap，所以通过hashSet底层源码追读可以了解hashMap在源码层面是如何工作的，下面切入源码去看
• hashSet初始化 以及第一次添加元素进入的源码解读。

    public static void main(String[] args) {


        Set set = new HashSet();

        //走源码 查看 add底层
        set.add("addicated");
        set.add("java");
        set.add("addicated");
    }
// 上为测试代码

 1   首先 调用 hashSet的无参构造器，这步没有什么难的，打断点追进去即可
    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();  // 可以看到hashSet底层调用hashMap的构造器
    }

 2  执行add 方法
  public boolean add(E e) {  e 即是添加进去的元素
        return map.put(e, PRESENT)==null; // 这里可以看到调用的其实是map.put方法去追加元素
        // map 则是前面初始化的hashMap
     }

 3 执行put方法。  该方法会追星 hash（key) 得到key对应的hash值
      // Dummy value to associate with an Object in the backing Map
      private static final Object PRESENT = new Object();

      public V put(K key, V value) {  // key 是什么 ？ 是addicated 即add的值                                                  // value 是什么？ 上面的 PREsent 理解为一个常量
        return putVal(hash(key), key, value, false, true);
    }

4    public V put(K key, V value) {
        // 关键是 hash（key）
        return putVal(hash(key), key, value, false, true);
    }
    // hash 方法
      static final int hash(Object key) {
        int h;
    // 如key传进来是空，就不进行运算，直接为0，否则拿到key的hashcode  按位异或 无符号位移16位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }
5 putVal 方法 这个是 add 操作底层最核心的难点
             执行 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;  // 辅助变量
        // if 语句表示如果当前table是null的，或者大小为0
        // 就是第一次扩容，到16个空间
        if ((tab = table) == null || (n = tab.length) == 0)  // table 为hashmap中的一个数组 类型是 node[]
        // 经过resize方法之后 tab 被定义成有16个空间的空数组， 而这个resize里面有一个缓冲机制，缓冲的系数为 0。75 即，超过12个空间被占用之后扩容
            n = (tab = resize()).length;

        // 1 根据key 得到hash 去计算该key应该存放到ttable表的的哪个索引位置
        // 并把这个位置的对象 赋给p
        // 2 判断p 是否为null
            // 2。1 如果p为null 表示还没有存放过数据，就创建一个 Node(key="addicated",value =PRESENT)
            // 2。2 否则 就放在该位置 tab[i] = newNode(hash, key, value, null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        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);
            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)  // 判断是否大雨12 大于则扩容
            resize();
        afterNodeInsertion(evict);  // 这是一个空方法，主要是留给hashmap的子类来去实现
        return null;  // 返回一个空则代表添加成功了，否则则是失败

• 上述为hashSet第一次添加元素的源码，比较乱，需要自行debug追入才能更好的理解。

  常用API

  和Collection中的一致，无需重复学习。

无序集合遍历

1. 迭代器

2. 增强for ```java public class SetDemo {

   public static void main(String[] args) {

    //无序无下标不可重复
    Set<String> sets = new HashSet<>();
    sets.add("Java");
    sets.add("MySQL");
    sets.add("Java");
    sets.add("H5");
    sets.add("MMP");
    sets.add("HMP");
    System.out.println(sets); //[Java, MySQL, php, H5]
   

    //遍历
    System.out.println("---------------迭代器-----------------");
    Iterator<String> it = sets.iterator();
    while ( it.hasNext() ){
        String obj = it.next();
        System.out.println(obj);
    }
    System.out.println("---------------增强for-----------------");
    for( String obj : sets){
        System.out.println(obj);
    }
    System.out.println("---------------查找-----------------");
    for( String obj : sets){
        char c = obj.charAt(0);
        if(c=='H'){
            System.out.println(obj);
        }
    }
}

}

> Set集合不可以单独直接取出某个元素，需要遍历筛选出你要的元素


<a name="Ob5Ou"></a>
### HashSet去重
HashSet去重原理：

- 添加元素的时候，先判断对象的hashcode 是否与现有元素的hashcode 相同。
- 不相同：直接保存
- 相同： 需要进一步判断 equals 是否和现有元素相同
- 相同： 放弃保存
- 不同： 保存

自定义类型：如果希望自定义类型，成员相同的时候，不要重复添加到Set集合，则需重写两个方法 `**hashCode()**`  `**equals()**`** **
```java
class Book{

    String name;
    String author;

    public Book() {
    }

    public Book(String name, String author) {
        this.name = name;
        this.author = author;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", author='" + author + '\'' +
                '}';
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + (author != null ? author.hashCode() : 0);
        return result;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Book book = (Book) o;

        if (name != null ? !name.equals(book.name) : book.name != null) return false;
        return author != null ? author.equals(book.author) : book.author == null;
    }
}

HashSet 集合底层 是套娃 HashMap

LinkedHashSet 【了解】

HashSet子类，可以记录元素的添加顺序，底层使用LinkedHashMap。

public class LinkedHashSetDemo {

    public static void main(String[] args) {

        Set<String> sets = new LinkedHashSet<>();
        sets.add("Hello");
        sets.add("CSS");
        sets.add("MySQL");
        sets.add("Hello");

        System.out.println(sets);
    }
}

TreeSet 【了解】

他是Sorted接口的实现类，具备元素可排序的能力，可以把元素按照从小到大或者从大到小排列（可以把元素升序降序排列）。它的底层套娃 TreeMap

自然排序

• 排序规则
  • 如果调用无参数构造器，则是自然排序，何谓自然排序，即，在添加对象的时候，会吧自动使用对象的compareTo方法，要求添加的对象类必须实现compareable接口。
  • 如果需要自定义排序，则是调用有参构造器并以匿名内部类的方式实现Compator并重写compare方法，详情见Treeset解读文章

Book类

package set;

public class Book implements   Comparable  {
    String name;
    String author;
    double pirce;
    //省略其他
    //自动定义比较规则的方法
    @Override
    public int compareTo(Object o) {
        Book book = (Book) o;
        if(this.pirce > book.pirce){
            return 1;
        }
        if( this.pirce< book.pirce ){
            return -1;
        }
        //return 0; //去重
        return  this.name.compareTo(book.name);
    }
}

测试类

public class TreeSetDemo {
    public static void main(String[] args) {
        System.out.println("------------自用自然排序------------------");
        Set<Book> books = new TreeSet<>();
        books.add( new Book("西游记","a",10) );
        books.add( new Book("西游记后传","a",23) );
        books.add( new Book("西游记前传","a",9) );
        for (Book book : books) {
            System.out.println(book);
        }
    }
}

排序器排序

这种方式需要在创建TreeSet实例的时候传入一个Comparator接口的实例，通常使用匿名内部类来做。元素类不需要实现Comparable 接口。

package set;

public class Book  {
    String name;
    String author;
    double pirce;
    //省略其他
}

public class TreeSetDemo {

    public static void main(String[] args) {

        System.out.println("-----------使用排序器排序-------------------");
        Set<Book> books = new TreeSet<>( new Comparator<Book>() {
            @Override
            public int compare(Book o1, Book o2) {
                if(o1.pirce>o2.pirce){
                    return 1;
                }
                if(o1.pirce<o2.pirce){
                    return -1;
                }
                return 0;
            }
        } );
        books.add( new Book("西游记","a",10) );
        books.add( new Book("西游记后传","a",23) );
        books.add( new Book("西游记前传","a",9) );
        for (Book book : books) {
            System.out.println(book);
        }
    }
}

Map集合

理解Map 映射

map接口，也是一种容器，存储的数据是成对出现，**key-->value**
注意点：

• 存储无序的键值对
• key必须是唯一的，而且和value是一一对应

常用API

public class TestMap {

    public static void main(String[] args) {
        //实例化一个map集合
        Map<String,String> maps= new HashMap<>();
        //1 添加元素（key-value） put(K key, V value)
        maps.put("apple","苹果");
        maps.put("actress","女优");
        maps.put("student","学生");
        maps.put("teacher","老师");
        //2 根据key 获得value    get(K key):V
        String actress = maps.get("apple");
        System.out.println(actress);
        //3 获得元素个数          size():int
        System.out.println(maps.size());
        //4 清空全部元素          clear():void
         //maps.clear();
        //5 检查键 containsKey(K key):boolean
        System.out.println(maps.containsKey("apple1"));
        //6 检查值 containsValue(K key):boolean
        System.out.println(maps.containsValue("女优"));

        //7 移除元素 remove(K key):V
        maps.remove("teacher");
        System.out.println(maps);
    }
}

Map集合遍历[ 掌握 ]

根据keySet()

Map集合提供了一种视图，这个视图就是可以看见和搜集全部键的集合

/**
 * Map集合遍历
 */
public class MapDemo {
    public static void main(String[] args) {

        //实例化Map集合
        Map<String, String> map = new HashMap<>();

        //添加元素 key要唯一
        map.put("台湾","周杰伦");
        map.put("香港","刘德华");
        map.put("大陆","黄渤");

        System.out.println("---------------------- keySet()----------------------");
        Set<String> keySet = map.keySet();
        for (String key : map.keySet()) {
            String value = map.get(key);
            System.out.println(key+":"+value);
        }
    }
}

根据entrySet()

Map集合提供了一种视图，这个视图就是可以看见和搜集全部的 把键值视为一个整体**(Map.Entry<K,V>)** 的集合。Entry是Map中的内部类类型。

/**
 * Map集合遍历
 */
public class MapDemo {
    public static void main(String[] args) {

        //实例化Map集合
        Map<String, String> map = new HashMap<>();

        //添加元素 key要唯一
        map.put("台湾","周杰伦");
        map.put("香港","刘德华");
        map.put("大陆","黄渤");

        System.out.println("-----------------------entrySet()---------------------");
        Set<Map.Entry<String,String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry : entries) {
            System.out.println(entry);
        }
    }
    }

遍历全部值values()

Map集合提供了一种视图，这个视图就是可以看见和搜集全部的value，全部的value构成一个Collection的集合，而搜集的方法就是 values():Collection。

public class MapDemo {
    public static void main(String[] args) {

        //实例化Map集合
        Map<String, String> map = new HashMap<>();

        //添加元素 key要唯一
        map.put("台湾","周杰伦");
        map.put("香港","刘德华");
        map.put("大陆","黄渤");

        System.out.println("-----------------------values()------------------------");
        Collection<String> values = map.values();
        for (String value : values) {
            System.out.println(value);
        }
    }
    }

Map 集合实现类区别

HashMap 特点

它是最常用的Map实现类，底层使用 hash表，它是一种(数组+链表+红黑数)数据结构，不保证线程安全。HashSet底层就是使用的HashMap实现的功能，并且只使用了它的Key空间。HashMap的键是**无序**的，且允许包含空键和空值。

Hashtable 特点

它也是Map实现类，但是它是一个古老映射集合，是jdk1.0的集合，它是线程安全的。实现原理也就是hash表，就是说实现原理和HashMap一样，API兼容。 它不允许出现空键和空值 ，HashMap可以。可以说HashMap的出现就是为了替代Hashtable，Hashtable 几乎不用。

TreeMap 特点

它是一个底层通过红黑树实现，可以把**key进行排序**。TreeSet就是可以把元素排序，应为它的底层就是使用的TreeMap，并就是利用key空间来装元素。
TreeMap 虽然可以对key排序，但是对Key的类型有要求，要求Key类型实现Comparable 接口。 这就是为什么使用TreeSet时元素类型需要实现接口的原因。