数据结构之详解【Map和Set】_set和map数据结构

目录

1. 对Map和Set的理解

2. Map的使用

​编辑

 2.1 Map的常用方法

 2.2 TreeMap和HashMap的区别

3. Set的使用

 3.1 Set的常用方法

3.2 练习一下

3.3 TreeSet和HashSet的区别

4.二叉搜索树（Binary Search Tree）

4.1 概念

4.2 二叉搜索树 — 查找

4.3 二叉搜索树 — 插入（重点）

4.4 二叉搜索树 — 删除（难点）

5. 哈希表

5.1 哈希表的理解

5.2 哈希冲突 

5.3 哈希冲突降低之 哈希函数设计

5.4 哈希冲突降低之 负载因子调节

5.5 哈希表冲突解决之 闭散列

5.6 哈希表冲突解决之 开散列

---

1. 对Map和Set的理解

（1）概念

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

Map和Set是动态查找相比较与静态查找（比如直接查找。二分查找等），其优点是可以在查找过程中对区间进行一些插入和删除的操作。

（2）模型

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

1. 纯 key 模型：Set中存储的就是key

比如查找 某本书中是否有一个名词

2. Key-Value模型：Map中存储的就是key-value的键值对

比如统计 某本书中某几个名词出现的次数

---

2. Map的使用

 2.1 Map的常用方法

这里用Map实现TreeMap的接口

（1）put（key，value）方法   设置 key 对应的 value

给里面放key一定要是可以比较类型，并且不能为null

如果放入同样的key，那就会覆盖之前的key的value

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        System.out.println(map1);
    }

Map里面重写了toString直接打印map1，可以看到打印出来的顺序，和输入的顺序是不一样的

这是因为TreeMap底层是一个搜索树，给搜索树中插入是需要比较大小的，同key来比较大小

这里最需要注意的是，如果插入自定义类型。那么自定义类型一定要是可以比较的，并且不能为null，不然会报错

还需要注意的是

    public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        map1.put("javase",66);
        System.out.println(map1);
    }

如果放入同样的key，那就会覆盖之前的key的value

 （2）get（key）与getOrDefault（key，value）方法

打印key-value  和设置默认的key-value

public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        System.out.println(map1.get("javase"));
        System.out.println(map1.get("c++"));
        System.out.println(map1.getOrDefault("c++",45));
    }

 

 get能够将put放入的key和Value都打印出来，如果没有就打印null

getOrDefault能够能够设置一个默认的key的value，如果之前没有put这个默认的key，那就打印出这个key和设置的value

如果之前有

 （3）remove （key）删除 key 对应的映射关系

    public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        map1.remove("javaee");
        System.out.println(map1);
    }

 （4）Set<K> keySet()   返回所有 key 的不重复集合

public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        Set<String> set = map1.keySet();
        System.out.println(set);
    }

（5）Collection<V> values()   返回所有 value 的可重复集合 

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
        Collection<Integer> collection= map1.values();
        System.out.println(collection);
    }

 （6）Set<Map.Entry<K, V>> entrySet()     返回所有的 key-value 映射关系

 

 public static void main(String[] args) {
        Map<String,Integer> map1 = new TreeMap<>();
        map1.put("javase",20);
        map1.put("javaee",13);
        map1.put("javaweb",6);
 
        Set<Map.Entry<String,Integer>> entrySet = map1.entrySet();
        for (Map.Entry<String,Integer> entry : entrySet) {
            System.out.println("key: " + entry.getKey() +
                    " val: " + entry.getValue());
        }
    }

 2.2 TreeMap和HashMap的区别

1.Map是一个接口，不能直接实例化对象（要实例化对象可以实现类TreeMap或HashMap）

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

3.Map中key可以全部分离开，存储在Set中去进行访问（因为key不可以重复）

4.Map中value可以全部分离开，存储在Collection的任何一个子集合中（value可以重复）

5.Map中key不能直接修改，如果必须修改就要先删除key，在进行重新插入

6.HashMap的存储 是根据底层的哈希函数和key，去找对应的位置的，

所以HashMap不是根据存储顺序打印的，而是根据一些映射关系等存储的，那么HashMap也可以存储null

---

3. Set的使用

TreeSet当中存储的元素，必须是可以比较的 

 3.1 Set的常用方法

boolean add(key)  添加元素，但重复元素不会被添加成功

所以Set用在去掉重复的情况下

TreeSet中存储的元素必须是可以比较的

public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("qwe");
        set.add("asd");
        set.add("qwe");
        System.out.println(set);
    }

 并且实现了SortedSet的接口，所以TreeSet中存储的元素必须是可以比较的

而且 

其他方法和map使用方法类似 

---

3.2 练习一下

1.现在有100w个数据，要把这100w个数据中重复的元素删除掉

可以直接存储在set中，因为set中存储元素是将元素去重之后存储的

public static void fun1(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

2.现在有100w个数据，要把这100w个数据中第一个重复的数据找出来

将元素给集合中存储，每次存储判断一下，集合中有没有，要是有就返回这个数字

 public static int fun2(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                return array[i];
            }
        }
        System.out.println(set);
        return -1;
    }

3.现在有100w个数据，要把这100w个数据中每个数据出现的次数打印出来

将元素给集合中存储，先看key有没有，要是没有就存储key，value为1,；如果集合中有key，那就给value加1

 public static void fun3(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
           int key = array[i];
           if(map.get(key) == null) {
               map.put(key,1);
           }else {
               int val = map.get(key);
               map.put(key, val + 1);
           }
        }
    }

---

3.3 TreeSet和HashSet的区别

