Java集合（复习）

Java中的集合

概述

集合、数组都是对多个数据进行存储操作的结构，简称Java容器。

说明: 此时的存储，主要是指能存层面的存储，不涉及到持久化的存储（.txt,.jpg,.avi,数据库中）

数组在存储多个数据方面的特点：

• 一旦初始化以后，它的长度就确定了。
• 数组一旦定义好，它的数据类型也就确定了。我们就只能操作指定类型的数据了。
  • 比如：String[] arr;int[] str;

数组在存储多个数据方面的特点：

• 一旦初始化以后，其长度就不可修改。
• 数组中提供的方法非常有限，对于添加、删除、插入数据等操作，非常不便，同时效率不高。
• 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
• 数组存储数据的特点：有序、可重复。对于无序、不可重复的需求，不能满足。

集合分类

• Java 集合可分为Collection和Map两种体系
  • Collection接口：单列数据，定义了存取一组对象的方法的集合
    • List：元素有序、可重复的集合
    • Set：元素无序、不可重复的集合
  • Map接口：双列数据，保存具有映射关系“key-value对”的集合

Collection 接口继承树：

Map接口继承树：

Collection 接口中常用的方法

Iterator 迭代器

Iterator对象称为迭代器(设计模式的一种)，主要用于遍历Collection 集合中的元素。

GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

Collection接口继承了 java.lang.Iterable 接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。

Iterator 仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator 接口中的方法：

