Map、Set和哈希表（数据结构系列14）网站首页 技术杂谈

//定义一个静态内部类
    static class TreeNode{
        public int val;
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;//定义一个根节点

1.2插入

我们在搜索树中进行插入操作的话，我们就要先找到要插入的位置，我们根据搜索树的特点来看，左孩子的值要小于根结点的值，右孩子的值要大于根节点的值，那么我们的核心思想就是：if(cur.val < val) 我们就让 cur = cur.right,与此同时我们还要记录一下cur的父结点的位置，因为我们要查找的话就一定是一个循环结构的操作，那么我们的结束条件就一定是cur == null, 所以我们要记录一下上一个位置，防止丢失，同理如果cur.val > val的时候我们就让cur = cur.left ，同时让parent = cur。这样我们就可以找到要插入的位置了。

找到插入的位置之后在去判断parent的值和要插入的值的大小，来确定是要插入到parent的左边还是右边。

示意图如下所示：

代码如下所示：

/**
     * 插入一个数据
     */
    public void insert(int val) {
        //如果当前树为一颗空树
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        //如果不是一颗空树，那么我们就需要遍历这颗树，然后按照搜索树的特点来进行插入。
        TreeNode cur = root;
        TreeNode parent = null;//用来记录cur结点的父结点
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //出来之后我们就找到了要插入的位置了。
        TreeNode node = new TreeNode(val);//定义一个结点
        if (parent.val < val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
    }

1.3查找

其实我们在上述插入的过程中已经用到了查找了，这里小编就不再做过多的说明了，大家可以直接看代码。

    /**
     * 查找二叉树中指定的val值
     */
    public TreeNode find(int val) {
        TreeNode cur = root;//当前遍历到的结点
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            }else if (cur.val == val) {
                return cur;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

1.4删除

删除操作在搜索树中是比较难的，这里删除我们一共分为三大块：
1.cur.left == null

cur是root，则root = cur.right。
cur不是root，cur是parent.left，则parent.left = cur.right。
cur不是root，cur是parent.right，则parent.right = cur.right。

示意图如下所示：

2.cur.right == null

cur是root，则root = cur.left。
cur不是root，cur是parent.left，则parent.left = cur.left。
cur不是root，cur是parent.right，则parent.right = cur.left。

示意图如下所示：

3.cur.left != null && cur.right != null

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除结点中，再来处理该结点的删除问题。

示意图如下所示：

删除代码如下所示：

    /**
     * 删除值为val的结点
     */
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        //查找到要删除的结点的位置
        while (cur != null) {
            if (cur.val == val) {
                removeNode(parent,cur);//删除操作的代码
                return;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        //1.cur.left == null
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }else if (parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //此时cur.left != null && cur.right != null
            //使用替换法来完成
            //我们需要在最
            TreeNode target = cur.right;
            TreeNode targetP = cur;
            while (target.left != null) {
                targetP = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetP.left) {
                targetP.left = target.right;
            }else {
                targetP.right = target.right;
            }
        }
    }

1.5二叉搜索树整体代码展示

整体代码：

package Map和Set博客发布代码;

public class BinarySearchTree {
    //定义一个静态内部类
    static class TreeNode{
        public int val;
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;//定义一个根节点

    /**
     * 查找二叉树中指定的val值
     */
    public TreeNode find(int val) {
        TreeNode cur = root;//当前遍历到的结点
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            }else if (cur.val == val) {
                return cur;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }

    /**
     * 插入一个数据
     */
    public void insert(int val) {
        //如果当前树为一颗空树
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        //如果不是一颗空树，那么我们就需要遍历这颗树，然后按照搜索树的特点来进行插入。
        TreeNode cur = root;
        TreeNode parent = null;//用来记录cur结点的父结点
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //出来之后我们就找到了要插入的位置了。
        TreeNode node = new TreeNode(val);//定义一个结点
        if (parent.val < val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
    }

    /**
     * 中序遍历输出该搜索树
     */
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    /**
     * 删除值为val的结点
     */
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        //查找到要删除的结点的位置
        while (cur != null) {
            if (cur.val == val) {
                removeNode(parent,cur);//删除操作的代码
                return;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        //1.cur.left == null
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }else if (parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //此时cur.left != null && cur.right != null
            //使用替换法来完成
            //我们需要在最
            TreeNode target = cur.right;
            TreeNode targetP = cur;
            while (target.left != null) {
                targetP = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetP.left) {
                targetP.left = target.right;
            }else {
                targetP.right = target.right;
            }
        }
    }
}

package Map和Set博客发布代码;

public class Main {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        //以插入的方式构造一颗搜索树
        binarySearchTree.insert(5);
        binarySearchTree.insert(3);
        binarySearchTree.insert(7);
        binarySearchTree.insert(1);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(8);
        binarySearchTree.insert(0);
        binarySearchTree.insert(2);
        binarySearchTree.insert(9);

        //以中序遍历输出二叉搜索树
        System.out.println("该二叉搜索树为：");
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();
        //删除一个结点
        binarySearchTree.remove(4);
        System.out.println("删除结点4之后的二叉搜索树为：");
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();
        //查找一个结点
        System.out.println("查找结点5是否存在：");
        BinarySearchTree.TreeNode ret = binarySearchTree.find(5);
        System.out.println(ret.val);
    }
}

运行结果：

那么我们的二叉搜索树和我们要给大家介绍的Map和Set又有什么关系呢？我们先来看一下下面的这张图。

在上图中我们可以看到TreeSet和TreeMap分别继承了Set和Map接口，其实他们的底层就是一颗搜索树，只不过他比我们现在学习的二叉搜索树要更加复杂一点，它的底层用的是红黑树，而红黑树是一颗近似平衡的二叉搜索树，即在二叉搜索树的基础之上+颜色以及红黑树的性质验证，感兴趣的同学可以自己去学习一下。那么接下来小编就给大家来介绍一下Map和Set的一些基本知识点，以及如果使用他们。

2. Map和Set的讲解

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

直接遍历，时间复杂度为O(N)，元素如果比较多效率就会非常慢。
二分查找，时间复杂度为O(logN)，但搜索前必须要求序列是有序的。

上述的两个都比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，现实中的查找比如：

根据姓名查寻考试成绩。
通讯录，即根据姓名查询联系方式。
不重复集合，即需要先搜索关键字是否已经在集合中。

可能在查找时进行一些插入和删除操作，即动态查找，那上述两种方式就不太适合了，所以我们这里就给大家来介绍Map和Set一种适合动态查找的集合容器。我们一般把搜索的数据称之为关键字（key），和关键字所对应的称之为值（value），将其称之为key-value的键值对。

这里我们有两种模型：
1.纯key模型
比如：

有一个英文词典，快速查找一个单词是否在词典中。
快速查找某个名字在不在通讯录中。

2.key-value模型

比如：

统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号，比如及时雨-宋江。

而Map中存储的就是key-value的键值对，Set中只存储了key。

2.1 Map的说明

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

2.1.1Map的方法

方法	解释
V get(Object Key)	返回key对应的value
V getOrDefault(Object key, V defaultValue)	返回key对应的value，key不存在，返回默认值
Vput(K key, V value)	设置key对应的value
V remove(Object key)	删除key对一个的映射关系
Set<K> keySet()	返回所有key的不重复集合
Collection<V>values()	返回所有value的可重复集合
Set<Map.Entry<K,V>>entrySet()	返回所有的key-value映射关系
boolean containsKey(Object key)	判断是否包含key
boolean containsValue(Object vaule)	判断是否包含value

注意：

Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者是HashMap
Map中存放键值对的key是唯一的，value是可以重复的。
在TreeMap中插入键值对时，key不能为空，否则就会抛出NullPointerException异常，value可以为空，但是HashMap的key和value都可以为空。
Map中的key可以全部分离出来，存储到Set中来进行访问（因为Key不能重复）。
Map中的value可以全部分离出来，存储在Collection的任何一个子集合中（value可能有重复）。
Map中的键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将key删除掉，然后再来进行重新插入。

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

方法	解释
V getKey()	返回entry中的key
V getValue()	返回entry中的value
V setValue(V value)	将键值对中的value替换为指定value

注意：Map.Entry<K,V>没有提供设置key的方法。

Map方法代码演示：

package Map和Set博客发布代码;

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapTest {
    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        //put()：插入一个键值对。
        treeMap.put("hello", 3);
        treeMap.put("world", 4);
//        treeMap.put(null, 6); //会报错误NullPointerException
        System.out.println(treeMap);//TreeMap重写了toSting方法，以键值对的形式打印出来
        //{hello=3, world=4}
        //get()：获取key，并返回对应的value值。
        Integer val = treeMap.get("hello");//返回3
        System.out.println(val);

        //getOrDefault()：获取key有则返回对应的value值，没有则返回默认值。
        Integer val2 = treeMap.getOrDefault("hello world", 100);
        System.out.println(val2);//返回100

        //Set<K> keySet()：返回所有key的不重复集合
        Set<String> keySet = treeMap.keySet();
        System.out.println(keySet);//[hello, world]

        //Set<Map.Entry<K,V>>entrySet()：返回所有key-value映射关系
        Set<Map.Entry<String,Integer>> set = treeMap.entrySet();
        for (Map.Entry<String,Integer> entry : set) {
            System.out.println("key:" + entry.getKey() + " value:" + entry.getValue());
        }
        //key:hello value:3
        //key:world value:4
    }
}

结果展示：

2.2 Set 的说明

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

2.2.1Set的方法

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断o是否在集合中
Iterator<E> iterator()	返回迭代器
boolean remove(Object o)	删除集合中的o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection<?>c)	集合中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E >c)	将集合c中的元素添加到set中，可以达到去重的效果

set方法代码演示：

package Map和Set博客发布代码;

import java.util.Set;
import java.util.TreeSet;

public class SetTest {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        //add():添加元素
        set.add("hello");
        set.add("world");
        set.add("world");
//        set.add(null); //不可以添加null否则就会报：NullPointerException
        System.out.println(set);
        //[hello, world]

        //contains(): 判断元素是否在集合中
        System.out.println(set.contains("hello"));//true

        //set(): 删除集合中的元素
        set.remove("world");
        System.out.println(set);//[hello]

        //返回集合中的元素个数
        System.out.println(set.size());//1

        //isEmpty(): 检测set是否为空
        System.out.println(set.isEmpty());//false

        //toArray(): 将set中的元素转化为数组返回
        //先来添加几个元素
        set.add("the");
        set.add("world");
        set.add("dog");
        Object[] strings = set.toArray();
        for (Object e : strings) {
            System.out.print(e + " ");
        }

    }
}

