Java-Collection,集合框架的数据结构,原理,使用,呕心沥血之作

志之难也，不在胜人，在自胜也

集合与数组的区别

相同点：

都是容器,可以存储多个数据

不同点：

数组的长度是不可变的,集合的长度是可变的

数组可以存基本数据类型和引用数据类型

集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类

集合体系结构

基本数据结构

栈

  • 特点：先进后出，后进先出

    队列

  • 特点：先进先出，后进后出

    数组

  • 特点：查询快，增删慢

    链表

  • 链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址

  • 查询慢，增删快

    树

  • 度：没一个节点的子节点数量

  • 二叉树中，任意节点的度<=2

  • 树高：树的总层数

  • 根节点：最顶层的节点

二叉树的遍历方式

前序遍历：根左右

前序遍历
中序遍历：左根右

中序遍历
后序遍历：左右根

后序遍历
层序遍历：

层序遍历

二叉查找树

二叉查找树
存数规则

弊端：但数据有序、单一，会造成树偏移

平衡二叉树

平衡二叉树判断

平衡二叉树保持平衡机制(旋转)

保持平衡机制

左旋

自定义链式左旋：左旋后的节点即将作为根节点且不全有左右字数

1. 首先找到不平衡的节点，也就是要确定支点

寻找不平衡的点、支点
2. 进行左旋

左旋操作
3. 左旋步骤

左旋步骤
4. 左旋后

完成左旋

自定义叉式左旋：左旋后即将作为根节点且已经有了两个左右子节点

1. 寻找支点进行左旋，7是支点，且左旋的部分涉及到分叉


2. 左旋步骤，先把即将要变为根节点的多余的节点当做没有，按照自定义链式左旋，左旋后，


3. 再将刚才多余的节点，链接到旧根节点

右旋
左旋和右旋的原理一样，只是旋转方向不同
需要旋转的情况
左左——整体右旋

左右——局部左旋整体右旋


右右——整体左旋


右左——局部右旋整体左旋


红黑树

  • 是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
  • 1972年出现，被称为平衡二叉B树
  • 是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
  • 每一个节点可以是红或者黑，红黑树不是高度平衡的，他的平衡是通过”红黑规则”实现


红黑规则
  1. 每一个节点或是红色的、或是黑色的
  2. 根节点必须是黑色
  3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点Nil是黑色的
  4. 如果某一个节点是红色的，那么它的子节点必须是黑色(不能出现两个红色相连的情况)
  5. 对每一个节点，从该节点到其所有后叶代节点的简单路径上，均包含相同数目的黑色节点(路径上黑色节点的数量是一样的)
添加节点的规则

单列集合：一次添加一个数据


List系列集合：

  • 有序：存入的顺序和取出来的顺序是一致的。
  • 可重复：集合中的元素可以重复。
  • 有索引：可以按照根据索引取出对应的元素。

set系列集合：

  • 无序：存入的顺序和取出的顺序不一定是一致的。
  • 不重复：集合中的元素是不可以重复。
  • 无索引：不能通过索引获取每一个元素

使用场景

Collection集合

概述
  • 是单列集合的祖宗接口，它的功能是全部单列集合可以继承使用的
  • 是单例集合的顶层接口,它表示一组对象,这些对象也称为Collection的元素
  • JDK 不提供此接口的任何直接实现.它提供更具体的子接口(如Set和List)实现
创建Collection集合的对象
  • 多态的方式
  • 具体的实现类ArrayList
1
Collection<String> coll = new ArrayList<>();
Collection集合常用方法
方法名 说明
boolean add(E e) 添加元素
boolean remove(Object o) 从集合中移除指定的元素
boolean removeIf(Object o) 根据条件进行移除
void   clear() 清空集合中的元素
boolean contains(Object o) 判断集合中是否存在指定的元素
boolean isEmpty() 判断集合是否为空
int   size() 集合的长度，也就是集合中元素的个数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
Collection<String> coll = new ArrayList<>();

// 1.添加元素
// 细节1：往List集合中添加元素，方法永远返回true，List集合允许元素重复
// 细节2：往Set集合中添加元素，元素不存在、添加成功返回true，元素存在，添加失败返回false
coll.add("aaa");

// 2.清空集合中的元素
coll.clear();

// 3.删除（传递对象）
// 因为Collection集合是List、Set集合的接口，Collection接口里面定义的是两者共性的方法，List
// 有索引、Set无索引，所以不能通过索引删除
// 元素不存在、删除失败
coll.remove("aaa");

// 4.判断元素是否包含
boolean result = coll.contains("aaa");
System.out.println(result);
// 底层源码
 public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * {@code Objects.equals(o, get(i))},
     * or -1 if there is no such index.
     */
    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {  //这里的equals方法取决于传入的是什么类型，调用的是哪个类型的equals方法
                    return i;
                }
            }
        }
        return -1;
    }
/*
如果存的是自定义对象，没有重写equals方法，默认使用的是Object类中的equals是方法，进行地址值判断
*/
/*
原理：contains()方法调用了indexOf()方法，利用indexOf的返回值大于>=0即可证明，元素存在
    indexOf()调用了indexOfRange()，其原理是循环遍历每一个元素，找到则返回下标，否则返回-1，
    其中单独进行了传空判断。
*/
// 5.判断集合是否为空
boolean result = coll.isEmpty();
System.out.printlf(result);

//6.获取集合的长度
int size = coll.size();
System.out.println(size);
Collection集合的遍历方式
集合的遍历方式为通用遍历方式，即：单列、双列集合均可以使用
迭代器遍历：不依赖索引、创建指针、移动指针获取元素
迭代器Java中的类是Iterator,集合的专用遍历方式

Iterator iterator(): 返回此集合中元素的迭代器,通过集合对象的iterator()方法得到

  • Iterator中的常用方法
    • boolean hasNext(): 判断当前位置是否有元素可以被取出
    • E next(): 获取当前位置的元素,将迭代器对象移向下一个索引位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class IteratorDemo1 {
     public static void main(String[] args) {
         //创建集合对象
         Collection<String> c = new ArrayList<>();
 
         //添加元素
         c.add("hello");
         c.add("world");
         c.add("java");
         c.add("javaee");
 
         //Iterator<E> iterator()：返回此集合中元素的迭代器，通过集合的iterator()方法得到
         // 迭代器好比一个箭头，默认指向0索引处
         // 初始化迭代器后，光标(指针)初始值为-1
         Iterator<String> it = c.iterator(); //集合调用iterator的方法，方法会返回迭代器的对象
 
         //用while循环改进元素的判断和获取
         while (it.hasNext()) {	// 判断是否有元素取出
             String s = it.next(); // 获取元素并且移动指针
             System.out.println(s);
         }
     }
 }