使用迭代器遍历集合：

    @Test
    public void test() {
        Collection coll = new ArrayList();
        coll.add(11);
        coll.add("lisi");
        coll.add(new Date());

        // d迭代器遍历
        Iterator iterator = coll.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

remove() 方法调用之前确保已经调用了 next() 方法，否则会报 java.lang.IllegalStateException

    @Test
    public void test() {
        Collection coll = new ArrayList();
        coll.add(11);
        coll.add("lisi");
        coll.add(new Date());

        // d迭代器遍历
        Iterator iterator = coll.iterator();
        while(iterator.hasNext()) {
            Object next = iterator.next();
            if ("lisi".equals(next)) {
                iterator.remove();
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

forEach 增强for循环

底层也是用的迭代器遍历

语法：

for (数据类型:变量名 遍历的集合){

​ // 输出

}

关于 forEach 的面试题：以下代码会输出什么？

    @Test
    public void test2 () {
        String[] strings = {"11", "11", "11"};

        for (int i = 0; i < strings.length; i++) {
            strings[i] = "22";
        }
        System.out.println(Arrays.toString(strings));
    }
1
2
3
4
5
6
7
8
9

输出结果：

22 22 22
1

以下这段代码又会输出什么？

    @Test
    public void test2 () {
        String[] strings = {"11", "11", "11"};

        for (String s : strings) {
            s = "22";
        }
        System.out.println(Arrays.toString(strings));
    }
1
2
3
4
5
6
7
8
9

输出结果：

11 11 11
1

forEach 中的变量：相当于是将数组的值赋值给变量，改变的不是数组中的值，而是这个变量的值。

Collection子接口之一：List 接口

• 鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组
• List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
• JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

经典面试题： ArrayList、LinkedList和Vector 有何异同？

相同点： 都实现了 List 接口，都能存储有序、可重复的数据。

不同：

1、底层实现的数据结构不同： ArrayList 和 Vector 采用的都是Object类型的数组，而 LinkedList 采用的双向链表

2、操作数据的效率不同：

• ​ 查询数据： 由于 ArrayList 和 Vector采用的数组结构，按index索引get/set 数据，因此它的查询效率非常高。而LinkedList则需要从头结点向尾结点遍历，直到找到目标位置。因此在查询上 ArrayList 和 Vector 会优于 LinkedList
• 对于随机插入、删除数据： ArrayList和 Vector 需要移动目标节点的后面节点，而LinkedList只需要修改节点的next 和 pre 地址即可。因此在效率上 LinkedList 优于 ArrayList和 Vector
• 对于顺序插入、删除数据：由于 ArrayList 不需要移动节点，因此在效率上比 LinkedList 更好。这也是为什么在实际使用中 ArrayList 更多，因为大部分情况下我们的使用都是顺序插入。

3、 安全性不同：

​ Vector 集合中的方法都是线程安全的，因此在性能上 ArrayList 要更好一点。

ArrayList 源码分析

Jdk7 中：

在 Jdk7 中 ，创建ArrayList 实例时，底层就创建了一个 长度为 10 的 Object类型的数组。在进行扩容时，扩容为之前的 1.5 倍，同时将原有数组中的数据拷贝到新的数组中。

在创建 ArrayList 实例时，可以指定容量大小，并且也推荐这样使用。

ArrayList list = new ArrayList(int capacity)

Jdk 8 中：

在Jdk 8中，创建 ArrayList 实例时，并不会马上指定数组长度，而是在执行第一次 add 操作时，指定数组长度为 10 ，扩容时仍然为之前的1.5 倍

、

LinkedLIst 源码分析

• 对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高
• LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构

在 LinkedList 源码中，定义了一个 Node 私有类，使用 Node 类保存集合中的元素

    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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

Vector 源码分析

Vector集合底层初始长度为 10，扩容方式为之前的 2 倍

创建 Vector 实例时初始化容量 10

扩容为之前的 2 倍 ：

List 接口常用的方法

除了继承的 Collection 中的 方法，List 中还增加了一些根据索引操作集合的方法

public class ListTest1 {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        // void add(intindex, Object ele)
        list.add(1,"B");
        System.out.println(list); // [a, B, b, c]

        // boolean addAll(int index, Collection eles)
        List<String> asList = Arrays.asList("c","d", "e", "f");
        list.addAll(4,asList);
        System.out.println(list); // [a, B, b, c, c, d, e, f]

        // int indexOf(Object obj)
        int index = list.indexOf("c");
        System.out.println(index); // 3

        // int lastIndexOf(Object obj)
        int index2 = list.lastIndexOf("c");
        System.out.println(index2); // 4

        // Object remove(int index)
        Object remove = list.remove(4);
        System.out.println(remove); // c

        // Object set(int index, Object ele)
        Object a = list.set(0, "A");
        System.out.println(list); //[A, B, b, c, d, e, f]

        // List subList(int fromIndex, int toIndex)
        List<Object> objects = list.subList(0, 4);
        System.out.println(objects); // [A, B, b, c]

    }
}
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

 * 总结：常用方法
 * 增：add(Object obj)
 * 删：remove(int index) / remove(Object obj)
 * 改：set(int index, Object ele)
 * 查：get(int index)
 * 插：add(int index, Object ele)
 * 长度：size()
 * 遍历：① Iterator迭代器方式
 *      ② 增强for循环
 *      ③ 普通的循环
1
2
3
4
5
6
7
8
9
10

面试题：

    /**
     * 区分List中remove(int index)和remove(Object obj)
     */

    @Test
    public void testListRemove() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);//
    }

    private void updateList(List list) {
//        list.remove(2); 输出结果：[1,2]
        list.remove(new Integer(2)); // 输出结果：[1,3]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

new Integer(2): 会将 2 看做一个对象

list.remove(2) ： 会将 2 看成索引

Collection 子接口之二： Set 接口

• Set接口是Collection的子接口，set接口没有提供额外的方法
• Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
• Set 判断两个对象是否相同不是使用==运算符，而是根据equals()方法
• Set 的主要实现类： HashSet、LinkedHashSet(HashSet的子类)、TreeSet

Set 集合的特点：

• 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
• 不可重复：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

HashSet

• HashSet是Set 接口的典型实现，大多数时候使用Set 集合时都使用这个实现类。
• HashSet按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
• HashSet具有以下特点：
  • 不能保证元素的排列顺序
  • HashSet不是线程安全的
  • 集合元素可以是null
• 底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32，依次为64,128…等）
• HashSet 集合判断两个元素相等的标准：两个对象通过hashCode() 方法比较相等，并且两个对象的equals()方法返回值也相等。
• 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

HashSet存储数据的过程？ 如何判断不可重复性

HashSet法来判断元素是否重复。hashCode方法可以这样理解：它返回的就是根据对象的内存地址换算出的一个值

在增加元素时，首先会调用 元素的 hashCode() , 得到元素的哈希值，根据这个哈希值就能定位到他在内存中的位置：

• 如果此位置上是空的，那么就直接将元素存储到这个位置上。
• 如果此位置上有元素，先判断俩个元素的哈希值：
  • 如果哈希值不一样，则增加成功，存入到对应的链表中。
  • 如果哈希值一样，则会根据元素的 equals 方法判断是否相等
    • 如果相等，判断为重复元素，则增加失败。
    • 如果不相等，则增加成功，存入到对应的链表中。

LinkedHashSet

• LinkedHashSet是HashSet的子类
• LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
• LinkedHashSet插入性能略低于HashSet，但在迭代访问Set 里的全部元素时有很好的性能。
• LinkedHashSet不允许集合元素重复。

LInkedHashSet 遍历的顺序和插入的顺序是一致的，就是因为使用了双向链表中保存 next 、pre 地址。

public class LinkHashSetTest {
    public static void main(String[] args) {
        LinkedHashSet<Object> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("a");
        linkedHashSet.add("b");
        linkedHashSet.add("c");
        System.out.println(linkedHashSet); // [a, b, c]

    }
}
1
2
3
4
5
6
7
8
9
10

TreeSet

• TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。
• TreeSet 的俩种排序方法： 自然排序 和 定制排序
• 存放在 TreeSet 集合中的数据应该是同一类的对象，因为只有同一类的对象才能进行比较。比如： string类型的和 int类型这样的就无法比较了。
• TreeSet 底层采用 红黑树 的数据结构存储数据

自然排序

• 存放在 TreeSet 中的对象必须实现 Comparable 接口，并且重写 compareTo(Object obj)方法 ， TreeSet 会根据 CompareTo 的返回值进行排序。返回0：相等，返回正整数：大于，返回-1：小于

代码演示：

User 类：

public class User implements Comparable{
    private String name ;
    private int age ;

    public User() {
    }

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

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

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

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

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

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

    @Override
    public int compareTo(Object o) {
        if (o instanceof User) {
            int result = this.name.compareTo(((User) o).name);
            if (result != 0) {
                return result;
            }else {
                return Integer.compare(this.age,((User) o).age);
            }
        }
        return 0;
    }
}

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

测试：

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Object> treeSet = new TreeSet<>();
        treeSet.add(new User("aliya",22));
        treeSet.add(new User("mike",17));
        treeSet.add(new User("brose",30));
        treeSet.add(new User("brose",28));

        System.out.println(treeSet);
    }
}
1
2
3
4
5
6
7
8
9
10
11

