java集合解析

集合

数组的局限

• 长度开始时必须指定，而且一旦指定，不能更改

• 保存的元素必须是同一类型的元素

• 数组进行增加或者删除操作时较为麻烦

集合

• 可以动态保存多个对象
• 提供了一些方便操作对象的方法，add、remove、set、get等
• 使用集合添加、删除新元素

集合框架体系

java的集合类很多，主要分为两大类：

collection

Map

Collections方法

Collection接口实现类的特点：

1、Collection实现子类可以存放多个元素，每个元素都可以是Object

2、有些Collection的实现类，可以存放重复的元素，有些不可以

3、有些Collection的实现类，有些是有序的List，有些是无序的Set

4、Collection接口没有直接实现的子类，通过他的子接口Set和List来实现的

常用方法

• add:添加单个元素
• remove:删除指定元素
• contains:查找元素是否存在
• size:获取元素个数
• isEmpty:判断是否为空
• clear:清空
• addAll:添加多个元素
• containsAll：查找多个元素是否都存在
• removeAll:删除多个元素

ArrayList来演示

public class CollectionMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
//        add:添加单个元素
        list.add("jack");
        list.add(12);//list.add(new Integer(10));
        list.add(true);
        System.out.println("list="+list);
//        remove:删除指定元素
        //list.remove(0);//索引删除第一个元素
        list.remove(true);//对象删除
        System.out.println("list="+list);
//        contains:查找元素是否存在
        System.out.println("查找元素："+list.contains("jack"));
//        size:获取元素个数
        int size = list.size();
        System.out.println("list的大小="+size);
//        isEmpty:判断是否为空
        System.out.println("判断是否为空："+list.isEmpty());
//        clear:清空
        list.clear();
        System.out.println("list="+list);
//        addAll:添加多个元素
        ArrayList list1 = new ArrayList();
        list1.add("xiaogege");
        list1.add("daidai");
        list.addAll(list1);//添加对象collection
        System.out.println("list="+list);
//        containsAll：查找多个元素是否都存在
        System.out.println(list.containsAll(list1));
//        removeAll:删除多个元素
        System.out.println(list.removeAll(list1));
    }
}

输出结果：

list=[jack, 12, true]
list=[jack, 12]
查找元素：true
list的大小=2
判断是否为空：false
list=[]
list=[xiaogege, daidai]
true
true

Collection接口

Iterator接口

使用Iterator迭代器

1、Iterator对象称为迭代器，主要用于遍历Collection集合中的元素

2、所有实现了Collection接口的集合类都有一个iterator()方法，用于返回一个实现了Iterator接口的对象，返回一个迭代器

Iterator接口的方法

• hasNext():如果迭代器还有元素返回true
• next():返回下一个元素
• remove():从基础集合中移除迭代器返回的最后一个元素

注意：在调用it.next()方法之前必须调用it.hasNext()进行检测。若不调用，且下一条记录无效，直到调用it.next()会抛出NoSuchElementException异常

实例演示

public class CollectionIterator {
    public static void main(String[] args) {
        Collection collection = new ArrayList();

        collection.add(new Book("红楼梦","曹雪芹",32.8));
        collection.add(new Book("三国演义","罗贯中",30.8));
        collection.add(new Book("云边有个小卖铺","张嘉佳",9.9));

        //1.得到collection对应的迭代器
        Iterator iterator = collection.iterator();
        //2.使用while循环遍历
        while (iterator.hasNext()){
            Object next = iterator.next();
            System.out.println(next);
        }
        //3.当退出while循环后，这时的iterator迭代器，指向最后的元素
        //iterator.next();//NoSuchElementException
        //4.重置迭代器
        System.out.println("----------第二次遍历------------");
        iterator = collection.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next();
            System.out.println(next);
        }
    }
}
class Book{
    private String name;
    private String author;
    private double price;

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

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getAuthor() {
        return author;
    }

    public void setAuthor(String author) {
        this.author = author;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

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

for循环增强

底层仍然是迭代器，可以理解成他的简化版

实例演示

for (Object o : collection) {
    System.out.println("collection="+o);
}

注意：可以在Collection集合中使用，也可以直接在数组使用

List接口

List接口是Collection接口的子接口

• List集合类元素添加元素和取出元素顺序一致，并且可以重复
• List集合中的每个元素都有其对应的顺序索引
• List容器中的元素都对应一个整数型的序号记载在容器中的位置，可以根据序号存取容器中的元素
• JDK API中list接口的常用实现类
  • ArrayList
  • LinkedList
  • Vector

实例演示

public class List_ {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        //1.List集合类元素添加元素和取出元素顺序一致，并且可以重复
        list.add("haha");
        list.add("xixi");
        list.add("haha");
        System.out.println("list="+list);
        //2.List集合中的每个元素都有其对应的顺序索引
        Object o = list.get(2);
        System.out.println(o);
    }
}

常用的方法

• void add(int index, Object o):在index位置插入o这个元素
• 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):移除指定位置的元素，并返回此元素
• Object set(int index,Object ele):替换指定位置的元素
• List subList(int fromIndex,int toIndex):返回从fromIndex到toIndex位置的子集合

遍历方式

• iterator

  Iterator iter = col.iterator();
  while(iter.hasNext()){
      Object o = iter.next();
      System.out.println(o);
  }
  

• 使用增强for

  for(Object o:col){
      
  }
  

• 使用普通for

  for(int i=0;i<list.size();i++){
      Object object = list.get(i);
      System.out.println(object);
  }
  

ArrayList

ArrayList的注意事项

• ArrayList允许放任何的元素，包括null

• ArrayList是有数组来实现数据存储的