细节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class A04_CollectionDemo4 {
    public static void main(String[] args) {
      /*
        迭代器的细节注意点：
            1.报错NoSuchElementException
            2.迭代器遍历完毕，指针不会复位
            3.循环中只能用一次next方法
            4.迭代器遍历时，不能用集合的方法进行增加或者删除
                会出现并发修改异常的错误 
                如果我实在要删除：那么可以用迭代器提供的remove方法进行删除。
                如果我要添加，暂时没有办法。(只是暂时)
       */

        //1.创建集合并添加元素
        Collection<String> coll = new ArrayList<>();
        coll.add("aaa");
        coll.add("bbb");
        coll.add("ccc");
        coll.add("ddd");

        //2.获取迭代器对象
        //迭代器就好比是一个箭头，默认指向集合的0索引处
        Iterator<String> it = coll.iterator();
        //3.利用循环不断的去获取集合中的每一个元素
        while(it.hasNext()){
            //4.next方法的两件事情：获取元素并移动指针
            String str = it.next();
            System.out.println(str);
        }

        //当上面循环结束之后，迭代器的指针已经指向了最后没有元素的位置
        //System.out.println(it.next());//NoSuchElementException

        //迭代器遍历完毕，指针不会复位
        System.out.println(it.hasNext());

        //如果我们要继续第二次遍历集合，只能再次获取一个新的迭代器对象
        Iterator<String> it2 = coll.iterator();
        while(it2.hasNext()){
            String str = it2.next();
            System.out.println(str);
        }
    }
}

迭代器中的删除方法

void remove(): 删除迭代器对象当前指向的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class IteratorDemo2 {
     public static void main(String[] args) {
         ArrayList<String> list = new ArrayList<>();
         list.add("a");
         list.add("b");
         list.add("b");
         list.add("c");
         list.add("d");
 
         Iterator<String> it = list.iterator();
         while(it.hasNext()){
             String s = it.next();
             if("b".equals(s)){
                 //指向谁,那么此时就删除谁.
                 it.remove();
             }
         }
         System.out.println(list);
     }
 }
增强for遍历
  • 它是JDK5之后出现的,其内部原理是一个Iterator迭代器
  • 实现Iterable接口的类才可以使用迭代器和增强for
  • 简化数组和Collection集合的遍历(所有的单列集合才能用增强for)

格式
for(集合/数组中元素的数据类型 变量名 : 集合/数组名) {
// 已经将当前遍历到的元素封装到变量中了,直接使用变量即可
}

快速生成增强for代码：

集合名字.for 回车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class MyCollectonDemo1 {
      public static void main(String[] args) {
          ArrayList<String> list =  new ArrayList<>();
          list.add("a");
          list.add("b");
          list.add("c");
          list.add("d");
          list.add("e");
          list.add("f");
  
          //1,数据类型一定是集合或者数组中元素的类型
          //2,str仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素
          //3,list就是要遍历的集合或者数组
          //4.修改增强for中的变量，不会改变集合中的数据
          for(String str : list){
              System.out.println(str);
          }
      }
  }
forEach遍历方式
JDK8开始的Lambda表达式，提供了一种更简单、更直接的遍历集合的方式 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class A07_CollectionDemo7 {
    public static void main(String[] args) {
       /* 
        lambda表达式遍历：
                default void forEach(Consumer<? super T> action):
        */

        //1.创建集合并添加元素
        Collection<String> coll = new ArrayList<>();
        coll.add("zhangsan");
        coll.add("lisi");
        coll.add("wangwu");
        //2.利用匿名内部类的形式
        //底层原理：
        //其实也会自己遍历集合，依次得到每一个元素
        //把得到的每一个元素，传递给下面的accept方法
        //s依次表示集合中的每一个数据
       /* coll.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        });*/

        //lambda表达式
        coll.forEach(s -> System.out.println(s));
    }
}

List集合

  • Collection的方法List都继承了
  • List集合因为有索引，所以有很多索引操作的方法
List集合特有的方法
方法名 描述
void add(int index,E   element) 在此集合中的指定位置插入指定的元素
E remove(int   index) 删除指定索引处的元素，返回被删除的元素
E set(int index,E   element) 修改指定索引处的元素，返回被修改的元素
E get(int   index) 返回指定索引处的元素 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class MyListDemo {
      public static void main(String[] args) {
          // 1.创建一个集合
          List<String> list = new ArrayList<>();
          // 2.添加元素
          list.add("aaa");
          list.add("bbb");
          list.add("ccc");
          //method1(list);
          //method2(list);
          //method3(list);
          //method4(list);
      }
  
      private static void method4(List<String> list) {
          //        E get(int index)		返回指定索引处的元素
          String s = list.get(0);
          System.out.println(s);
      }
  
      private static void method3(List<String> list) {
          //        E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
          //被替换的那个元素,在集合中就不存在了.
          String result = list.set(0, "qqq");
          System.out.println(result);
          System.out.println(list);
      }
  
      private static void method2(List<String> list) {
          //        E remove(int index)		删除指定索引处的元素，返回被删除的元素
          //在List集合中有两个删除的方法
          //第一个 删除指定的元素,返回值表示当前元素是否删除成功
          //第二个 删除指定索引的元素,返回值表示实际删除的元素
          /*
          list.add(1);
          list.add(2);
          list.add(3);

          list.remove(1);

          remove(object o)
          remove(int index)
          
          删除1这个元素 ，是删除的1索引这个元素，还是删除的是1这个元素？
              1索引这个元素
            why？
                因为在调用方法的时候如果出现方法重载的现象
                优先调用，实参和形参类型一致的方法
            如果想要删除1，这个元素，需要传递一个对象，自动装箱即可
                Integer i = Integer.valueOf(1);
                list.remove(i);
            即可删除元素为1这个对象
                  
          */
          String s = list.remove(0);
          System.out.println(s);
          System.out.println(list);
      }
  
      private static void method1(List<String> list) {
          //        void add(int index,E element)	在此集合中的指定位置插入指定的元素
          //原来位置上的元素依次往后挪一个索引.
          list.add(0,"qqq");
          System.out.println(list);
      }
  }
List集合的遍历方式
  1. 迭代器
  2. 列表迭代器
  3. 增强for
  4. Lambda表达式
  5. 普通for循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//创建集合并添加元素
List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

//1.迭代器
/*Iterator<String> it = list.iterator();
     while(it.hasNext()){
        String str = it.next();
        System.out.println(str);
}*/


//2.增强for
//下面的变量s，其实就是一个第三方的变量而已。
//在循环的过程中，依次表示集合中的每一个元素
/* for (String s : list) {
       System.out.println(s);
   }*/

//3.Lambda表达式
//forEach方法的底层其实就是一个循环遍历，依次得到集合中的每一个元素
//并把每一个元素传递给下面的accept方法
//accept方法的形参s，依次表示集合中的每一个元素
//list.forEach(s->System.out.println(s) );


//4.普通for循环
//size方法跟get方法还有循环结合的方式，利用索引获取到集合中的每一个元素
/*for (int i = 0; i < list.size(); i++) {
            //i:依次表示集合中的每一个索引
            String s = list.get(i);
            System.out.println(s);
        }*/

// 5.列表迭代器(独有)
// 是之前迭代器的子接口
//获取一个列表迭代器的对象，里面的指针默认也是指向0索引的