结果展示：

注意：

set是继承自Collection的一个接口类。
Set中只存储了key，并且要求key一定要唯一。
TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的。
Set最大的功能就是对集合中的元素去重。
实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入。
TreeSet中不能插入null的key，但HashSet中可以。

3.哈希表

3.1哈希表的概念

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

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

当向该结构中：

插入元素：

根据插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。

搜索元素：

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

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

例如：数据集合{1,7,4,5,9}；

哈希函数设置为：hash（key） = key % capacity；capacity为存储元素底层空间总大小。

我们使用以上方法进行搜索就不必进行多次关键码的比较，因此搜索速度比较快，但是按照上述的哈希方式进行插入的话，那么如果要插入的元素是44，会出现什么问题呢？

3.2哈希冲突

对于我们上述提出的问题相信大多数同学都会发现，如果还是按照上述的哈希函数继续进行插入的话那么44和4就会发生冲突，也就是说对于两个元素的关键字k1和k2，有k1 != k2，但有hash（k1） = hash（k2）,即不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突碰撞。我们把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

为什么会出现这种冲突呢？

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

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

当然设计哈希函数就不在我们所考虑的范围内了。

那么我们又该如何避免这种情况的发生呢？

3.3冲突的避免

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

那么我们又该怎么降低这个冲突率呢？