• ArrayList基本等同于Vector,除了ArrayList是线程不安全的，在多线程情况下，不建议使用ArrayList

  //分析源码，没有synchronized的修饰，用来做线程互斥的
  public boolean add(E e){
      ensureCapacityInternal(size+1);
      elementData[size++];
      return true
  }
  

ArrayList中的字段

1、serialVersionUID：适用于java序列化机制（通过判断类的serialVersionUID来验证的版本一致。在进行反序列化，jvm会把传来的字节流中的serialVersionUID与本地相应类的serialVersionUID进比较，如果相同说明一致，则可以进行反序列化，否则会出现反序列化版本一致的异常,就是InvalidCastException）

2、DEFAULT_CAPACITY：默认容量，为10

3、EMPTY_ELEMENTDATA：空的数组，有参构造使用

4、DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量空数组，无参构造使用

5、elementData：arrayList集合中维护的元素数组，transient表示该属性无法被序列化

6、size：集合中元素的数量

7、MAX_ARRAY_SIZE：ArrayList中定义的最大长度（Intger.MAX_VALUE）

底层操作机制源码分析

1、ArrayList中维护了一个Object类型的·数组elementData。transient Object[] elelmentData

2、当创建ArrayList对象式，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elemenData为1.5倍

3、如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍

分析使用无参构造器，创建和使用

1、创建了一个空的elementData数组

2、执行list.add

3、ensureCapaityInternal():确认大小是否够添加一个数据

• 确认minCapacity,第一次扩容为10
• modCount++作用是当前集合被修改的次数，防止多线程操作出现的异常；minCapacity大于elementData的长度，才会调用grow()底层的扩容操作

4、进入ensureExplicitCapacity，判断minCapacity是否大于数组的长度，是则调用grow（）进行扩容

5、新的容量是初次扩容（10）的1.5倍，然后将原来elementData中元素和新容量赋给新的elementData

注意：

在debug的情况下，如果看不到详细情况，是idea隐藏了

打开Settings-Build,Execution,Deployment

Vector

基本介绍

1、Vector类的定义说明

public class Vector< E >

extends AbstractList< E >

implements List< E >, RandomAccess, Cloneable, Serializable

2、Vector底层也是一个对象数组

protected Object[] elementData;

3、Vector是线程同步的，即线程安全，操作方法symchronized，就是支持线程的

4、在开发中，需要线程同步安全时，考虑使用Vector

源码解读

1、如果是无参构造，默认为10，需要扩容时，按2倍扩容

2、添加元素时，记录了当前集合被修改的次数

3、再进入ensureCapacityHelper，确认是否需要扩容

4、当需要的容量大于初始容量时，进入grow方法进行扩容

5、设置新的容量时，capacityIncrement通常为0，所以是旧容量（10）的2倍

如果指定大小，则每次直接按2倍扩容

LinkedList

基本介绍

1、LinkedList实现了双向链表和双端队列特点

2、可以添加任何元素，可以重复，也包括null

3、线程不安全，没有实现同步

4、属性first和last分别指向第一个节点和最后一个节点

属性

源码分析

1、LinkedList linkedList = new LinkedList();

    public LinkedList() {
    }

就是做了一个简单的初始化，这时LinkedList的属性first和last都为null

2、执行添加操作

public boolean add(E e) {
    linkLast(e);
    return true;
}

3、将新的节点添加到双向链表后面

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

• 添加一个节点：first和last都指向第一个节点
• 添加第二个节点：
  • l指向第一个节点
  • 新节点pre指向l
  • last指向新节点
  • l的next指向新节点，这样两个节点连接起来了

4、删除节点

linkedList.remove():默认删除的是第一个节点

1、执行 removeFirst

public E remove() {
    return removeFirst();
}

2、再执行

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

3、执行unlinkFirst

set接口

基本介绍

1、无序，添加和取出的顺序不一样，没有索引

2、不允许存放重复元素，最多包含一个null

3、常见的set接口实现类：HashSet、TreeSet等

常用的方法

Set接口也是Collection的子接口，因此常用方法和Colletion接口一样

遍历方法

1、迭代器

2、增强for

3、但是不能使用索引的方式获取

实例演示

public class Set_ {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add("heihei");
        set.add("xixi");
        set.add("haha");
        set.add("gaga");
        set.add("gaga");
        set.add(null);
        System.out.println("set="+set);//set=[null, haha, gaga, heihei, xixi]

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
        /** 输出：
         * null
         * haha
         * gaga
         * heihei
         * xixi
         */

        System.out.println("---------------------");
        for (Object o : set) {
            System.out.println(o);
        }
        /** 输出：
         * null
         * haha
         * gaga
         * heihei
         * xixi
         */
    }
}

HashSet

基本介绍

1、HashSet实际上是HashMap，所以他的底层就是HashMap

2、可以存放null，但是只能有一个null

3、HashSet不保证存放元素和取出元素的顺序一致，就是不确定，可能一致，可能不一致

4、不能有重复元素

public class HashSet01 {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        /*
        1.执行add方法后，会返回一个boolean
        2.如果添加成功，返回true，否则返回false
        3.remove指定删除对象
         */
        System.out.println(set.add("huhu"));//true
        System.out.println(set.add("gaga"));//true
        System.out.println(set.add("gaga"));//false
        System.out.println(set.add("aa"));//true

        set.remove("aa");
        System.out.println("set="+set);

        set = new HashSet();
        System.out.println("set="+set);
        set.add("made");//添加成功
        set.add("made");//添加不了
        set.add(new Dog("tom"));//可以
        set.add(new Dog("tom"));//可以。两个对象，只不过叫同一个名字
        System.out.println("set="+set);//set=[Dog{name='tom'}, Dog{name='tom'}, made]