//额外添加了一个方法：在遍历的过程中，可以添加元素
/*
其中有两个方法和hasNext、next方法相反
hasPrevious()
Previous() 将指针从后往前移动
*/
ListIterator<String> it = list.listIterator();
while(it.hasNext()){
    String str = it.next();
    if("bbb".equals(str)){
        //qqq
        it.add("qqq"); //使用迭代器中的方法去添加
    }
}
/*
其中有两个方法和hasNext、next方法相反，

*/
System.out.println(list);
ArrayList集合
底层原理
  1. 空参构造创建ArrayList对象的时候，他在底层先创建了一个默认长度为0的数组。
    数组名字：elementDate 定义变量size，记录数组长度
  2. 当添加第一个元素的时候，底层会创建一个新的长度为10的数组，size++

size这个变量有两层含义：

①：元素的个数，也就是集合的长度

②：下一个元素的存入位置
  1. 存满时，会创建新的数组，长度为原数组的1.5被，将原数组的数据拷贝在新数组中
  2. 如果一次添加多个元素，1.5倍还放不下，则创建新数组，长度以实际为准

第一次添加一个元素时：

空参创建新ArrayList并添加一个元素，第一次添加数据
当添加元素需要扩容时：

添加的元素超出了当前数组的上限，第十一次添加数据

LinkedList集合
底层原理
  • 底层数据结构是双链表、查询慢、增删快
  • 如果操作的是首尾元素，速度也是极快的，LinkedList本身多了许多直接操作首尾元素的API
1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
        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;
        }
    }
LinkedList第一次添加元素

创建LinkedList对象，并添加第一个元素
过程：

  1. 创建LinkedList对象，会产生一个堆内存，其中的两个结点

Node first：用于存储目前链表中，第一个结点的地址值
Node last：用于存储目前链表中，最后一个结点的地址值

  1. 调用LinkedList对象中的add方法，add方法中会调用linkLast方法(拼接在后面)
  2. 在linkLast方法中，先用变量l来获取目前链表中最后一个结点的地址值last(因为链表刚创建、所以此处last为空)
  3. 创建一个新结点，按照固定传参new
    Node<>(l,e,null),将链表最后一个结点的地址值l放入新结点的前驱(此时，头部也为空，因为是第一个结点，没有前结点)。
  4. 将链表最后一个结点的地址值last进行更新，更新为新结点的地址值
  5. 判断l是否为空，也就是判断新节点的前驱是否为空，也就是判断该结点是不是链表中的第一个结点，此处是，将链表中的第一个结点的地址first更新为这个新结点的地址值
  6. 此时第一次创建的新结点
    既是链表的第一个结点(first地址值)，也是链表的最后一个结点(last地址值)
  7. 完成添加第一个结点
LinkedList第n次添加元素(n>=2)


过程：

  1. 调用LinkedList对象中的add方法，add方法中会调用linkLast方法(拼接在后面）
  2. 在LinkedList方法中，先用变量l来获取目前链表中最后一个结点的地址值last，准备用于插入到新节点的前驱
  3. 创建一个新结点 new Node<>(l, e,
    null)，然后将刚才取出的链表最后一个结点的地址值last、元素e填入新结点中
  4. 已有新的结点准备链入，此时更新链表最后一个结点的地址值last为新结点的地址值
  5. 此时，链表中最后一个结点l链接新的结点，也就是最后一个结点的后继链接新结点的地址值，需注意：此处为l，因为last已更新为最新结点的地址值，而l是存放链表最后一个结点的地址值，l.next=newNode，将链表上一个结点的后继更新为新结点的地址值
  6. 完成链入

迭代器

底层原理、并发修改异常原理
迭代器底层源码、并发修改异常原理

泛型深入

  • 泛型是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，它提供了编译时类型安全检测机制
  • 泛型的格式：<数据类型>
  • 泛型只能支持引用数据类型，基本数据类型的包装类，指定泛型的类型后，可以传入该类类型和其子类类型
  • 泛型的好处：1.把运行时期的问题提前到了编译期间 2.避免了强制类型转换

Java中的泛型是伪泛型，当元素存入集合中，底层还是会当做Object类来处理，当获取这些元素的时候，集合底层自动进行了强转，转为泛型对应的数据类型。称为泛型的擦除。

泛型定义的范围
泛型可以定义在类后面、方法上面、接口后面
泛型类
使用场景：当一个类中，某个变量的基本数据类型不确定的时候，就可以定义带有泛型的类

泛型类格式
自定义泛型类示例

泛型方法

泛型方法使用场景
泛型方法格式
泛型方法示例
其中E…e为可变参数，可以传递任意个参数，使用循环遍历参数。

泛型接口

泛型接口的格式、使用场景

泛型的继承和通配符
泛型不具备继承性，但数据具备继承性

创建了Ye、Fu、Zi有继承结构的类，实例化类后，传递实例化类参数到泛型方法中，只有类型相同的才可以传递
采用通配符就可以限制传递参数

泛型通配符细节

Set集合

  • 无序：存取顺序不一致
  • 不重复：可以去重
  • 无索引：没有带索引的方法，不能使用普通for循环遍历，也不能通过索引来获取元素

Set集合的实现类

  • HashSet：无序、不重复、无索引
  • LinkedHashSet：有序、不重复、无索引
  • TreeSet：可排序、不重复、无索引

Set接口中的方法基本上与Collection的API一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class MySet1 {
    public static void main(String[] args) {
      	//创建集合对象
        Set<String> set = new TreeSet<>();
      	//添加元素
        set.add("ccc"); //true
        set.add("aaa"); //true
        set.add("aaa"); //false
        set.add("bbb"); //true

//        for (int i = 0; i < set.size(); i++) {
//            //Set集合是没有索引的，所以不能使用通过索引获取元素的方法
//        }
      
      	//遍历集合
        // 迭代器遍历
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("-----------------------------------");
        // 增强for遍历
        for (String s : set) {
            System.out.println(s);
        }
        // Lambda表达式遍历
        s.forEach(str -> System.out.println(str));
    }
}
HashSet集合
  • 底层数据结构是哈希表
  • 存取无序
  • 不可以存储重复元素
  • 没有索引,不能使用普通for循环遍历
哈希表
  • JDK1.8以前
    数组 + 链表
  • JDK1.8以后
    • 节点个数少于等于8个
      数组 + 链表
    • 节点个数多于8个
      数组 + 红黑树
哈希值
  • 是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
  • 该方法定义在Object类中，所有对象都可以调用，默认使用地址值计算
  • 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值

对象的哈希值的特点

  • 如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
  • 如果已经重写hashCode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
  • 在小部分情况下，不同属性值或者不同的地址值计算出来的哈希值也有可能一样(哈希碰撞)
HashSet JDK8以前的底层原理
  1. 创建一个默认长度16，默认加载因子为0.75的数组，数组名table



2. 根据元素的哈希值跟数组的长度进行计算，算出应存入的位置


3. 判断当前位置是否为null，如果是null直接存入
4. 如果当前计算的位置不是null，表示有元素，则调用equals方法去比较属性值
5. 一样：不存 不一样：存入数组

JDK8以前：新元素存入数组，老元素挂在新元素的下面

JDk8以后：新元素直接挂在老元素的下面

如果集合中存储的是自定义对象，必须重写hashCode和equals方法

加载因子：是数组扩容时间，当数组内元素达到16*0.75个元素
12个，就会触发扩容机制，扩容为原先的2倍

当数组的长度大于等于64且链表(挂的元素)的长度大于8，链表会自动转换为红黑树

一个元素下面挂多个元素的情况，实际上是由于哈希冲突造成的。当不同的元素经过哈希计算得到相同的数组索引位置时，它们会被存储在同一个位置对应的链表或者红黑树中。这种设计可以保证在HashSet中快速存储和查找元素，同时保证了存储的效率和性能。

HashSet的三个问题
  1. 为什么存和取的顺序不一样？

因为元素添加到数组中，是从数组的0索引开始依次向后遍历，全部遍历，遇到链表和红黑树，会先取链表和红黑树中元素，因此顺序会改变

  1. HashSet为什么没有索引？

底层涉及数组、链表、红黑树无法使用索引

  1. HashSet是利用什么机制保证数据去重的？

利用HashCode方法和equals方法，不同的数据算出的哈希值不同，如果遇到哈希冲突，再用equals方法比较数据属性值是否相同，相同则剔除

LinkedHashSet集合
  • 有序、不重复、无索引
底层原理

底层数据结构依旧是哈希表，只是每个元素又额外多了一个双链表的机制记录存储的顺序


遍历的时候从双向链表的头结点遍历，保证了数据的有序

TreeSet集合
  • 添加自定义对象时，必须指定排序规则
  • 不重复、无索引、可排序（默认从小到大）
  • TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都很好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class TreeSetDemo01 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Integer> ts = new TreeSet<Integer>();

        //添加元素
        ts.add(10);
        ts.add(40);
        ts.add(30);
        ts.add(50);
        ts.add(20);

        ts.add(30);

        //遍历集合

        // 增强for
        for(Integer i : ts) {
            System.out.println(i);
        }
        // 迭代器

        // Lambda表达式
        ts.forEach(s->System.out.print(s));
    }
}
TreeSet集合默认的规则
  • 对于数值类型，Integer、Double，默认按照从小到大的顺序进行排序
  • 对于字符、字符串类型：按照字符在ASCII码表中的数字升序进行排序(从小到大)，多个字符的字符串，从第一个字母开始依次比较字母的ASCII值