这里就需要大家先来明确一个概念叫做负载因子。

散列表的载荷因子定义为：荷载因子 = 填入表中的元素个数 / 散列表的长度。

一般对于开方定址法，荷载因子是特别重要的，应严格限定在0.7 - 0.8以下。在Java的系统库限定了荷载因子为0.75，超过此值将resize散列表。

对于开方定址法小编下面来给大家慢慢解释。

那么基于上述的荷载因子的定义我们要想避免上述问题，那么我们就可以通过调节散列表的长度来避免冲突。

3.4哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列。那么接下来小编就来给大家介绍一下它两分别是什么。

3.4.1闭散列

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

① 线性探测

比如上面我们提出的那个问题，当我们需要插入44的时候我们该插哪里呢？通过线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

注意：
采用闭散列处理哈希冲突时，不能随意物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，比如删除元素4，如果直接删掉，44查找起来可能会受到影响，因此线性探测采用标记的伪删除来删除一个元素，比如1代表删除，0代表没有删除。

② 二次探测

线性探测的缺陷是产生冲突数据堆积在一起，这与其找下一空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次线性探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i ^ 2) % m，或者Hi = （H0 - i^2）% m。其中i = 1,2,3...，H0是通过散列函数hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。

3.4.2开散列

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

针对于上述的值我在加入几个值以便于我们更好的理解开散列的存储方法。

在我们的Java中的HashMap就采用的是这种方法。接下来我们自己来实现一下。

代码展示：

package Map和Set博客发布代码;

public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;//存储链表的数组
    public int usedSize;//使用的空间大小

    public static final double LOAD_FACTOR = 0.75;//定义荷载因子
    public HashBuck() {
        array = new Node[10];//初识化数组的长度
    }

    /**
     * 放值
     */
    public void put(int key, int val) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //采用头插法进行插入
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (calculateLoadFactor() >= LOAD_FACTOR) {
            //扩容
            resize();
        }
    }

    //计算负载因子
    private double calculateLoadFactor() {
        return usedSize * 1.0 / array.length;
    }

    private void resize() {
        Node[] newArray = new Node[2 * array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null){
                Node curNext = cur.next;
                int index = cur.key % newArray.length;//找到了在新的数组中的位置
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }

    /**
     * 获取值
     */
    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}

package Map和Set博客发布代码;

public class HashBuckMain {
    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(1,11);
        hashBuck.put(2,22);
        hashBuck.put(5,55);
        hashBuck.put(8,88);
        hashBuck.put(3,33);
        hashBuck.put(14,144);
        hashBuck.put(7,77);
        Integer val = hashBuck.get(7);
        System.out.println(val);
    }
}

结果展示：