        set.add(new String("bwh"));
        set.add(new String("bwh"));//加入不了
        System.out.println("set="+set);
    }
}
class Dog{
    private String name;

    public Dog(String name) {
        this.name = name;
    }

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

HashSet属性

• map:由此可见HashSet的底层结构是HashMap
• PRESENT:只是一个Object对象，因为HashSet底层是HashMap，要用到寻多HashMap方法，用PRESENT来占位

HashMap属性

• DEFAULT_INITIAL_CAPACITY：默认初始化容量，1左移4位，就是1 * 2 ^ 4，16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

• MAXIMUM_CAPACITY：最大容量，1*2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

• DEFAULT_LOAD_FACTOR:默认扩容因子，如果理解扩容因子，就是当内容达到一个容量的多少，就让这个容器扩容。因为向一个数组中填充，而该元素的索引值是通过某种算法随机获取的，可如果一个数组内的元素已经足够多时，那么在填充一个元素的话，这个元素出现已经有索引的概率就会增大。（可以理解为有16个桶，还有许多白球，让白球一个个进入一个桶，每个球进入每个桶的概率相同，都是16/1。那么第一个球进入一个桶后，后面的球就有可能和它进入一个相同的桶，哪怕是最极端的情况—前十六个球进入了不同的桶，第17个球也会与前面的球发生碰撞。为了尽量避免发生碰撞，当达到一定程度后，就要进行扩容。），默认到达0.75后就进行扩容，这个0.75是经过大量计算得出的（泊松分布）。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

• TREEIFY_THRESHOLD：树型阈值，即将链表树化的一个条件，默认为8。如果table数组中的一个链表的长度达到这个值（向上达到），就要将其转化树

static final int TREEIFY_THRESHOLD = 8;

• UNTREEIFY_THRESHOLD：由树转换成链表的阈值，如果table数组中的一棵树的元素个数达到了这个值（向下达到），就要将一棵树转化成链表

static final int UNTREEIFY_THRESHOLD = 6;

• MIN_TREEIFY_CAPACITY：最小树形化容量阈值，链表树化的另一个条件，只有当大于这个值（64），才能进行链表树型化

static final int MIN_TREEIFY_CAPACITY = 64;

• table：链表数组，数组的每个元素都是一条链表

add方法分析

1、添加一个元素，先得到hash值，会转化成索引值

2、找到存储数据表table，看这个索引值是否已经存放的元素

3、如果没有，直接加入

4、如果有，调用equals比较，如果相同，就放弃添加；如果不相同，则添加到最后

5、如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认为8），并且table>=

MIN_TREEIFY_CAPACITY（默认为64）就会进行树化（红黑树）

• 第一次添加元素

1. new一个HashSet对象

   

2. 进入HashSet的构造器（无参），初始化一个HashMap并将其赋给map

   

3. 进入无参构造器，扩容因子为默认扩容因子

   

4. 执行add方法

   

5. 进入put方法，key就是e（”java“），value就是PRESENT

   

6. hash(key)，根据传入的key值，获取到这个key值的hash值。如果传入的key为null，则返回0；如果传入的key不为null，将这个值进行无符号右移16位操作，再与之前的值进行异或运算，然后返回

   • 为什么进行右移16位：将元素插入到table数组时，需要根据hash值求出索引位置，方法就是这个hash值与table长度取模（hash%length），取模操作就是让n与n-1相与，但是如果直接将hash值与长度-1相与的话，会只后后几位参与运算，具体是几位取决于table长度
   • 异或运算：异或运算能更好的保留各部分的特征，如果采用&员孙计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢

   

7. 进入putVal方法，先定义辅助变量，table是HashMap的一个node数组，此时为null，所以要对table进行resize重新规划尺寸

   

8. 进入resize方法

   1、定义oldCap来记录原来table的长度，这里旧表为空，所以oldCap为0，然后让oldThr等于threshold（阈值），还有定义newCap（新容量）和newThr(新阈值)

   

   2、判断旧容量是否大于0，再判断旧阈值是否大于0，这里直接进入else语句，将新的容量为默认初始化容量（16），新的阈值默认为初始化容量*扩容因子（0.75）为12

   

   3、判断新阈值是否等于0

   

   4、将新阈值的值赋给临界值

   

   5、创建一个长度为newCap的新数组newTab赋给table

   

   6、判断旧表是否不为null，不满足，直接返回新表

   

9. 重新返回putVal方法，table和辅助数组tab都变成了（table变化是因为resize方法中将map的table变成了newTable，辅助数组tab变化是因为resize方法的返回值是newTable）

   

10. 根据key计算出的hash来计算key在tab中存放的索引位置，并且把这个这个位置的对象赋给p

    

    • 判断p是否为null，为null表示还没有存放过数据，就创建一个Node（key=”java”,value=PRESENT）hash值以后用来表示新的元素与之比较，相等的话排到后面，null表示这个元素后面没有元素，为null

      

11. 判断元素个数是否达到阈值（12），如果达到了需要重新规划

    

12. afterNodeInsertion为模板方法，在该实现类中没有具体方法实现，但是会在子类中实现，对于hashMap可以忽略

    

13. 回到putVal，返回null

    

14. 再回到add方法，需要判断put方法返回来的是不是空，也就是说，只有返回的是null，才算插入成功

    

15. 第一次add添加元素

    • 将table扩容为长度16的数组
    • 阈值确定为12
    • 将元素添加到数组中

• 再插入一个元素，与第一次添加元素差不多，还是比较简单的，因为不用扩容了