TreeSet比较规则


这里的需求是指一些特殊的排序，如字符长度等，第一种默认是数字从小到大，字母ASCII码从小到大

比较器内的写法

this：表示当前要添加的元素

o：表示已经在红黑树存在的元素

返回值：

负数：认为要添加的元素是小的，在左边

正数：认为要添加的元素是大的，在右边

0：认为添加的元素已经存在

方式一：

默认排序/自然排序：javabean类实现Comparable接口指定比较规则

需求：按照学生对象的年龄进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Student implements Comparable<Student>{
     private String name;
     private int age;

     public Student() {
     }

     public Student(String name, int age) {
         this.name = name;
         this.age = age;
     }

     public String getName() {
         return name;
     }

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

     public int getAge() {
         return age;
     }

     public void setAge(int age) {
         this.age = age;
     }

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

     @Override
     public int compareTo(Student o) {
         //按照对象的年龄进行排序
         //主要判断条件: 按照年龄从小到大排序
         /*
         this：表示当前要添加的元素
         o：表示已经在红黑树存在的元素
         返回值：
             负数：认为要添加的元素是小的，在左边
             正数：认为要添加的元素是大的，在右边
             0：认为添加的元素已经存在
         原理是写了红黑树存数的规则
         */
         int result = this.age - o.age;
         //次要判断条件: 年龄相同时，按照姓名的字母顺序排序
         result = result == 0 ? this.name.compareTo(o.getName()) : result;
         return result;
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MyTreeSet2 {
      public static void main(String[] args) {
          //创建集合对象
          TreeSet<Student> ts = new TreeSet<>();
  	    //创建学生对象
          Student s1 = new Student("zhangsan",23);
          Student s2 = new Student("lisi",24);
          Student s3 = new Student("wangwu",25);
          Student s4 = new Student("zhaoliu",26);
          Student s5 = new Student("qianqi",27);
  		//把学生添加到集合
          ts.add(s1);
          ts.add(s2);
          ts.add(s3);
          ts.add(s4);
          ts.add(s5);
  		//遍历集合
          for (Student student : ts) {
              System.out.println(student);
          }
      }
  }

方式二：创建TreeSet对象时候，传递比较器Comparator指定规则
有参构造，传递接口的实现类，重写比较方法

o1：表示当前要添加的元素

o2：表示已经在红黑树存在的元素

返回值规则与之前相同

  • 案例需求
    • 存储老师对象并遍历，创建TreeSet集合使用带参构造方法
    • 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Teacher {
      private String name;
      private int age;

      public Teacher() {
      }

      public Teacher(String name, int age) {
          this.name = name;
          this.age = age;
      }

      public String getName() {
          return name;
      }

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

      public int getAge() {
          return age;
      }

      public void setAge(int age) {
          this.age = age;
      }

      @Override
      public String toString() {
          return "Teacher{" +
                  "name='" + name + '\'' +
                  ", age=" + age +
                  '}';
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class MyTreeSet4 {
      public static void main(String[] args) {
        	//创建集合对象
          TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {
              @Override
              public int compare(Teacher o1, Teacher o2) {
                  //o1表示现在要存入的那个元素
                  //o2表示已经存入到集合中的元素
                
                  //主要条件
                  int result = o1.getAge() - o2.getAge();
                  //次要条件
                  result = result == 0 ? o1.getName().compareTo(o2.getName()) : result;
                  return result;
              }
          });
  		//创建老师对象
          Teacher t1 = new Teacher("zhangsan",23);
          Teacher t2 = new Teacher("lisi",22);
          Teacher t3 = new Teacher("wangwu",24);
          Teacher t4 = new Teacher("zhaoliu",24);
  		//把老师添加到集合
          ts.add(t1);
          ts.add(t2);
          ts.add(t3);
          ts.add(t4);
  		//遍历集合
          for (Teacher teacher : ts) {
              System.out.println(teacher);
          }
      }
  }

双列集合：一次添加一对数据

双列集合的特点：
  • 双列集合一次需要存一对数据，分别为键和值
  • 键不能重复，值可以重复
  • 键和值是一一对应的，每一个键只能找到自己对应的值
  • 键+值这个整体我们称之为“键值对”或“键值对对象”，在Java中叫做Entry对象

Map集合

Map是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用的

Map常见的API

方法名 说明
V   put(K key,V   value) 添加元素
V   remove(Object key) 根据键删除键值对元素
void   clear() 移除所有的键值对元素
boolean containsKey(Object key) 判断集合是否包含指定的键
boolean containsValue(Object value) 判断集合是否包含指定的值
boolean isEmpty() 判断集合是否为空
int size() 集合的长度，也就是集合中键值对的个数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class MapDemo02 {
     public static void main(String[] args) {
         //创建集合对象
         // Map是接口，不能创建其对象，创建其实现类的对象
         Map<String,String> map = new HashMap<String,String>();

         //V put(K key,V value)：添加元素
         /*
         put方法的细节：
         添加/覆盖
         在添加元素的时候，
         如果键不存在，就直接把键值对对象添加到Map集合中，方法返回null
         如果键存在，就把原有的键值对对象覆盖，把覆盖的值进行返回
         */
         map.put("张无忌","赵敏");
         map.put("郭靖","黄蓉");
         map.put("杨过","小龙女");

         //V remove(Object key)：根据键删除键值对元素
         /*
         删除方法，删除键，会删除键值对，会对值进行返回
         */
        System.out.println(map.remove("郭靖"));
        System.out.println(map.remove("郭襄"));

         //void clear()：移除所有的键值对元素
        map.clear();

         //boolean containsKey(Object key)：判断集合是否包含指定的键
        System.out.println(map.containsKey("郭靖"));
        System.out.println(map.containsKey("郭襄"));

         //boolean isEmpty()：判断集合是否为空
        System.out.println(map.isEmpty());

         //int size()：集合的长度，也就是集合中键值对的个数
         System.out.println(map.size());

         //输出集合对象
         System.out.println(map);
     }
 }

Map集合获取值的方式

方法名 说明
V   get(Object key) 根据键获取值
Set   keySet() 获取所有键的集合
Collection   values() 获取所有值的集合
Set<Map.Entry<K,V>>   entrySet() 获取所有键值对对象的集合 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class MapDemo03 {
      public static void main(String[] args) {
          //创建集合对象
          Map<String, String> map = new HashMap<String, String>();

          //添加元素
          map.put("张无忌", "赵敏");
          map.put("郭靖", "黄蓉");
          map.put("杨过", "小龙女");

          //V get(Object key):根据键获取值
  //        System.out.println(map.get("张无忌"));
  //        System.out.println(map.get("张三丰"));

          //Set<K> keySet():获取所有键的集合
  //        Set<String> keySet = map.keySet();
  //        for(String key : keySet) {
  //            System.out.println(key);
  //        }

          //Collection<V> values():获取所有值的集合
          Collection<String> values = map.values();
          for(String value : values) {
              System.out.println(value);
          }
      }
  }

Map集合遍历方式

  1. 键找值
  • 遍历思路
    • 我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
    • 把所有的丈夫给集中起来
    • 遍历丈夫的集合，获取到每一个丈夫
    • 根据丈夫去找对应的妻子
  • 步骤分析
    • 获取所有键的集合。用keySet()方法实现
    • 遍历键的集合，获取到每一个键。用增强for实现
    • 根据键去找值。用get(Object key)方法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MapDemo01 {
     public static void main(String[] args) {
         //创建集合对象
         Map<String, String> map = new HashMap<String, String>();

         //添加元素
         map.put("张无忌", "赵敏");
         map.put("郭靖", "黄蓉");
         map.put("杨过", "小龙女");

         //获取所有键的集合。用keySet()方法实现
         Set<String> keySet = map.keySet();
         //遍历键的集合，获取到每一个键。用增强for实现
         for (String key : keySet) {
             //根据键去找值。用get(Object key)方法实现
             String value = map.get(key);
             System.out.println(key + "," + value);
         }
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class HashMapDemo1 {
    public static void main(String[] args) {
        HashMap<String, String> hm = new HashMap<>();

        hm.put("西游记","吴承恩");
        hm.put("红楼梦","曹雪芹");
        hm.put("水浒传","施耐庵");
        hm.put("三国演义","罗贯中");

//        将键值对的键，使用keySet方法放入集合中
        Set<String> keySet = hm.keySet();

//        遍历集合
//        方式一：增强for
        for (String key : keySet) {
            String value = hm.get(key);
            System.out.println(key + "作者:" + value);
        }
        System.out.println("===========================================");

//        方式二：迭代器遍历
        Iterator<String> it = keySet.iterator();
        while (it.hasNext()){
           String value2 = it.next();
            System.out.println(value2+"作者："+ hm.get(value2));
        }
        System.out.println("===========================================");

//        方式三：lambda表达式遍历
        keySet.forEach(s -> System.out.println(s+"的作者:"+hm.get(s)));
    }
}
  1. 键值对
  • 遍历思路
    • 我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
    • 获取所有结婚证的集合
    • 遍历结婚证的集合，得到每一个结婚证
    • 根据结婚证获取丈夫和妻子
  • 步骤分析
    • 获取所有键值对对象的集合
      • Set<Map.Entry<K,V>> entrySet()：获取所有键值对对象的集合
    • 遍历键值对对象的集合，得到每一个键值对对象
      • 用增强for实现，得到每一个Map.Entry
    • 根据键值对对象获取键和值
      • 用getKey()得到键
      • 用getValue()得到值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class MapDemo02 {
      public static void main(String[] args) {
          //创建集合对象
          Map<String, String> map = new HashMap<String, String>();

          //添加元素
          map.put("张无忌", "赵敏");
          map.put("郭靖", "黄蓉");
          map.put("杨过", "小龙女");

          //获取所有键值对对象的集合
          Set<Map.Entry<String, String>> entrySet = map.entrySet();
          //遍历键值对对象的集合，得到每一个键值对对象
          for (Map.Entry<String, String> me : entrySet) {
              //根据键值对对象获取键和值
              String key = me.getKey();
              String value = me.getValue();
              System.out.println(key + "," + value);
          }
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package JiHe.map;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class HashMapDemo2 {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
//        添加元素
        map.put("富","强");
        map.put("民","主");
        map.put("文","明");
        map.put("和","谐");

//        放入键值对对象中
        Set<Map.Entry<String, String>> entries = map.entrySet();

//        使用增强for遍历
        for (Map.Entry<String, String> entry : entries) {
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + value);
        }

        System.out.println("===========================");

//        使用iterator迭代器遍历
        Iterator<Map.Entry<String, String>> it  = entries.iterator();
        while (it.hasNext()){
            Map.Entry<String, String> next = it.next();
            String value1 = next.getValue();
            String key1 = next.getKey();
            System.out.println(key1 + value1);
        }

        System.out.println("===========================");
//        lambda表达式遍历
        entries.forEach(entry ->{
            String key2 = entry.getKey();
            String value2 = entry.getValue();
            System.out.println(key2+value2);
        });

    }

}

  1. Lambda表达式遍历

底层原理;

底层实现就是通过调用entrySet方法将键值对对象放入Set集合中，然后使用增强for遍历，使用getKey、getValue方法取出键、值

此处的Lambda遍历与之前的Lambda遍历方式不同点在于：

之前的Lambda表达式是将键或键值对对象放入单列集合使用Lambda表达式遍历，实现的是Consumer函数式接口

此处的Lambda表达式是直接遍历Map集合，实现的是BiConsumer函数式接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class HashMapDemo3 {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();

        map.put("鱼香","肉丝");
        map.put("宫爆","鸡丁");
        map.put("夫妻","肺片");
        map.put("红烧","肉");

//        Lambda表达式遍历
        
//        map.forEach(new BiConsumer<String, String>() {
//            @Override
//            public void accept(String key, String value) {
//                System.out.println(key + value);
//            }
//        });


        map.forEach((key,value)->{
            System.out.println(key + value);
        });

    }
}

HashMap集合

  • 无序、不重复、无索引
  • HashMap是Map里面的一个实现类
  • HashMap跟HashSet底层原理是一模一样的，都是哈希表结构

底层原理：

  1. 创建一个数组
  2. 利用键计算哈希值，跟值无关
  3. 如果索引位置为空，则直接存入，如果键的位置已存在数据，比较属性值，属性值是一样的，就会覆盖原entry对象

注意：

  1. 如果键存储的是自定义对象，需要重写HashCode和equals方法
  2. 如果值存储自定义对象，并不需要重新HashCode和equals方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 学生类
public class Student {
    private String name;
    private Integer age;

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    public String getName() {
        return name;
    }

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

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(name, student.name) && Objects.equals(age, student.age);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

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

// 测试
public class HashMapDemo4 {
    public static void main(String[] args) {
        HashMap<Student, String> hm = new HashMap<>();

        hm.put(new Student("zhangsan", 23), "sichuan");
        hm.put(new Student("lisi", 24), "fujian");
        hm.put(new Student("wangwu", 25), "beijing");

        Set<Student> keySets = hm.keySet();

        Set<Map.Entry<Student, String>> entries = hm.entrySet();

//      键取值  增强for遍历
        for (Student key : keySets) {
            String value1 = hm.get(key);
            System.out.println(key + value1);
        }
        System.out.println("============================");

//        entry对象 iterator迭代器遍历
        Iterator<Map.Entry<Student, String>> it = entries.iterator();
        while(it.hasNext()){
            Map.Entry<Student, String> next = it.next();
            Student key2 = next.getKey();
            String value2 = next.getValue();
            System.out.println(key2 + value2);
        }
        System.out.println("==============================");

//        lambda表达式直接遍历map集合
        hm.forEach((key3,value3)->{
            System.out.println(key3+ value3);
        });

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// HashMap方法
public class HashMapDemo5 {
    public static void main(String[] args) {
//        设置四个景点
        String[] arr = {"A","B","C","D"};
//        产生随机数对象，模拟投票四个景点
        Random r = new Random();
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < 80; i++) {
            String ticket = arr[r.nextInt(arr.length)];
            list.add(ticket);
        }

//      将投好的票，放入Map集合中计数
        HashMap<String, Integer> map = new HashMap<>();
        for (String name : list) {
//            判断当前景点是否存在
            if (map.containsKey(name)){
//                存在则增加票数
//                通过键获取值，取出当前的票数
                Integer count = map.get(name);
//                让票数+1
                count++;
//                将新票数放入集合中
                map.put(name,count);
            }else{
//                不存在则存入景点
                map.put(name,1);
            }
        }

        map.forEach((key,value)-> System.out.println(key+"的票数是"+value+"票"));


    }
}
HashMap底层源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

static class Node<K, V> implements Map.Entry<K, V> { final int hash;
//键的哈希值 final K key; // 键 V value; //值 Node<K, V> next;
//是链表结构，指向下一个元素的地址值 }


// 红黑树的属性 static final class TreeNode<K, V> extends
LinkedHashMap.Entry<K, V> { int hash; //键的哈希值 final K key; //键 V
value; //值 TreeNode<K, V> parent; // 父节点的地址值 red-black tree links
TreeNode<K, V> left; //左子节点的地址值 TreeNode<K, V> right;
//右子节点的地址值 TreeNode<K, V> prev; // needed to unlink next upon
deletion boolean red; // 节点的颜色 }


    //这个数组就是HashMap中存放元素的数组
    transient Node<K, V>[] table;


    /**
     * The default initial capacity - MUST be a power of two.
     */

// 默认数组的长度1*2^4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// aka 16


    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */

// 最大的容量1*2^30 static final int MAXIMUM_CAPACITY = 1 << 30;


    /**
     * The load factor used when none specified in constructor.
     */
    // 决定了扩容时机
    static final float DEFAULT_LOAD_FACTOR = 0.75f;


    // 空参构造

// 当调用空参构造的时候，并未创建数组，只是将加载因子设置为默认加载因子 public
HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields
defaulted }


    // 2.添加元素
    HashMap<String, Integer> hm = new HashMap<>();

hm.put("aaa",111); hm.put("bbb",222); hm.put("ccc",333);
hm.put("ddd",444); hm.put("eee",555);

// 添加元素的时候至少考虑三种情况： // 2.1数组位置为null //
2.2数组位置不为null，键不重复，挂在下面形成链表或者红黑树 //
2.3数组位置不为null，键重复，元素覆盖


// 添加方法,当调用添加方法的时候才会创建table数组 // 参数1：键 参数2：值
返回值，被覆盖元素的值，没有覆盖返回null public V put(K key,V value){ //
第一个字段是将key传过去计算键的hash值 //
第四个参数，表示当前的参数是否保留，相同值时覆盖数据，就是这个参数决定 return
putVal(hash(key),key,value,false,true); }


//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值 static final int hash(Object key){ int h;
return(key==null)?0:(h=key.hashCode())^(h>>>16); }


// put方法调用putVal方法 // 参数1：键的hash值 参数2：键 参数3：值
参数4：如果键重复了，是否保留 // ture：旧元素的值保留，不覆盖	//
false：旧元素的值不会保留，覆盖 final V putVal(int hash,K key,V
value,boolean onlyIfAbsent, boolean evict){
//定义一个局部变量，用来记录哈希表中数组的地址值。 //
方法运行在栈中，数组存放在堆中，需要反复从栈到堆中寻找使用 // 效率不高 Node<K,
V>[]tab; //临时的第三方变量，用来记录键值对对象的地址值 Node<K, V> p;
//表示当前数组的长度 int n; //表示索引 int i; //
把hash表中数组的地址值，赋值给局部变量tab tab=table
if(tab==null||(n=tab.length)==0) // resize在底层做的事情
//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
//如果没有达到扩容条件，底层不会做任何操作
//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
tab=resize(); //表示把当前数组的长度赋值给n n=tab.length;

        // 拿着数组的长度跟键的哈希值进行与运算，计算出当前键值对对象，在数组中应该存入的位置
        i=(n-1)&hash;
        // 获取数组中对应的键值对对象的地址值
        p=tab[i];

        // 数组位置的地址值为null，走if中的代码
        if(p == null){
            // 将哈希值、键、值、null传递给一个名为newNode的方法
            // newNode方法底层会创建一个键值对对象，然后放入数组中
            tab[i]=newNode(hash,key,value,null);
        // 不为空，走else
        }else{
            Node<K, V> e;K k;

            // 等号左边：数组中，键值对的hash值(键值对的哈希值是根据键算的)
            // 等号右边：当前要添加键值对的哈希值
            // 如果键不一样，会返回false
            // 如果键一样，返回true
            boolean b1 = p.hash==hash;

            // 如果哈希值不一样，键肯定不一样，走下边的判断
            if( b1 &&((k=p.key)==key||(key!=null&&key.equals(k)))){
                e=p;
                // 判断p是不是树的节点
            }else if(p instanceof TreeNode){
                // 如果从数组中获取出的键值对是树的节点会添加到红黑树中
                e=((TreeNode<K, V>)p).putTreeVal(this,tab,hash,key,value);
            }else{
                // 如果不是树节点就当做链表结点,添加到链表当中
                for(int binCount=0;/*判断条件为true*/;++binCount){
                    // 获取数组中的结点的下一个结点,赋值给e
                    // 判断下一个结点是否为null
                    if((e=p.next)==null){
                        // 如果为null就会创建一个新的结点,来挂哈希值相同,但是键不同的键值对对象
                        // 形成一个新的链表
                        p.next=newNode(hash,key,value,null);
                        // 判断长度是否超过8
                        if(binCount>=TREEIFY_THRESHOLD-1) // -1 for 1st
                            // 超过8 就会调用treeifyBin
                            // 该方法的底层还会继续判断
                            // 判断数组的长度是否大于等于64
                            // 如果同时满足这两个条件,就会将链表转为红黑树
                            treeifyBin(tab,hash);
                        // 跳出循环
                        break;
                    }
                    // 若计算出哈希值一样，还需要用equals比较内部的属性值是否相同，属性值不同，又会返回循环
                    // 若内部的属性值一样，break
                    if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))
                        break;
                    p=e;
                }
            }

            // 如果e为空,表示当前不覆盖任何元素
            // e不为空，表示当前的键是一样的，值需要进行覆盖
            if(e!=null){ // existing mapping for key
                V oldValue=e.value;
                if(!onlyIfAbsent||oldValue==null){

                    // 等号的右边：当前要添加的值
                    // 等号的左边：被覆盖的值
                    e.value=value;
            }
                afterNodeAccess(e);
                // 将被覆盖的值return
                return oldValue;
            }
        }
        ++modCount;
        //threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12
        //size先++再和扩容时机(阈值)去比较 
        if(++size>threshold){
            resize();
        }
       
        afterNodeInsertion(evict);

        // 若当前没有覆盖任何元素，返回null
        return null;
        }

LinkedHashMap集合

  • 由键决定：有序，不重复，无索引
  • 底层依旧是哈希表，每个键值对又多了一个双链表的机制记录存储的顺序

TreeMap集合

  • 添加自定义对象时，必须指定排序规则
  • 底层是红黑树
  • 由键决定特性：不重复、无索引、可排序
  • 可排序：对键进行排序
  • 默认按照从小到大进行排序，也可以自己规定键的排序

书写两种排序规则

  • 实现comparable接口，指定比较规则
  • 创建集合时传递Comparator比较器对象，指定比较规则

案例需求

  • 创建一个TreeMap集合,键是学生对象(Student),值是籍贯(String),学生属性姓名和年龄按照年龄进行排序并遍历
  • 要求按照学生的年龄进行排序,如果年龄相同则按照姓名进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Student implements Comparable<Student>{
      private String name;
      private int age;

      public Student() {
      }

      public Student(String name, int age) {
          this.name = name;
          this.age = age;
      }

      public String getName() {
          return name;
      }

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

      public int getAge() {
          return age;
      }

      public void setAge(int age) {
          this.age = age;
      }

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

      @Override
      public int compareTo(Student o) {
          //按照年龄进行排序
          int result = o.getAge() - this.getAge();
          //次要条件，按照姓名排序。
          //此处的compareTo是String包重写的方法，按照字母的ASCII码顺序，从小到大
          result = result == 0 ? o.getName().compareTo(this.getName()) : result;
          return result;
      }
  }



public class Test1 {
      public static void main(String[] args) {
        	// 创建TreeMap集合对象
          TreeMap<Student,String> tm = new TreeMap<>();
        
  		// 创建学生对象
          Student s1 = new Student("xiaohei",23);
          Student s2 = new Student("dapang",22);
          Student s3 = new Student("xiaomei",22);
        
  		// 将学生对象添加到TreeMap集合中
          tm.put(s1,"江苏");
          tm.put(s2,"北京");
          tm.put(s3,"天津");
        
  		// 遍历TreeMap集合,打印每个学生的信息
          tm.forEach(
                  (Student key, String value)->{
                      System.out.println(key + "---" + value);
                  }
          );
      }
  }

创建集合对象时，传递Comparator比较器对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TreeMapDemo1 {
    public static void main(String[] args) {
        String s = "abcdbcdbbcdaacbfgfgdfggjuhiulghvbsdawfcggjjloioplpihjgbncvcvbbaxaaefdbacbd";
        TreeMap<Character, Integer> tm = new TreeMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
//            判断集合集合中是否有这个字符
            if (tm.containsKey(c)){
//                有的话就计数，更新
                Integer count = tm.get(c);
                count++;
                tm.put(c,count);

            }else{
//                没有就添加进去
                tm.put(c,1);
            }
        }
//        遍历集合，拼接
        tm.forEach((key,value)-> System.out.print(key+"("+value+")"));
    }
}

StringBuilder拼接字符串

TreeMap底层源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
    private static final boolean RED   = false;
    private static final boolean BLACK = true;

    /**
     * Node in the Tree.  Doubles as a means to pass key-value pairs back to
     * user (see Map.Entry).
     */

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
    }

// 三个需要知道的成员变量 // 比较规则 private final Comparator<? super K>
comparator;

    //根节点 
    private transient Entry<K,V> root;

    /**
     * The number of entries in the tree
     */
    // 集合的长度、红黑表中节点的个数
    private transient int size = 0;


// 空参构造 // 默认传值，没有比较器对象 public TreeMap() { comparator = null;
} // 带参构造 // 传递比较器对象 public TreeMap(Comparator<? super K>
comparator) { this.comparator = comparator; }