输出结果：

[User{name='aliya', age=22}, User{name='brose', age=30}, User{name='brose', age=28}, User{name='mike', age=17}]
1

定制排序

• 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
• 利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
• 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
• 使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

  // 实现定制排序
    @Test
    public void test() {
        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof  User) {
                    User user1 = (User)o1;
                    User user2 = (User)o2;
                    // 根据年龄从小到大
                    return Integer.compare(user1.getAge(),user2.getAge());
                }
                return 0;
            }
        };
        // 将 comparator 参数传进去
        TreeSet<Object> treeSet = new TreeSet<>(comparator);
        treeSet.add(new User("aliya",22));
        treeSet.add(new User("mike",17));
        treeSet.add(new User("brose",30));
        treeSet.add(new User("brose",28));

        System.out.println(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

重写 hashCode 和 equals 原则

• 重写 equals() 就一定要重写 hashCode

• 参与到 hashCode 中的属性，在 equals中也一定要参与比较

• 当俩个对象的equals相等，那么它的 hashCode 也相等，反之则不一定

Set集合面试题

Person类

public class Person {
    int id;
    String name ;

    public Person() {
    }

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

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

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

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}
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

 // 面试题
    @Test
    public void test3() {
        HashSet set = new HashSet();
        Person p1 = new Person(1001, "AA");
        Person p2 = new Person(1002, "BB");

        set.add(p1);
        set.add(p2);
        System.out.println(set); 

        p1.name = "CC";
        set.remove(p1);
        System.out.println(set);

        set.add(new Person(1001, "CC")); 
        System.out.println(set);
        
        set.add(new Person(1001, "AA"));
        System.out.println(set); 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第一个 sout 输出肯定没问题，简单的输出集合

第二个 sout 估计很多人想的都是： [Person{id=1002, name='BB'}]，但是结果却是 [Person{id=1002, name='BB'}, Person{id=1001, name='CC'}] 原因是什么呢？

在将 p1 、p2 存入集合时，它是按照 俩个对象的 哈希值 存入指定位置的，如下图所示：

在执行 p1.name = “CC” 后，此时存储发生变化：

在执行 remove 时，他首先会获取 1001，"CC" 这个对象的哈希值，定位到数组中的位置（箭头所指）。p1 的位置是 1001，"AA" 对象哈希值的位置，拿着 1001，"CC" 对象的哈希值去找肯定找不到，因此删除失败。

第三个 sout，是不是有人会想： 咦, Set 集合不可重复，有一个 1001，“CC”，肯定添加失败。那你就又错了，最后结果是能存进去。

接着上图所说，获取 1001，"CC" 对象的哈希值后，在数组中定位位置，发现是空的，因此判断是不重复的。

第四个 sout ，这时会有人说了，这我知道了，p1 是 1001，"AA" 对象哈希值的位置，此时又存入了一个 1001，"AA" ，哈希值一样，肯定添加失败。

错错错！！，哈希值一样是没错，位置一样也没错，但是 哈希值一样，还会根据 equals 方法进行比较，此时 p1位置上是 1001，"CC" , equals 返回 false， 因此存储成功。

总结：

熟练掌握 HashSet 的存储过程，有利于理解 HashMap ！！！

Map 接口

• Map接口：存储 key-value 的键值对
  • HashMap ：作为Map 的主要实现类，线程非安全，允许 key-value 的值为 null
    • LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。
      • 原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
      • 对于频繁的遍历操作，此类执行效率高于HashMap。
  • TreeMap：保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用 红黑树
  • HashTable： 线程安全，效率低，不允许 key-value 的值为 null
    • Properties：常用来 处理配置文件，key 和 value 都是 String 类型。

Map 结构的理解

• Map中的key : 无序的、不可重复的，使用Set存储所有的key —> key所在的类要重写equals()和hashCode() （以HashMap为例）
• Map中的value: 无序的、可重复的，使用Collection存储所有的value —>value所在的类要重写equals()
• 一个键值对：key-value构成了一个Entry对象。
• Map中的entry: 无序的、不可重复的，使用Set存储所有的entry

HashMap 底层实现原理

HashMap 在 jdk8 之前底层采用 数组 + 链表 实现，jdk8 之后，采用 数组+链表+红黑树 实现。

HashMap 的 Jdk7 时底层实现原理：

• 当 HashMap map = new HashMap(): 创建一个 HashMap 实例时，底层创建了长度是16的一维数组Entry[ ] table。
• map.put(key1,value1)；
• 首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
• 如果此位置上为空，此时的 key1-value1 直接存储在数组中。
• 如果此位置上不为空，也就意味着此位置上有一个或多个数据存储在 链表 上。此时比较 key1与 其他 元素key的 哈希值：
  • 如果key1的哈希值与其他元素的key哈希值都不相等，则存入链表中
  • 如果此时key1 的哈希值与某一个 元素key 的哈希值相等， 就调用 k1 所在类的 equals 方法，k1.equals(k2) ：
    • 如果 equals 返回为 false ，存储到链表中
    • 如果 equals 返回为 true ，value1 的值 覆盖 value2 的值

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

HashMap 的 Jdk8 相较于 Jdk7 底层实现原理的不同：

• 创建HashMap 实例时，并没有创建长度为 16 的一个数组，而是在首次进行 put() 操作时，创建了一个长度 16 的 Node[ ] 数组，而是 Entry[ ] 数组。
• jdk8 底层数据结构采用： 数组+链表+红黑树 存储数据

什么时候用到红黑树。什么时候用链表？

对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后超过8个（阈值8), 并且数组的长度超过 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。

对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。

HashMap 源码分析

HashMap源码中定义的一些属性：

jdk7 中 HashMap 源码：

首先看 HashMap 中构造器的方法：

    /**
     * Constructs an empty HashMap with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

	// this 调用此构造方法: 主要是对参数的一些校验，以及赋值
    public HashMap(int initialCapacity, float loadFactor) {
        // 初始容量为16不成立
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 16 并未超过最大容量，不成立
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 对加载因子的判断，大于0，是一个Float类型，不成立
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 设置默认加载因子
        this.loadFactor = loadFactor;
        // 设置临界值为 16
        threshold = initialCapacity;
        init();
    }
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

在 new 一个 HashMap是实例时，设置DEFAULT_INITIAL_CAPACITY默认容量为16， DEFAULT_LOAD_FACTOR 加载因子，默认值 0.75，threshold 也为 16

HashMap的 put 方法：

    public V put(K key, V value) {
        // 这里主要是为了检查设置的初始容量是否是 2 的n次幂，如果不是自动给他调整为 2 的n次幂
       // 并且在这个方法中创建数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        // 这个主要是对 key、value 为null 的一个处理
        if (key == null)
            return putForNullKey(value);
        // 计算key的哈希值
        int hash = hash(key);
        // 根据哈希值，找到在数组中的存放位置
        int i = indexFor(hash, table.length);
        // 这个 for 循环，就是遍历数组中某一个位置上的所有元素，因为在链表中可能存在多个元素。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 比较哈希值，equals 比较。
            // 这里还用了一个 == 比较，比较俩个 key 的内存地址，内存地址一样了，就不用比较 equals，也算是提高了效率
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 如果 哈希值 和 equals判断都为 true，就判定为重复的 key ，就直接 覆盖 vlaue
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        // 增加元素方法
        addEntry(hash, key, value, i);
        return null;
    }
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

inflateTable() 方法：

• roundUpToPowerOf2() 通过此方法，将容量控制在 2 的 n 次幂
• 设置临界值
• 创建数组，并设置初始长度

    /**
     * Inflates the table.
     */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
        // 从这里也可以得出： 临界值 = 容量 * 加载因子
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        // 从这里开始创建数组，
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12

indexFor: 根据哈希值找到元素在数组中存放的位置

采用 & ，效率高

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }
1
2
3
4
5
6
7