  1. 再次添加元素

     

  2. 进入map.put方法，再进入putVal方法，判断table是否为空，已经确定过新阈值和新数组不为空，这里不用重构

     

  3. 通过与hash值的&运算，得出存放i的值，然后再判断这个位置有没有元素，这里插入到索引为4的位置

     

     

  4. 判断元素个数有没有达到阈值，这里没有达到，不用重构，返回null

     

  5. 回到add方法，put方法返回null，添加元素成功

     

• 再插入一个与之前相同的元素

  1. 

  2. 进入add方法，再进入put方法，再进入putVal方法，判断table是否为空，这里不为空

     

  3. 之前添加的元素和现在元素在与hash进行&元素后得到的索引位置是一样的，所以这个位置是有元素，所以进入else语句

     

     1、if判断语句，第一个条件：第一个元素hash是否等于当前元素的hash值；第二个条件：第一个元素的key值是否等于当前添加元素的key值或者满足是相等对象。满足这两个条件，就不能加入元素

     

     • 添加之前没有添加过的元素，并且添加索引相同

       1、再判断if语句，判断p是不是一棵红黑树，如果是就调用putTreeVal方法来进行添加

       

       2、当添加元素存放到同一索引位置时，就是该索引位置已经有元素时，进入for循环，判断添加元素与p（索引第一个元素）比较是否相同，如果不相同，继续比较下一个元素，直到找到相同元素退出循环或者直到最后没有找到，就可以添加元素到链表的最后，即添加成功，跳出循环；循环到最后没有找到，再判断链表元素个数是否大于等于7，如果是，则调用treeifyBin方法对当前链表进行树化（方法中判断table元素个数大于64）；进入下一个if判断语句；如果当前链表只有一个元素，因此第一次循环直接跳出进入另一个if判断

       

       

       3、当一直找到一条链表的最后，如果都没有找到一个相同的元素，才算是插入成功。当前链表中只有一个元素，因此第一次循环就直接跳出，跳出后进入另一个if判断，判断e是否不等于null，因为上述到达了链表的最后，所以e是null。这个e只要不为null，那么hashSet对象的add方法就失败了，因为进入该if中分析发现，会将e的值返回，结合hashSet对象的add方法（返回的对象只有为null时，才算执行成功），只要进入了该方法，返回到hashSet对象的add方法的结果对象就注定不为空，因此add方法的执行结果就不正确

       

       4、不需要重新构造容量，返回null，添加成功

       

  4. 判断e是否等于null，因为添加之前添加过的元素，e指向p节点，所以不为null，进入if语句。分析发现，会将e的值返回，当退出到add方法时，只有返回对象为null，才能添加成功，所以添加失败了

     

HashSet去重机制

通过hashCode()和equals()来实现的，底层通过存入对象，进行运算得到一个hash值，通过hash值得到对象在table表对应的索引，如果该索引位置没有元素，直接添加；如果有元素，就进行遍历用equals比较是否相同，如果相同，就加入，否则不加入

总结：

1. 计算每个插入元素的hash值，并对其进行特殊的计算，得到一个特殊的hash值
2. 再根据该hash值求出该元素在链表中插入的索引位置
3. 然后查看该索引位置是否存放元素，就是确定是否是空链表，如果是空链表，直接插入
4. 如果相同，再比较该索引位置的第一个节点与插入元素的hash是否相同，如果相同再比较他们的key值，如果key值比较也相同，这是添加之前添加过的元素，直接将该节点的value域返回，即添加失败，不能添加
5. 遍历索引位置的所有节点，如果遇到当前的遍历节点的下个节点的hash值与插入元素的hash值相同，且key值相同的情况，直接将当前遍历对象的下个节点的value域返回，即添加失败
6. 遍历到最后p指向的下一个节点为空，，都没有遇到与当前节点相同的元素，就可以添加，直接将该元素插入到链表的最后，还需要判断当前链表长度和table元素个数是否进行树化操作

扩容机制

1、第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor=0.75）=12

2、如果table数组使用到了临界值12，再次扩容到16*2=32，新的临界值就是32 * 0.75=24

3、进入resize方法，定义辅助数组oldTable为table数组，oldCap为oldTab的长度（现在是16），oldThr为thrshold临界值（12），再定义新的容量newCap和临界值newThr

4、先判断原来的数组容量是否大于0，现在oldCap=16>0

1. 进入if语句，先判断oldCap是否大于最大容量，不成立
2. 然后让新容量等于旧容量的2倍，再判断是否小于最小容量，成立；再判断旧容量是否大于等于默认初始化容量，成立，让新阈值等于旧阈值的2倍

5、判断新阈值是否等于0，不成立

6、将新阈值赋给临界值，创建长度为newCap的新数组newTab，将其赋给table

7、先判断oldTab是否为null，将oldTab的内容置为null，并且把其内容赋给newTab

if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
            else { // preserve order
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> 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;
                }
            }
        }
    }
}

8、返回null，添加成功

注意：

还有一种情况会触发扩容，当size大于临界值

1、定义A、B两个类

2、在两个不同索引的位置添加元素

3、当添加到table元素个数大于12，进行扩容

4、table数组扩容为32

树化分析

1、定义一个类，并且定义其属性，然后重写hashCode方法，是每一个对象的hashCode固定，这样根据hash得到的索引位置一样

2、在同一个索引位置插入元素

1. 插入第一个元素后，table数组扩容为16

   

2. 在此索引插入八个元素

   

3、当添加第九个元素后，table数组扩容为32，没有进行树化，链表长度大于8条件满足，但是table数组没有大于等于64，所以没有进行树化