参数一：键 参数二：值 参数三：当键重复的时候，是否需要覆盖值 true：覆盖 false：不覆盖

    private V put(K key, V value, boolean replaceOld) {
    	//获取根节点的地址值，赋值给局部变量t
        Entry<K,V> t = root;
    	//判断根节点是否为null
    	//如果为null，表示当前是第一次添加，会把当前要添加的元素，当做根节点
    	//如果不为null，表示当前不是第一次添加，跳过这个判断继续执行下面的代码
        if (t == null) {
    		//方法的底层，会创建一个Entry对象，把他当做根节点
            addEntryToEmptyMap(key, value);
    		//表示此时没有覆盖任何的元素
            return null;
        }
    	//表示两个元素的键比较之后的结果
        int cmp;
    	//表示当前要添加节点的父节点
        Entry<K,V> parent;
    	
    	//表示当前的比较规则
    	//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null
    	//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器
        Comparator<? super K> cpr = comparator;
    	//表示判断当前是否有比较器对象
    	//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准
    	//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准
        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 {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        } else {
    		//把键进行强转，强转成Comparable类型的
    		//要求：键必须要实现Comparable接口，如果没有实现这个接口
    		//此时在强转的时候，就会报错。
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
    			//把根节点当做当前节点的父节点
                parent = t;
    			//调用compareTo方法，比较根节点和当前要添加节点的大小关系
                cmp = k.compareTo(t.key);
    			
                if (cmp < 0)
    				//如果比较的结果为负数
    				//那么继续到根节点的左边去找
                    t = t.left;
                else if (cmp > 0)
    				//如果比较的结果为正数
    				//那么继续到根节点的右边去找
                    t = t.right;
                else {
    				//如果比较的结果为0，会覆盖
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
                // 判断要添加的根节点是否为空，不为空就继续找地方添加
                // 为空就找到了地方，进行添加节点
            } while (t != null);
        }
    	//就会把当前节点按照指定的规则进行添加
        addEntry(key, value, parent, cmp < 0);
        return null;
    }	



     private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (addToLeft)
            parent.left = e;
        else
            parent.right = e;
    	//添加完毕之后，需要按照红黑树的规则进行调整
        fixAfterInsertion(e);
        size++;
        modCount++;
    }



    private void fixAfterInsertion(Entry<K,V> x) {
    	//因为红黑树的节点默认就是红色的
        x.color = RED;

    	//按照红黑规则进行调整
    	
    	//parentOf:获取x的父节点
    	//parentOf(parentOf(x)):获取x的爷爷节点
    	//leftOf:获取左子节点
        while (x != null && x != root && x.parent.color == RED) {
    		
    		
    		//判断当前节点的父节点是爷爷节点的左子节点还是右子节点
    		//目的：为了获取当前节点的叔叔节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
    			//表示当前节点的父节点是爷爷节点的左子节点
    			//那么下面就可以用rightOf获取到当前节点的叔叔节点
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
    				//叔叔节点为红色的处理方案
    				
    				//把父节点设置为黑色
                    setColor(parentOf(x), BLACK);
    				//把叔叔节点设置为黑色
                    setColor(y, BLACK);
    				//把爷爷节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
    				
    				//把爷爷节点设置为当前节点
                    x = parentOf(parentOf(x));
                } else {
    				
    				//叔叔节点为黑色的处理方案
    				
    				
    				//表示判断当前节点是否为父节点的右子节点
                    if (x == rightOf(parentOf(x))) {
    					
    					//表示当前节点是父节点的右子节点
                        x = parentOf(x);
    					//左旋
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
    			//表示当前节点的父节点是爷爷节点的右子节点
    			//那么下面就可以用leftOf获取到当前节点的叔叔节点
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    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;
    }


6.课堂思考问题： 6.1TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？
此时是不需要重写的。


6.2HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。
既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？
不需要的。 因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的


6.3TreeMap和HashMap谁的效率更高？
如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高
但是这种情况出现的几率非常的少。 一般而言，还是HashMap的效率要更高。


6.4你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？
此时putIfAbsent本身不重要。 传递一个思想：
代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。
那么该逻辑一定会有B面。

    习惯：
    	boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
    	int类型的变量控制，一般至少有三面，因为int可以取多个值。


6.5三种双列集合，以后如何选择？ HashMap LinkedHashMap TreeMap

    默认：HashMap（效率最高）
    如果要保证存取有序：LinkedHashMap
    如果要进行排序：TreeMap

可变参数

方法形参的个数是可以发生变化的

格式:属性类型…名字

int…args

可变参数
可变参数的细节：

Collections

  • java.util.Collections：是集合工具类
  • 作用：Collections不是集合，而是集合的工具类

常用API


前两个方法的示例

不变集合

创建不可变的集合

不能修改的集合：长度不能修改、内容不能修改
  • 如果某个数据不能被修改，把它防御性拷贝到不可变集合中是很好的实践
  • 当集合对象被不可信的库调用时，不可变形式是安全的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class ImmutableDemo1 {
    public static void main(String[] args) {
        /*
            创建不可变的List集合
            "张三", "李四", "王五", "赵六"
        */

        //一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
        List<String> list = List.of("张三", "李四", "王五", "赵六");

        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
        System.out.println(list.get(3));

        System.out.println("---------------------------");

        for (String s : list) {
            System.out.println(s);
        }

        System.out.println("---------------------------");


        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("---------------------------");

        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }
        System.out.println("---------------------------");

        //list.remove("李四");
        //list.add("aaa");
        list.set(0,"aaa");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ImmutableDemo2 {
    public static void main(String[] args) {
        /*
           创建不可变的Set集合
           "张三", "李四", "王五", "赵六"


           细节：
                当我们要获取一个不可变的Set集合时，里面的参数一定要保证唯一性
        */

        //一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
        Set<String> set = Set.of("张三", "张三", "李四", "王五", "赵六");

        for (String s : set) {
            System.out.println(s);
        }

        System.out.println("-----------------------");

        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }

        System.out.println("-----------------------");
        //set.remove("王五");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 键值对数<=10
public class ImmutableDemo3 {
    public static void main(String[] args) {
       /*
        创建Map的不可变集合
            细节1：
                键是不能重复的
            细节2：
                Map里面的of方法，参数是有上限的，最多只能传递20个参数，10个键值对
            细节3：
                如果我们要传递多个键值对对象，数量大于10个，在Map接口中还有一个方法
        */

        //一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
        Map<String, String> map = Map.of("张三", "南京", "张三", "北京", "王五", "上海",
                "赵六", "广州", "孙七", "深圳", "周八", "杭州",
                "吴九", "宁波", "郑十", "苏州", "刘一", "无锡",
                "陈二", "嘉兴");

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

        System.out.println("--------------------------");

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

// 键值对数大于10
public class ImmutableDemo4 {
    public static void main(String[] args) {

        /*
            创建Map的不可变集合,键值对的数量超过10个
        */

        //1.创建一个普通的Map集合
        HashMap<String, String> hm = new HashMap<>();
        hm.put("张三", "南京");
        hm.put("李四", "北京");
        hm.put("王五", "上海");
        hm.put("赵六", "北京");
        hm.put("孙七", "深圳");
        hm.put("周八", "杭州");
        hm.put("吴九", "宁波");
        hm.put("郑十", "苏州");
        hm.put("刘一", "无锡");
        hm.put("陈二", "嘉兴");
        hm.put("aaa", "111");

        //2.利用上面的数据来获取一个不可变的集合
/*
        //获取到所有的键值对对象（Entry对象）
        Set<Map.Entry<String, String>> entries = hm.entrySet();
        //把entries变成一个数组
        Map.Entry[] arr1 = new Map.Entry[0];
        //toArray方法在底层会比较集合的长度跟数组的长度两者的大小
        //如果集合的长度 > 数组的长度 ：数据在数组中放不下，此时会根据实际数据的个数，重新创建数组
        //如果集合的长度 <= 数组的长度：数据在数组中放的下，此时不会创建新的数组，而是直接用
        Map.Entry[] arr2 = entries.toArray(arr1);
        //不可变的map集合
        Map map = Map.ofEntries(arr2);
        map.put("bbb","222");*/


        //Map<Object, Object> map = Map.ofEntries(hm.entrySet().toArray(new Map.Entry[0]));

        Map<String, String> map = Map.copyOf(hm);
        map.put("bbb","222");
    }
}