JavaDS —— 二叉搜索树、哈希表、Map 与 Set

前言

我们将学习 Map 与 Set 这两个接口下的 TreeMap 与 TreeSet ，HashMap 与 HashSet ，在学习这四个类使用之前，我们需要先学习 二叉搜索树与 哈希表的知识。

二叉搜索树

在学习二叉树的时候，我们就已经了解过二叉搜索树的概念与性质，性质我们来回顾以下：

二叉搜索树（Binary Search Tree），也称为二叉查找树或二叉排序树，是一种特殊的二叉树。它的定义基于以下性质：

若它的左子树不空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不空，则右子树上所有节点的值都大于根节点的值。
它的左、右子树也分别为二叉搜索树。
此外，二叉搜索树的一个重要特性是它的中序遍历结果一定是有序的。这意味着在二叉搜索树中，如果按照中序遍历的方式访问所有节点，将得到一个有序的节点值序列。‌

二叉搜索树的这些性质使得它在数据检索、排序等算法中具有高效性，尤其是在需要频繁查找、插入或删除数据的场景中，二叉搜索树的操作效率通常优于其他数据结构。

现在我们来模拟实现二叉搜索树，先创建好类：

public class BinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

搜索

搜索可以类比成二分查找，当根节点数值大于要查找的数值，就去左子树继续查找，当根节点的数值小于要查找的数值，就去右子树继续查找。

    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == key) {
                return cur;
            } else if(cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

当二叉搜索树是一颗均匀分布的完全二叉树时，搜索的时间复杂度最佳，为O(logN)
当二叉搜索树为一颗单分支的树，此时搜索效率最差，为O(N)

插入

插入和搜索类似。

这里要注意的是，如果插入的数值已经存在于二叉树中，就不能继续插入，也就是说二叉搜索树只能保存一份数据，无法保存两份及以上的相同的数据。

    public void insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
            return;
        }
        
        TreeNode cur = root;
        TreeNode prev = null;

        while(cur != null) {
            if(cur.val == key) {
                return;
            } else if(cur.val > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }

        if(key > prev.val) {
            prev.right = node;
        } else {
            prev.left = node;
        }
    }
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 void remove(int key) {
        TreeNode prev = null;
        TreeNode cur = root;

        while(cur != null) {
            if(cur.val > key) {
                prev= cur;
                cur = cur.left;
            } else if(cur.val < key) {
                prev= cur;
                cur = cur.right;
            } else {
                removeNode(prev,cur);
                return;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分情况讨论：del 左子树为空，del 右子树为空，del 左右子树均不为空。

当del 左子树为空：del 有两种情况，一个是在 parent 的左边，另一种是在 parent 的右边，根据不同的情况我们直接将del 的右子树直接连接到 parent 左/右 上
这里要注意如果 del 是根节点的话，我们的 root 就要改变。

        if(del.left == null) {
            if(del == root) {
                root = del.right;
            } else if(parent.left == del) {
                parent.left = del.right;
            } else {
                parent.right = del.right;
            }
        }
1
2
3
4
5
6
7
8
9

当del 右子树为空：del 有两种情况，一个是在 parent 的左边，另一种是在 parent 的右边，根据不同的情况我们直接将del 的左子树直接连接到 parent 左/右 上
这里要注意还有第三种情况如果 del 是根节点的话，我们的 root 就要改变。

        else if(del.right == null) {
            if(del == root) {
                root = del.left;
            } else if(parent.left == del) {
                parent.left = del.left;
            } else {
                parent.right = del.left;
            }
        }
1
2
3
4
5
6
7
8
9

---

第三种情况： del 的左右子树均不为空

在这种情况下，直接去删除这个结点是一件很麻烦的事情，如果采用直接删除，我们需要重新在其子树找到合适的结点，然后将其变为新的双亲结点 ，并且要连接好两颗子树。

因此为了方便，我们采用替换删除法，替换删除法是找到一个合适的结点，将这个结点的数值直接覆盖到你要删除的结点的数值域里，这样就变相删除了这个结点，然后再将这个合适的结点删除掉。

什么是合适的结点？
由于这是一颗二叉搜索树，所以该树的根节点大于左子树，小于右子树，所以合适的结点就要满足这两个条件，比左子树的大，比右子树的小
这个合适的结点是从要删除的结点的左子树或者右子树出发寻找，根据二叉搜索树的性质，根节点的左子树任意结点都比根节点的右子树任意结点小，那么我们只要找到左子树最大的结点的数值将其覆盖到要删除结点的数值。而左子树的最大结点为左子树最右边的结点
如果是从右子树出发，那我们就要寻找到右子树的最小结点，也就是右子树的最左边的结点。

这里我以找寻右子树最左边的结点为例子：
这里要注意如果 while 循环没有进去，也就是 prev = del，cur = del.right；那么 prev 的右边是否为 cur
如果循环进去了，那结果就是 prev 的左边为 cur
所以最后删除的时候要分类讨论一下。

		else {
            TreeNode prev = del;
            TreeNode cur = del.right;
            while(cur.left != null) {
                prev = cur;
                cur = cur.left;
            }

            del.val = cur.val;
            if(prev.right == cur) {
                prev.right = cur.right;
            } else {
                prev.left = cur.right;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

removeNode 最终代码：

    private void removeNode(TreeNode parent,TreeNode del) {
        if(del.left == null) {
            if(del == root) {
                root = del.right;
            } else if(parent.left == del) {
                parent.left = del.right;
            } else {
                parent.right = del.right;
            }
        } else if(del.right == null) {
            if(del == root) {
                root = del.left;
            } else if(parent.left == del) {
                parent.left = del.left;
            } else {
                parent.right = del.left;
            }
        } else {
            TreeNode prev = del;
            TreeNode cur = del.right;
            while(cur.left != null) {
                prev = cur;
                cur = cur.left;
            }

            del.val = cur.val;
            if(prev.right == cur) {
                prev.right = cur.right;
            } else {
                prev.left = cur.right;
            }
        }
    }
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

Map 与 Set 的简单介绍

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。

回顾之前我们学习到的搜索，假设有一组数据，需要查找某一个数据的时候，我们会考虑到两种方法，一种是直接遍历，时间复杂度为O(N) ，另一种是二分查找，时间复杂度为O(logN)，二分查找的前提是数据必须是有序的。

上面两种查找方式比较适合静态类型的查找，即一般不会对数据有插入和删除的操作

但是在现实中，我们的查找有：
1.根据姓名查找个人信息
2.找到不重复的集合，即筛选掉重复的数据，只保留一份数据。

这些查找可能会伴随一些插入和删除的操作，这就是动态查找，那么我们就不适合使用上面两种静态查找的方式了，这时候Java 给我们提供了两个容器 Map 和 Set 两个适合动态查找的容器。

两个模型

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

1.纯 key 模型
比如：有一个英文词典，快速查找一个单词是否在词典中
快速查找某个名字在不在通讯录中

2.Key-Value 模型
比如：统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
Map中存储的就是key-value的键值对，Set中只存储了Key。

哈希表

概念

在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：
插入元素:
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素

搜索元素：
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

举个例子：现在有一组数据 { 1，5，9，2，4，7}
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
存储空间大小为 10

在存储的时候，我们按照哈希函数来确定数据的具体位置，在搜索的时候，将要搜索的元素通过哈希函数计算出具体的下标，然后直接去该处拿去元素。

可见哈希表的存储和搜索的时间复杂度为 O(1)

冲突

概念

对于两个数据元素的关键字 a 和 b ,在进行插入的时候，通过哈希函数的计算，发现Hash(a) 等于Hash(b) ，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

避免冲突 —— 哈希函数设计

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数设方法:
1.直接定制法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

当我们事先直到数据的分布情况，我们可以朝着线性分布的方向继续设计哈希函数，也就是一次函数Hash（Key）= A*Key + B，让数据在哈希表中分布均匀。

2.除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3.平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4.折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。

通常应用于关键字长度不等时采用此法

6.数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

负载因子调节（重点）

哈希表的负载因子定义为 a = 填入表中的元素个数 / 散列表的长度

现在我们来看一下负载因子和冲突率的关系图：

可以得出一个结论：当负载因子越大，冲突率就会越高，而负载因子的大小又与填入表中元素的个数成正比。

对于开放定址法，负载因子是一个很关键的因素，应该严格限制在 0.7 - 0.8以下。超过0.8，查表是的CPU 缓存不命中（cache missing） 按照指数曲线上升。
在 Java 的 hash 库中，负载因子被定义在 0.75，一旦超过这个数值，就会对哈希表进行扩容

解决冲突

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

1. 线性探测
   线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
   通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

举个例子：在上面我们已经插入了一组数据 { 1，5，9，2，4，7}

现在又要插入一个数据，这个数据是 17，由于 hash(17) = 17 & 10 = 7，而 7 下标已经插入了数据，这时候会发生哈希冲突，使用线性探测，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，发现 8 下标的位置为空，那么我们直接将 17 插入到 8 小标里面。

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他
元素的搜索。比如删除元素7，如果直接删除掉，17查找起来可能会受影响，因为 17 的哈希值为 7 ，但是 7 下标没有数据，那计算机到底是认为存在17 还是不存在 17 呢？因此线性探测采用标记的伪删除法来删除一个元素。

线性探测的缺陷是产生冲突的数据堆积在一块，这与其 找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找

2. 二次探测
   因此二次探测为了避免线性探测的问题，找下一个空位置的方法为： H = ( H0 + i ^2 ) % m 或者 H = ( H0 - i ^2 ) % m，其中 i = 1、2、3…，H0 是通过哈希函数 Hash(x) 对元素的关键码 key 进行计算得到的位置，m 为表的长度。

举个例子，还是插入17 这个元素，使用二次探测法插入：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

开散列/哈希桶（重点）

开散列法又叫链地址法(开链法)，也就是数组加链表的形式，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

那么在上面讨论 17 应该插入在哪个位置，如果使用链地址法，应该放在 7 的后面，如下图：

冲突严重时的解决办法

刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

1.每个桶的背后是另一个哈希表
2.每个桶的背后是一棵搜索树

模拟实现哈希表

由于Java 自己的hash 库使用的是 链地址法，所以这里我使用数组加单链表的方法来模拟哈希表，并且负载因子和 Java 的 0.75 设置一致，哈希函数我设置为 hash(x) = key % 数组长度
并且插入结点采用头插法
模拟 key - val 模型

public class Hash {
    static class Node {
        int key;
        int val;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] elem = new Node[10];
    private int useSize;

    private static final double DEFAULT_LOAD_FACTOR = 0.75;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

扩容

当负载量超过负载因子的时候，我们就要扩容，我们先写一个方法用于检测目前的负载量：

    //检测当前的负载量
    private double checkCurrentLoad() {
        return useSize * 1.0 / elem.length;
    }
1
2
3
4

然后我们来写扩容方法，注意哈希表不是简单的扩容，扩容意味着原本哈希表存放的数据就要进行移动，使之与新表匹配，所以我们先创建一个新数组，然后遍历旧哈希表，将所有结点移动到新哈希表上，最后改变 elem 的引用，就是实现了哈希表的扩容。

    private void resize() {
        Node[] newArray = new Node[elem.length * 2];

        for (int i = 0; i < elem.length; i++) {
            Node cur = elem[i];
            while(cur != null) {
                Node curN = cur.next;

                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;

                cur = curN;
            }
        }

        elem = newArray;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入

我们先插入数据，这里要注意哈希表不能存放两份及以上的相同的 key ，如果有，则会更新 val 值
这里采用头插法
等到插入完成后，要判断此时是否超出负载因子的设置范围，如果超过了，则要进行扩容。

    //插入数据
    public void put(int key,int val) {

        //是否已经存在 key ,存在则更新 val 值
        int index = key % elem.length;
        Node cur = elem[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        //头插法
        Node node = new Node(key, val);
        node.next = elem[index];
        elem[index] = node;
        useSize++;

        //检测是否超过负载因子
        if(checkCurrentLoad() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }
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

获取 val

直接通过哈希函数获取 key 所在下标，然后遍历这个下标的链表，获取 val 值

    //获取 val 值
    public int get(int key) {
        int index = key % elem.length;
        Node cur = elem[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12

泛型类哈希表模拟

在获取key 位置的时候，我们不能直接直接通过 key % 数组长度 来获取，因为 key 此时是 泛型，但是我们可以通过 hashCode() 方法来得知它的哈希值，哈希值是整型，所以我们可以利用哈希值来算 key 的下标

在比较两个泛型结点的 key 是否相同的时候，我们不能直接使用 == ，而是要使用 equals 来比较两个泛型的内容相不相同。

所以我们在使用 HashMap 或者 HashSet 的时候，如果插入的是自定义类型，那这个自定义类型就啊哟重写好 hashCode() 和 equals 两个方法！！！

public class hash2<K,V> {

    static class Node<K,V> {
        K key;
        V val;
        Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node<K,V>[] elem = new Node[10];
    private int useSize;

    private static final double DEFAULT_LOAD_FACTOR = 0.75;

    //插入数据
    public void put(K key,V val) {

        //是否已经存在 key ,存在则更新 val 值
        int index = key.hashCode() % elem.length;
        Node<K,V> cur = elem[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        //头插法
        Node<K,V> node = new Node<>(key,val);
        node.next = elem[index];
        elem[index] = node;
        useSize++;

        //检测是否超过负载因子
        if(checkCurrentLoad() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    private void resize() {
        Node<K,V>[] newArray = new Node[elem.length * 2];

        for (int i = 0; i < elem.length; i++) {
            Node<K,V> cur = elem[i];
            while(cur != null) {
                Node<K,V> curN = cur.next;

                int index = cur.key.hashCode() % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;

                cur = curN;
            }
        }

        elem = newArray;
    }

    //检测当前的负载量
    private double checkCurrentLoad() {
        return useSize * 1.0 / elem.length;
    }

    //获取 val 值
    public V get(K key) {
        int index = key.hashCode() % elem.length;
        Node<K,V> cur = elem[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        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
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

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。

Map 与 Set 的使用

在上面，大家已经了解到 二叉搜索树和哈希表，现在我们来学习 Map 与 Set 的使用。

在讲解之前，我们先讨论一个问题，二叉搜索树的搜索的时间复杂度有好有坏，我们该如何将二叉搜索树的性能变成最好的？当二叉搜索树是一颗完全二叉树的时候，性能是最佳的，那如何保持为完全二叉树，这时候就需要将二叉搜索树调整为平衡树，如何调整？答案就是使用红黑树这个数据结构维持，它能让二叉树保持为一个平衡树，也就是无论是插入还是删除，红黑树始终能让二叉树保持为一个平衡树。

在Java 中提供的哈希表是使用链地址法，也就是数组加链表，还有加红黑树，即哈希表等于 数组 + 链表 + 红黑树 ，Java 的哈希表一旦数组长度超过 64 并且链表长度超过 8 ，就会通过红黑树将链表进行树化调整为红黑树，保持哈希表优秀的性能

平衡树与红黑树会在后序文章中讲解，大家尽情期待~~

下面我们来看一下 Map 与 Set 两个接口的情况：

Map 的使用

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

---

注意事项：

1.Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

2.Map中存放键值对的Key是唯一的，value是可以重复的

3.在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，并且key 必须是可比较的，value可以为空。但是HashMap的key和value都可以为空。

4.Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。

5.Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。

6.Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

---

TreeMap 与 HashMap

Map 常用方法

代码演示：

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        map.put("abcd",123);
        map.put("hello",64);
        map.put("world",256);
        map.put("error",1024);

        System.out.println("size: " + map.size());

        System.out.println("hello: " + map.get("hello"));

        System.out.println(map.containsKey("ab"));

        System.out.println(map.containsValue(256));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        map.put("abcd",123);
        map.put("hello",64);
        map.put("world",256);
        map.put("error",1024);
        map.put("null",1024);

        System.out.println(map.entrySet());

        map.remove("abcd");

        System.out.println("======================");
        
        System.out.println(map.entrySet());
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        map.put("abcd",123);
        map.put("hello",64);
        map.put("world",256);
        map.put("error",1024);
        map.put("null",1024);

        Set<Map.Entry<String,Integer>> set = map.entrySet();

        for(Map.Entry<String,Integer> x: set) {
            System.out.println("key: " + x.getKey() + "val: " + x.getValue());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

keySet 方法可以返回所有 key 的不重复合集，可以使用 Set 来接收
如果想接收所有的 values 包括重复的 values 的合集，可以使用 Collection 来接收

---

Map.Entry<K,V>

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        map.put("abcd",123);
        map.put("hello",64);
        map.put("world",256);
        map.put("error",1024);
        map.put("null",1024);

        Set<Map.Entry<String,Integer>> set = map.entrySet();

        for(Map.Entry<String,Integer> x: set) {
            x.setValue(10256);
        }

        System.out.println("======================");
        System.out.println("检测将每个键值对的 value 设置为 10256是否成功");

        for(Map.Entry<String,Integer> x: set) {
            System.out.println("key: " + x.getKey() + "   val: " + x.getValue());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Set 的使用

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

注意事项：
1.Set是继承自Collection的一个接口类

2.Set中只存储了key，并且要求key一定要唯一

3.TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

4.Set最大的功能就是对集合中的元素进行去重

5.实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6.Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入

7.TreeSet中不能插入null的key，HashSet可以。

---

TreeSet 与 HashSet

---

Set 常用方法

代码演示：

    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(10);
        treeSet.add(100);
        treeSet.add(85);
        treeSet.add(32);

        System.out.println(treeSet.contains(100));

        Iterator<Integer> it = treeSet.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();

        System.out.println("======演示删除======");
        
        treeSet.remove(100);

        it = treeSet.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();

        System.out.println(treeSet.size());

        System.out.println(treeSet.isEmpty());

        Integer[] arr = (Integer[])treeSet.toArray(new Integer[0]);

        for (int x: arr) {
            System.out.print(x+"  ");
        }
    }
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

Java 的 HashMap 部分源码解析

构造方法

将默认 初始容量为 16，将负载因子设置为 默认值 0.75

---

调用了另一个构造方法来设置初始容量，但是负载因子还是设置为默认值 0.75

---

可以设置初始容量以及负载因子。

        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
1
2
3
4
5

当默认容量小于 0 会抛异常，当初始容量 大于 最大的默认容量也会抛异常。

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
1
2
3

当负载因子小于 0 或者负载因子不是数字 就会抛异常

下面是 isNaN 的源码：

现在我们来看一下 this.threshold = tableSizeFor(initialCapacity);是如何设置初始容量的：

返回给定目标容量的2次幂。
举个例子，如果你设置的初始容量为 10，经过一顿操作，实际设置的初始容量为 2 ^ 4 = 16

---

put

下面是 哈希表 的数组：

但是在此之前我们都没有看到一个数组的创建，实际上 数组的创建会在 put 方法里体现：

put 方法传入了 hash(key)：

通过 (h = key.hashCode()) ^ (h >>> 16) 会使 Key 分布的更均匀

---

put 方法 调用了 putVal 方法：

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
1
2

当数组为 null 或者 数组的长度为 0 就会扩容。

        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
1
2

当 key 的哈希值 所在的存储位置为空时，直接插入结点。

---

走到这里的时候，说明这个哈希值对应的数组的位置已经被插入了

Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
1
2
3

当哈希值是相同 并且 一个已经被插入的结点的 key 和待插入的结点的 key 的地址是相同，又或者 key 不是空并且 两个的 key 的内容是相同的话，就将待插入的结点赋值给 e 。

---

如果不满足上面的条件，就说明这个结点是一个要插入到 链表或者红黑树的结点，因此下面中的p instanceof TreeNode 会判断此时数组存储的是 链表还是红黑树，如果是红黑树， e 就是一个红黑树的结点，并通过 putTreeVal() 方法来将 结点插入到红黑树中。

else if (p instanceof TreeNode)
    	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
1
2

---

走到这里，说明需要需要在链表里插入新结点。

下面就是链表的插入代码：

else {
       for (int binCount = 0; ; ++binCount) {
               if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                }
                if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                    p = e;
                }
            }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

要注意其中这一行代码：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
1
2

这行代码是判断是否需要将链表调整为红黑树。

put 源码分析到这里，感兴趣可以继续往下分析

get

调用了 getNode() 方法：

if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & (hash = hash(key))]) != null) 
1
2

先判断这个 key 是否存在，从数组不为空并且数组长度不为 0 并且 key 的哈希值所在的 数组位置不为空，才会继续寻找，否则直接返回 null

---

if (first.hash == hash && // always check first node
   ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
1
2
3

检查是不是第一个结点，是的话直接返回，不是的话，说明在第一个结点后面的结点，需要继续寻找。

---

if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
     }
1
2
3
4
5
6
7
8
9

当第一个结点后面存在下一个结点才继续寻找，first instanceof TreeNode 是 true 说明第一个结点是树结点，说明数组连接的是红黑树，那么就会通过红黑树的搜索方法getTreeNode 来进行搜索，如果不是则是以链表的形式进行搜索。