4、当添加完第九个元素，table数组扩容为64，并且九个元素全部挂到新的索引为36的链表上

5、当添加第10个元素时，此时tab不为null，并且table长度大于64，所以不进行扩容，树化

此时节点由node变为treeNode

6、返回null，添加成功

HashSet的特点

• 底层结构是链表+数组+红黑树，每一个数组都是一个链表或者红黑树
• 扩容的特点
  • 如果是第一次扩容，容量和阈值设为默认初始化的值（16和12）
  • 之后每次扩容都是将容量和阈值设为原来的两倍
• 插入元素的特点
  • 插入元素之前要先计算该元素的hash值，并对其进行特殊操作（和右移16位后的结果异或运算），并根据该”hash“值求在table数组中的索引位置
  • 第一次插入要扩容
  • 每次插入在求出索引位置之后，都要判断该索引位置是否为空，如果为空直接插入
  • 如果不为空
    • 先比较第一个节点的hash，key（如果= = 判断不成立，还要进行equals的比较）和插入元素的是否相同，如果相同直接结束，插入失败。
    • 如果第一个节点比较之后，不相同，那么需要循环与该链表（红黑树）后的每个元素都进行比较，如果遇到相同的，直接跳出，插入失败
    • 如果直到访问到最后一个节点还不相同，再用尾插法插入到链表尾部，插入成功
• 树化的特点
  • 树化的第一个条件是相同索引的链表长度大于8，在相同索引位置插入第九个元素后满足
  • 树化的第一个条件是table的长度大于等于64，在相同位置插入第10元素时满足，就会进行树化的操作，添加完后，node–>treeNode

LinkedHashSet

基本介绍

• LinkedHashSet是HashSet的子类
• LinkedHashSet底层是一个LinkedHashMap，底层维护了数组+双向链表
• LinkedHashSet根据hashCode来决定元素的存储位置，同时使用双向链表来维护元素的次序，这使得元素看起来是以插入顺序保存的
• 不允许添加重复元素

双链表结构

单链表结构

插入元素分析

1、LinkedHashSet加入顺序和取出元素的顺序一致

2、查看插入结果

• map多了head和tail，head指向头结点，tail指向为节点，这就是双向链表的结构

  

• 数组时HashMap$Node[] 存放的元素/数据是LinkedHashMap$Entry，继承关系

  

• Entry继承了Node类，并且多加了两个属性，一个是before，一个是after，before用来记录上一个entry，after用来记录下一个entry，next节点则用来记录下一个节点

  

TreeSet

基本介绍

1、TreeSet底层是TreeMap

2、使用无参构造时，创建TreeSet，仍然是无序的

演示：

@SuppressWarnings({"all"})
public class TreeSet {
    public static void main(String[] args) {
        java.util.TreeSet treeSet = new java.util.TreeSet();
        treeSet.add("haha");
        treeSet.add("gag");
        treeSet.add("xi");
        System.out.println("TreeSet="+treeSet);//TreeSet=[gag, haha, xi]
    }
}

2、添加元素按照字符串的大小来排序，使用TreeSet提供的一个构造器，可以传入一个比较器（传入一个匿名内部类），指定排序规则

java.util.TreeSet treeSet = new java.util.TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        //比较规则,o1对象比较与o2对象
        return ((String)o1).compareTo((String)o2);//从大到小
    }
    输出：TreeSet=[gag, haha, xi]
});

进入字符串的compareTo，就是一个比较每一个字符的ascii码

• 将一个匿名内部类传给TreeSet

  

• 再进入TreeMap，将构造器赋给treeMap的属性

  

• 退出，再进入add方法，调用的是TreeSet的put方法，e代表的是具体的一个key，PRESENT是一个静态的对象

  

• 进入put方法，变成TreeMap的put方法，第一次添加元素时，也调用了compare方法，因为第一次添加，没有元素就比较key和key，所以等于0，但是对添加元素key值和value值没有影响，作用就是检测是否为空，为空则会抛出一个空指针异常

  

• 添加第一个元素完成后，添加第二个元素，进入put方法，定义了一个cpr，让comparator指向他，然后判断这个构造器是否为空，其中cpr.compare就是外部写的方法，比较字符串的ASCII码值，相当于动态绑定到外面写的匿名内部类中的compare；cmp等于0，两个对象相等，就不会添加；cmp小于0，t指向向左移

  

• dugger到cmp = cpr.compare(key,t,key),然后step into就进入到

  

• 创建一个新的entry，比较每个元素的ascii值，大于第一个元素，确定第一个元素的left指向这个新的元素，返回null，添加成功；小于第第一个元素，确定第一个元素的right指向新的元素，就是放在符节点的右边

  

• 添加成功

  

TreeSet去重机制

如果传入一个Comparator匿名对象，就使用实现的compare去重，如果方法返回0（cmp=0），就是相同的元素或者数据，就不添加；如果没有传入一个Comparator匿名对象，则以添加的对象实现的Comparable接口的compareTo去重

实例演示：

treeSet.add(new Person());
class Person{}

class Person implements Comparable{
    @Override
    public int compareTo(Object o) {
        return 0;
    }
}

会报一个 ClassCastException的异常，因为TreeSet（）构造器没有传入Comparator接口的匿名内部类。所以底层（Comparable<? super K> k = (Comparable<? super K>) Key ）会Person转换成Comparable类型，但是Person没有实现Comparable接口

Map

接口实现类的特点

• Map与Collection并列存在，用于保存具有映射关系的数据：key-value（双列），Collection是单列

• Map中的key与value可以是任何引用类型的数据，会封装到HashMa$Node对象中

• Map中的key不可重复，原因和HashSet一样，但是value可以重复