addEntry :增加元素的方法

• resize(2 * table.length);：扩容为之前容量的俩倍

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 扩容的条件：从这里就能看出，扩容的条件不仅仅是超出临界值，并且还要当前的位置不能为空。
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
1
2
3
4
5
6
7
8
9
10

jdk8 中 HashMap 源码：

一位老哥的博客写的非常详细：https://blog.csdn.net/qq_42764468/article/details/107934014

LinkedHashMap

• LinkedHashMap是HashMap的子类
• 在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
• 与LinkedHashSet类似，LinkedHashMap可以维护Map 的迭代顺序：迭代顺序与Key-Value 对的插入顺序一致

Entry内部类：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 能够记录插入的顺序
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
1
2
3
4
5
6

Map 接口常用的方法

TreeMap

• TreeMap存储Key-Value 对时，需要根据key-value对进行排序。TreeMap可以保证所有的Key-Value 对处于有序状态。
• TreeSet底层使用红黑树结构存储数据

TreeMap的Key的排序：

• 自然排序：TreeMap的所有的Key 必须实现Comparable接口，而且所有的Key应该是同一个类的对象，否则将会抛出ClasssCastException
• 定制排序：创建TreeMap时，传入一个Comparator 对象，该对象负责对TreeMap中的所有key 进行排序。此时不需要Map 的Key实现Comparable 接口
• TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。