1.Set继承于Collection的接口类

2.Set只存储key，并且key唯一

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

4.Set的功能最重要的是集合中元素去重

5.Set中不能插入为null的key

6.Set中key不能修改，如必须修改，先删除，在重新插入

底层结构上的区别和Map类似 

---

4.二叉搜索树（Binary Search Tree）

4.1 概念

二叉搜索树（二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

（1） 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉搜索树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势

主要用于，在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作

前面都是比较正式的概念，我的理解二叉搜索树给它中序遍历他是顺序递增的

---

4.2 二叉搜索树 — 查找

先根据二叉搜索树写出它的结构

 static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
 
        public TreeNode(int val) {
            this.val = val;
        }
    }
 
    public TreeNode root;

然后分析一下它的查找方法

 /**
     * @param key:
     * @return 找到了返回地址，没找到返回null
     * @description 查找key是否存在于二叉搜索树中
     */
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

---

4.3 二叉搜索树 — 插入（重点）

 /**
     * @param key:
     * @return boolean
     * @description 插入
     */
    public boolean insert(int key) {
        //将k变成一个节点（万一树为空，那么插入这个节点，树中就有key的这个节点了）
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root;
        //parent记录cur的父亲结点
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //存在相同的元素不能插入成功
                return false;
            }
        }
        //cur一直走到最后cur为null
        if(parent.val < key) {
            parent.right = node;
        }else {
           parent.left = node;
        }
        return true;
    }

---

4.4 二叉搜索树 — 删除（难点）

和前面查找的步骤一样，看根节点是不是，然后进入到左右子树中去寻找所要删除的结点

下面分析一下要删除结点，会遇到的情况

（1）下面先分析一下，要删除结点如果一边为null，一边不为null的情况

 （2）下面分析一下，两边都不为空的情况

 将上面所有的删除情况写为一个方法

 /**
     * @param cur: 删除结点
     * @param parent:删除结点的父结点
     * @description 进行删除
     */
    private void removeNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if (cur == root) {
                root = root.left;
            }else if(cur == cur.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetParent.left == target){
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

调用上面的删除方法

 /**
     * @param key:
     * @return void
     * @description 删除关键字为key的结点
     */
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //找到了，开始删除
                removeNode(cur,parent);
                return;
            }
        }
    }

---

5. 哈希表

5.1 哈希表的理解

在普通的数据结构中查找一个关键字，通常需要遍历整个数据结构或者多次比较，查找的效率取决于搜索过程中元素的比较次数

而哈希表不同与那些数据结构

哈希表，构造的存储结构是，通过某种函数使元素的存储位置与它的关键码之间建立一种映射关系，从而可以直接通过关键码值(Key value)直接进行访问的数据结构，加快查找速度

时间复杂度O(1)

对哈希表进行操作：

插入元素：根据待插入的元素关键码，通过函数计算出该元素的存储位置，然后根据此位置存放

搜索元素：对元素的关键码进行同样的计算，把求得的函数值作为元素的存储位置，然后在这个位置取元素进行比较，如果关键码一样，那么搜索成功

 这种方法叫哈希方法或者散列方法，哈希方法中使用的转换函数称为哈希函数或散列函数

这样的结构叫哈希表或散列表 

---

5.2 哈希冲突 

 

 对于两个数据元素的关键字，通过哈希函数计算出相同的哈希地址，这种现象叫哈希冲突或哈希碰撞

把具有不同关键字而具有相同哈希地址的数据元素叫“同义词”

这种冲突是必然的，这是因为哈希表底层的数组容量往往是小于实际要存储的关键字的数量的，

所以我们要想办法降低这种冲突的概率

---

5.3 哈希冲突降低之 哈希函数设计

要想减小冲突的概率，那就要设计合理的哈希函数

哈希函数设计的原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见的哈希函数

（1）直接定制法

哈希函数：Hash(key) = A*key + B

优点是 简单、均匀       

使用前提：需要提前知道关键字的分布情况，适合于查找较小且连续的情况

（2）除留余数法

哈希函数：hash(key) = key % capacity

capacity为存储元素的底层空间的总大小

（3）平方取中法 （4）折叠法 （5）随机数法  （6）数学分析法等等

方法很多，但设计的原则就是降低哈希冲突，注意只能降低，无法避免

---

5.4 哈希冲突降低之 负载因子调节

---

5.5 哈希表冲突解决之 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满

说明在哈希表中必然还有空位置，那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去

而找“下一个”位置有两种方法：

（1）线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

缺点：线性探测将冲突的元素都放在一起,并且删除也不方便

需要注意的是线性探测不能随便删除元素，比如删除3，那么后面查找23或33，就会受到影响，因此线性探测采用标记的伪删除法来删除一个元素。

（2）二次探测 

线性探测找位置是一个一个往后找，那么二次探测为了解决这个问题，找“下一个”位置有了不同的方法       找下一个空位置的方法为Hi = (H0 + i^2) % m

缺点：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。但是在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容，这样表的空间利用率就比较低了

---

5.6 哈希表冲突解决之 开散列

开散列法也叫哈希桶、链地址法、开链法、

和前面一样，都是先计算堆关键码用哈希函数计算地址，地址一样的放在一个子集合中，

不同的是，开散列法将每一个子集合当做一个桶，然后桶中的元素通过单链表连接起来，然后将单链表的头结点存储在哈希表中

 

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

如果搜索性能还比较低，也可以继续将这个小集合搜索问题转换为

1. 每个桶的背后是另一个哈希表

2. 每个桶的背后是一棵搜索树

---