• Map中key可以为null，value也可以为null，但是当单独的key为null，只能有一个，而value为null，可以有多个

• 常用String类作为Map的key

• key和value之间存在单向一对一关系，就是可以通过指定的key能找到对应的value

• 实例演示

  @SuppressWarnings({"all"})
  public class Map {
      public static void main(String[] args) {
          java.util.Map map = new HashMap();
          map.put("num1","4325");
          map.put("num2","4456");
          map.put("num1","4444");//当有相同的key，相等于替换
          map.put("num3","4325");//Map={num1=4444, num3=4325, num2=4456}
  
          map.put(null,null);
          map.put("num4",null);
          map.put("num5",null);
          map.put("num6",null);//Map={null=null, num6=null, num1=4444, num5=null, num4=null, num3=4325, num2=4456}
          map.put(1,"jiji");
          map.put(new Object(),"zhangsan");//Map={null=null, 1=jiji, num6=null, java.lang.Object@2f0e140b=zhangsan, num1=4444, num5=null, num4=null, num3=4325, num2=4456}
          System.out.println("Map="+map);
          System.out.println(map.get("num3"));//4325
  
      }
  }
  

• Map存放数据的key-value中，一对k-v是放在HashMap$Node中，因为Node实现Entry接口

  • k-v最后是HashMap$Node，node = newNode(Hash,key,value,null)

  • 为了方便程序员的遍历，还会创建EntrySet集合，该集合存放元素类型是Entry而一个Entry对象就有k-v（EntrySet<Entry<k,v>>）

    

  • entrySet中，定义的类型是Map.Entry，但是实际上存放的还是HashMap$Node

    

  • 当把HashMap$Node对象存放到entrySet就方便我们的遍历，因为Map.Entry提供了重要的方法

    • K getKey()
    • V getValue()

常用方法

• put：添加单个元素
• remove：根据指定的key移除一个元素，并将元素返回
• remove（重载）：根据指定的key-value删除一个元素
• get：根据指定的key获取一个元素
• containsKey：查看集合中是否包含该键
• keySet：将所有键存储到一个set集合中
• entrySet：将所有键值对存储到set集合中
• values：获取所有值

Map接口的遍历方法