HashTable

• Hashtable是个古老的Map 实现类，JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的。
• Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
• 与HashMap不同，Hashtable不允许使用null 作为key和value
• 与HashMap一样，Hashtable也不能保证其中Key-Value 对的顺序
• Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。

Properties

• Properties 类是Hashtable的子类，该对象用于处理属性文件
• 由于属性文件里的key、value都是字符串类型，所以Properties 里的key和value都是字符串类型
• 存取数据时，建议使用setProperty(String key,Stringvalue)方法和getProperty(String key)方法

        //文件路径默认在module下
        Properties prop = new Properties();
        FileInputStream is = new FileInputStream("jdbc1.properties");
        prop.load(is);

        String name = prop.getProperty("name");
        String age = prop.getProperty("age");
        System.out.println(name + "  "+age);
1
2
3
4
5
6
7
8

Collections 工具类

• 操作数组的工具类：Arrays

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

• Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

• 排序操作：（均为static方法）

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

• 额外的方法：

  • Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素

  • Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素

  • Object min(Collection)

  • Object min(Collection，Comparator)

  • int frequency(Collection，Object)：返回指定集合中指定元素的出现次数

  • void copy(List dest,List src)：将src中的内容复制到dest中

  • boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值

copy 方法演示：

public class MapTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        
        // ArrayList