• 遍历

  • 为什么Map没有自己的Iterator遍历器

    • Collection接口继承了Iterable接口，因此可以用迭代器遍历

      

    • [参考文章][https://qa.1r1g.com/sf/ask/1359565581/]

    • 可能是因为Collection只有一种内容需要遍历，就是值，而Map接口可能有三种选择内容去遍历，分别是键、值、键值对，他不知道实际根据那种情况去遍历，因此取消了遍历，而是通过三种内容自己的iterable去遍历，这样就可以根据不同的情况来选择方法来遍历，因此Map集合没有继承Iterable

  • 遍历所有key：调用keySey方法，获取到keySet的Set集合，在遍历set集合

    • 增强for

    Set keySet = map.keySet();
    for (Object key : keySet) {
        System.out.println(key + "-" + map.get(key));
    }
    /**
    jia-renmen
    hello-world
    ni-hao
    */
    

    • 迭代器遍历

    Iterator iterator = keySet.iterator();
    while (iterator.hasNext()){
        Object key = iterator.next();
        System.out.println(key + "-" + map.get(key));
    }
    

  • 遍历value：先调用values方法，获取一个value的Collection集合，再遍历Collection集合

    • 增强for

      Collection values = map.values();
      for (Object value : values) {
          System.out.println(value);
      }
      

    • 迭代器

      Iterator iterator1 = values.iterator();
      while (iterator1.hasNext()){
          Object value = iterator1.next();
          System.out.println(value);
      }
      

  • 遍历键值对：先调用entrySet方法，获取到一个entry的Set集合，再遍历Set集合

    • 增强for

      Set entrySet = map.entrySet();
      for (Object entry : entrySet) {
          Map.Entry m = (Map.Entry) entry;
          System.out.println(m.getKey() + "-" + m.getValue());
      }
      输出：
      jia-renmen
      hello-world
      ni-hao
      

    • 迭代器

      Iterator iterator2 = entrySet.iterator();
      while (iterator2.hasNext()){
          Object entry = iterator2.next();
          Map.Entry m = (Map.Entry) entry;
          System.out.println(m.getKey() + "-" + m.getValue());
      }
      

• 遍历详解

Map接口常用实现类

HashMap

1、HashMap是以key-value对的方式来存储数据（HashMap$Node类型）

2、key不能重复，但是值可以重复，允许使用null键和null值

3、如果添加相同的key，则会覆盖原来的key-val

4、与HashSet一样，不会保证映射的顺序，因为底层是以hash表的方式来存储的

5、没有实现同步，所以线程不是安全的，方法没有做同步互斥的操作，没有synchronizd

HashMap是Map实现类中使用频率最高的

• 第一次执行put方法

  1. 插入元素

     

  2. 进入putVal，第一次添加，table为null，执行resize方法扩容

     

  3. resize方法找那个，将容量和阈值初始化为默认的容量和阈值，并创建一个新的table，将原来的table指向他

     

  4. 根据hash经过特殊的运算（key.hashCode()^(h >>> 16)）得到在链表数组的索引位置，判断该是否有元素，因为是第一次插入元素，所以直接插入

     

  5. 判断大小是否大于扩容的阈值（现在是12）

     

  6. putVal返回null，添加成功

     

• put一个key相同，value不相同

  1. 添加新元素，与之前元素key值相同，而value值不相同

     

  2. 进入putVal方法，table不为null，不用扩容

     

  3. key相同，将e指向p节点

     

  4. e不为null，oldvalue保存旧的value值，节点的value替换为新的value

     

  5. table数组链表中元素的value替换成功

     

• 树化的条件：一条链表的元素个数超过THEEIFY_THRESHOLD（默认为8）；table的大小大于等于MIN_TREEIFY_CAPACITY（默认为64），满足两个条件就会树化

• HashMap在hashSet中已经分析完了，直接查看collection中的HashSet是如何进行操作的

• 剪枝：树化后，在之后的操作中删除节点到一定量，重新转换成链表

为什么树化的标准是8个

如果hashcode的分布离散良好的话，那么红黑树是很少使用的，因为各个值都均匀分布，很少出现链表很长的状态。在理想的状态下，链表长度符合泊松分布，各个长度的命中概率依次减低，而当长度为8时，概率已经很小了，hashMap的红黑树转换几乎不会发生

HashTable

基本介绍

• 存放的元素是键值对：k-v
• HashTable的键和值都不能为null，添加时键和值为null，出现异常
• HashTable使用方法基本上和HasMap一样
• hashTable是线程安全的，HashMap是不安全的

演示：

@SuppressWarnings({"all"})
public class HashTable {
    public static void main(String[] args) {
        Hashtable hashtable = new Hashtable();
        hashtable.put("haha",100);
        hashtable.put("haha",100);
        hashtable.put("haha",1201);//替换
//        hashtable.put(null,1000);//异常
//        hashtable.put("jiji",null);//异常
//        hashtable.put(null,null);
        System.out.println(hashtable);//{haha=100}
    }
}

底层

1、底层是数组Hashtable$Entry[]（Hashtable的内部类entry），初始化大小是11，临界值threshold 8 = 11*0.75

2、第二次扩容大小是23，临界值threshold为17

无参构造

1、执行无参构造

2、调用了一个带参构造器，将11和0.75作为参数传了过去

3、进入带参构造器，table数组会直接初始化为一个长度为11的Entry数组，并且threshold确定为初始化容量乘以扩容因子，也就是11*0.75=8

4、Entry实现了map中的entry接口，其中的参数hash，key，value，next属性与Node一样，所以将Entry理解成Node

扩容

1、不能添加value值为null的原因

2、判断count是否达到了阈值，也就是在插入第九个元素时，count才会达到阈值（HashTable与HashMap执行扩容的时机不同，hashMap是插入后，HashTable是要插入时）

3、进入rehash方法，新的容量为23 = 11*2+1

• 根据新容量创建一个Entry新数组

• 让阈值等于新容量乘以扩容因子，并让table指向newMap

  

• 将原来table的内容全部转移到新的newMap数组中

  

• 将addEntry中的变量都做出改变，需要让tab、hash、index重新计算一下

  

4、然后执行头插法

5、扩容成功

Properties

基本介绍

1、Properties类继承Hashtable类，也是使用一种键值对的形式来保存用户数据，key和value不能为空，相同的key时value被替换

2、Properties使用特点和Hashtable类似

3、Properties还可以用于xxx.properties文件中，加载数据到properties类对象中，并进行读取和修改（数据库外部文件db.properties保存用户名和密码，数据库启动时读取文件配置）

4、xxx.properties文件通常作为配置文件

常用方法

• get：通过key值获取对应的value
• remove：通过key值移除元素
• put：有相同的key替换value值

TreeMap

1、使用默认的构造器，创建TreeMap，排列是无序的

@SuppressWarnings({"all"})
public class TreeMap {
    public static void main(String[] args) {
        java.util.TreeMap treeMap = new java.util.TreeMap();
        treeMap.put("aaa",456);
        treeMap.put("aaa",123);
        treeMap.put("huhu",111);
        treeMap.put("ccc",222);
        System.out.println("treeMap="+treeMap);//treeMap={aaa=123, ccc=222, huhu=111}
    }
}

2、有参构造器，传入一个实现了Comparator接口的匿名内部类，传给TreeMap的comparator

• 第一次put添加中，新建一个entry，并将key和value传入，他的底层是TreeMap$entry，并将其挂在root上，然后返回null，添加成功

  

• 第二次put添加，拿到比较器，然后做一个判断（ascii码），遍历所有的key，给当前的key寻找位置，如果第一个元素小的话，挂在左边；如果大的话，挂在右边；如果相等说明key相等，将原来旧的value替换成新的value值

  

• 新建一个entry对象，并将key值、value和parent传入，如果小于parent的ASCII码，parent右节点指向这个对象；如果大于parent的ASCII码，parent的左节点则指向这个对象

  

如果选择集合实现类

选择集合实现类，主要取决与业务操作特点，然后根据集合实现类特性进行选择：

1、先判断存储类型：单列（一组对象）或者双列（一组键值对）

2、一组对象（单列）：

• 允许重复：使用List
  • 增删多：LinkedList，底层维护了一个双向链表
  • 改查多：ArrayList，底层维护了一个Object类型的可变数组
• 不允许重复：使用Set
  • 无序：使用HashSet，底层维护了一个哈希表，就是数组+链表+红黑树
  • 排序：TreeSet
  • 插入顺序和取出顺序一致：LinkedHashSet，底层是LinkedHashMap，而LinkedHashMap底层是HashMap（数组+双向链表）

3、一组键值对（双列）：

• 键无序：HashMap，jdk7时底层是数组+链表，jdk8时底层是数组+链表+红黑树
• 键排序：TreeMap
• 键插入和取出顺序一致：LinkedHashMap
• 读取文件：Properties

Collections工具类

介绍

1、Collectons是一个操作Set、List和Map等集合的工具类

2、Collections提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

方法（全部都是static方法）

• reverse(List)：反转List中元素的顺序
• shuffle(List)：对List中元素进行随机排序
• sort(List)：根据元素的自然顺序对指定的List集合元素进行升序排序
• sort(List, Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序
• swap(List, int, int)：指定List集合中元素的索引为i和j的元素进行交换

实例演示：

@SuppressWarnings({"all"})
public class Collections_ {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("xixi");
        list.add("gaga");
        list.add("haha");
        list.add("heihei");

        Collections.reverse(list);
        System.out.println("List="+list);

        Collections.shuffle(list);//打乱顺序，可以用于抽奖的游戏打乱顺序
        System.out.println("List="+list);

        Collections.sort(list);
        System.out.println("List="+list);//自然排序就是按照字符串的大小来排序

        Collections.sort(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String)o2);//按照字符串的大小来排序，就是按照ascii码来排序
            }
        });
        System.out.println("List="+list);

        Collections.swap(list,0,1);
        System.out.println("List="+list);


    }
}
/**
List=[heihei, haha, gaga, xixi]
List=[heihei, haha, xixi, gaga]
List=[gaga, haha, heihei, xixi]
List=[gaga, haha, heihei, xixi]
List=[haha, gaga, heihei, xixi]
*/

• Object max(Collection)：根据元素的自然顺序，返回集合中的最大元素
• Object max(Collection, comparator)：根据Comparator指定的顺序，返回集合中指定的最大元素
• Object min(Collection)：根据元素的自然顺序，返回集合中的最小元素
• Object min(Collection, comparator)：根据Comparator指定的顺序，返回集合中指定的最小元素
• int frequency(Collection, Object)：返回指定集合中指定元素出现次数
• void copy(List dest, List src)：将src中内容复制打击dest中
• boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换List对象中所有旧的值

实例演示：

Comparable max = Collections.max(list);
System.out.println("最大值="+max);

Object maxObject = Collections.max(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String) o1).length() - ((String) o2).length();
    }
});
System.out.println("长度最大的对象="+maxObject);

Comparable min = Collections.min(list);
System.out.println("最小值="+min);

int heihei = Collections.frequency(list, "heihei");
System.out.println("heihei出现的次数="+heihei);

ArrayList dest = new ArrayList();//dest和list大小一致
for (int i = 0; i < list.size(); i++) {
    dest.add("");
}
Collections.copy(dest,list);
System.out.println("dest="+dest);

Collections.replaceAll(list,"heihei","huhu");
System.out.println("替换后List="+list);

思考题

@SuppressWarnings({"all"})
public class HashSetWork {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        People people1 = new People(101, "jiji");
        People people2 = new People(102, "haha");
        hashSet.add(people1);
        hashSet.add(people2);
        people1.name = "xixi";
        hashSet.remove(people1);
        System.out.println(hashSet);
        hashSet.add(new People(101,"xixi"));
        System.out.println(hashSet);
        hashSet.add(new People(101,"jiji"));
        System.out.println(hashSet);
    }
}
class People {
    public int id;
    public String name;

    public People(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof People)) return false;

        People people = (People) o;

        if (id != people.id) return false;
        return name != null ? name.equals(people.name) : people.name == null;
    }

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

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

结果：

分析

1、hashSet.remove(people1)并没有删除成功，删除时是根据people1的101和“xixi”来计算的，计算后得到的位置可能不在原来people1时的位置上，删除时位置可能是空的，所以删除失败

2、hashSet.add(new People(101,”xixi”))成功是因为根据101和“xixi”得到的存储位置与一开始根据101和“jiji”得到的位置是不同的，即使后来将其value值改为“xixi”也是在该位置进行改变的，并没有重新换位置，所以能够成功

• 一开始根据101和“jiji”得到的索引位置，和修改为“xixi”的索引位置是一致的

  

• 再次添加根据101和“xixi”，是跟修改为“xixi”是不一样的

  

3、hashSet.add(new People(101,”jiji”))因为key和value是一样的，所以得到的索引位置是和第一次添加数据的索引是一样的，但是第一次添加的数据的value已经修改了，所以两个并不相同，但是索引位置是一样的，所以可以挂在第一次添加数据的后面，所以添加成功

Collection和Conlletions

collection是一个接口，提供了对集合对象进行基本操作的通用接口方法。collection接口在Java类库中有很多具体的实现。意义是为各种具体的集合提供了最大化的统一操作方式

collections是一个包装类，包含各种有关集合操作的静态多态方法，不能实例化，就像一个工具类

哈希冲突

哈希

使用哈希算法把任意长度的二进制映射为固定长度的较小的二进制数，这个较小的二进制值就是哈希值

哈希冲突

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，叫做碰撞（哈希碰撞）

怎么解决

• 链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位
• 开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位

HashMap与HashTable有什么区别

1、线程安全：HashMap是非线程安全的，而HashTable是线程安全的，内部的方法都经过synchronized修饰；保证线程安全使用concurrentHashMap

2、是否允许null key 、null value：HashMap中，null可以作为键，有且只有一个，可以一个或多个键对应的值为null；HashTable是不被允许的

3、初始容量大小和每次扩充容量大小不同：

• 创建时如果不指定容量初始值，HashTable默认的大小为11，之后每次扩充，容量变为原来的2n+1；HashMap默认的初始化大小为16，每次扩充，容量变为原来的2倍
• 创建时如果指定容量初始值，HashTable会直接给定大小；而HashMap会将起扩充为2的幂次方大小

4、底层数据结构：jdk1.8以后的HashMap在解决hash冲突时有了较大的变化，当链表长度大于阈值（默认为8）,将链表转化为红黑树，减少检索时间；而HashTable没有