数据结构 - Map 和 Set

目录

1.概念

2.模型

3.Map

3.1 Map的常用方法

📢 V put(K key,V value) - 设置 key 对应的 value

📢 V get(Object key) - 返回 key 对应的 value

 ​编辑

📢 V getOrDefault (Object key , V defaultVaule) - 返回 key 对应的 value，如果 key 不存在则返回默认值 （defaultVaule）

 📢 V remova (Object key) - 删除 key 对应的映射关系

 📢 Set keySet() - 返回所有 key 的不重复集合

📢 Collection values() - 返回所有 value 的可重复集合

 📢 boolean containsKey(Object key) - 判断是否包含 key 

📢 boolean containsValue(Object value) - 判断是否包含 value

📢 Set> entrySet() - 返回所有的 key - value 映射关系 

4.set

4.1 Set 的常用方法

 Set （Java Platform SE 8 ） (oracle.com)

 4.2 Set 的底层实现

5. 哈希表(散列表)

5.1 概念

5.2 哈希函数

5.3 哈希函数的种类

💯 直接定址法

💯 除留余数法 - 常用

💯 平方取中法

💯 随机数法

6.冲突

6.1 概念

6.2 负载因子

 6.3 解决 - 闭散列 和 开散列

📢 闭散列

 📢 开散列 - 哈希桶

模拟实现哈希桶

hashCode() 

 7.Tree 和 Hash 的区别

1.概念

Map 和 Set 是一种专门用于搜索查找的数据结构，其搜索的效率与具体实例化的子类有关。

例如本文中主要概述的 TreeMap 和 HashMap ，TreeSet 和 HashSet。

在以往的搜索查找中，我们常使用的方式有:1.直接遍历 O(N) 2.二分查找 O(log₂N) 

这些方式适用于静态查找，何为静态查找呢？

静态查找表:只作查找操作的查找表。

  1. 查询某个“特定”数据元素是否在查找表中。
  2. 检索某个“特定”数据元素和各种属性。

动态查找表:在查找过程同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。 

  1. 查找是插入数据元素。
  2. 查找时删除数据元素。 

现实中的查找例如：

  1.  根据学生姓名查找学生成绩。
  2. 根据姓名查找联系方式。
  3. 根据商品名称查询价格。

在查询的过程中可能会进行插入和删除的操作，而 Map 和 Set 就非常适合动态查找 

 图中可以看出 Set 是实现于 Collection 接口的，而 Map 是没有实现 Collection 接口的。

2.模型

介绍 Map 和 Set 之前需要了解一下什么是模型。

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

 1. 纯 key 模型 ：没有对应的值

  • 查找某字典中某个字

2.key - value 模型：有对应的值

  • 查找字典中某个字出现的次数(key == 字，value == 次数) 

key 是唯一的，不可重复，value是可以重复的：

  • 例如网上购物，查询水杯，水杯都是一样的情况下，而价格可能是不一样的。

Map 中存储 key - value，Set 只存储 key。 

3.Map

Map 是一个接口，不能实例化，需要实例化实现他的一个子类，例如TreeMap。

Map 存储的是 Map<K,V>结构的键值对。

3.1 Map的常用方法

此处实例化的是 treeMap 对象，HashMap 在后续 Hash 中会讲到 

📢 V put(K key,V value) - 设置 key 对应的 value

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap);
    }

因为 key 是唯一不重复的，如果你设置的key 在 map 中已经存在，那么将会更新同一 key 的 value 

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("猫爪杯子",100);
        System.out.println(treeMap);
    }

 

如果你的 key 是无法进行比较的对象，那么将会抛出异常(ClassCastException - 类强制转换异常)

    static class Cup {//杯子
        String name;
        public Cup(String name) {
            this.name = name;
        }
    }
    public static void main(String[] args) {
        Map<Cup,Integer> treeMap = new TreeMap<>();
        Cup cup1 = new Cup("猫爪杯子");
        Cup cup2 = new Cup("派大星杯子");
        Cup cup3 = new Cup("海绵宝宝杯子");
        treeMap.put(cup1,10);
        treeMap.put(cup2,25);
        treeMap.put(cup3,30);
        System.out.println(treeMap);
    }

key 不能传入 null 值，value 可以传入 null值。key 传入 null 时抛出空指针异常 

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put(null,10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
    }

📢 V get(Object key) - 返回 key 对应的 value

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.get("猫爪杯子"));
    }

 

如果没有找到 key 则返回 null

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.get("杯"));
    }

 

📢 V getOrDefault (Object key , V defaultVaule) - 返回 key 对应的 value，如果 key 不存在则返回默认值 （defaultVaule）

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.getOrDefault("杯子",100));
    }

 

 📢 V remova (Object key) - 删除 key 对应的映射关系

        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        treeMap.remove("派大星杯子");
        System.out.println(treeMap);

 

 📢 Set<K> keySet() - 返回所有 key 的不重复集合

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.keySet());
    }

📢 Collection<V> values() - 返回所有 value 的可重复集合

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        treeMap.put("杯子",10);
        treeMap.put("派杯子",25);
        treeMap.put("海杯子",30);
        System.out.println(treeMap.values());
    }

 📢 boolean containsKey(Object key) - 判断是否包含 key 

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.containsKey("猫爪杯子"));
    }

📢 boolean containsValue(Object value) - 判断是否包含 value

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        System.out.println(treeMap.containsValue(99));
    }

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

    public static void main(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("猫爪杯子",10);
        treeMap.put("派大星杯子",25);
        treeMap.put("海绵宝宝杯子",30);
        for (Map.Entry<String,Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + "=" +entry.getValue());
        }
    }

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

  1.  K.getKey() - 返回 entry 中的 key
  2.  V.getValue() - 返回 entry 中的 value
  3.  V.setValue() - 修改 key 相对应的 value

4.set

Set 和 Map 很相似，不同点在于 Set 是继承于Collection 的接口类，Set 只存储 Key

4.1 Set 的常用方法

Set 的主要方法都在下方链接中，就不一一说明了。

 Set （Java Platform SE 8 ） (oracle.com)

 4.2 Set 的底层实现

Set 的 底层实际上是通过 Map 实现的，让我们来看下源码

调用 Set 的 add() 方法添加元素进去：

    public static void main(String[] args) {
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(12);
    }

 实际上调用的是 Map 的 put() 方法，那么 Set 只存储 key, put 参数内的 PRESENT 又是啥

根据源码来看是一个 Object 类，通过注释得知这是一个与后备映射中的对象关联的虚拟值。 

当我们创建结点时(这里的Map 是 TreeMap 对象，底层是一棵红黑树)，value 值时上一步中传的虚拟值 PRESENT。

5. 哈希表(散列表)

5.1 概念

在上文中实例化的都是 TreeMap 和TreeSet ,他们的底层是一棵红黑树，而红黑树的底层又是一课搜索树，查找的时间复杂度 O(log₂N) 即为树的高度，而哈希表中哈希函数可以在元素的存储位置建立与其对应的关键码，他们之前建立映射关系，使哈希表中查找的时间复杂度为 O(1)。

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

5.2 哈希函数

假定我们的函数为 hash(key) = key % capacity(存储元素底层空间大小)

当 key 为 1时，根据哈希函数求得关键码为1，key 为 2 时，关键码为 2 ，按照这样的存储方式，查找数据时根据这个哈希函数求出关键码时间复杂度就不就是O(1)吗。

问题来了，关键字为 4 、14、24、34.....等等后面的的个位数为4 的关键字key 应该存在哪？

扩容数组？

 那我只存放10个 个位数为4的key，要将数组扩容到110大小吗？那剩下的100个空间不就是浪费了。

换哈希函数

显然也是不可取的，哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

5.3 哈希函数的种类

💯 直接定址法

  • 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 

例如：

一个国家的年龄是散布均匀的，那么就可以使用直接定址法：Hash (key) = key

 在比如一个小区的人都是1900 - 1999 年出生的，那么我们的就可以设为：Hash(key) = k - 1900

 💨 直接定址法虽然不会发生哈希冲突，但是但问题是需要事先知道关键字的分布情况，适合查找表较小且连续的情况，此方法简单，但是不常用。

💯 除留余数法 - 常用

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

💯 平方取中法

求出 key 的平方， 然后取中间三位数字作为哈希地址，平方取中法比较适合：不知道关键字的分
布，而位数又不是很大的情况。

💯 随机数法

取关键字的随机函数值为哈希地址，Hash(key) =  radom(key)。

random为随机函数 - Random (Java Platform SE 8 ) (oracle.com)

等等还有很多哈希函数，这里不一 一介绍。

6.冲突

6.1 概念

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞，在实际应用中，哈希表底层的数组是要小于需要存储关键字的数量的，这就导致了哈希冲突是必然发生的，我们需要做的就是降低冲突率。

6.2 负载因子

  • 散列表的载荷因子定义为: α = 填入表中的元素个数 / 散列表的长度
  • 当我们的哈希表长度为10时，填入表中的元素个数为7个，此时α = 0.7
  • 负载因子越大，意味着表中的元素越多，那就意味着冲突率越高， 此时我们应该降低负载因子，降低负载因子的办法就是 - 扩容。
  • 负载因子应该严格限制在0.7 - 0.8 以下，在java 中，负载因子限制为了0.75。

负载因子与冲突率之前的关系图: 

fu 

HashMap 底层定义的负载因子

  

 6.3 解决 - 闭散列 和 开散列

📢 闭散列

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

假如我们需要插入14元素，根据哈希函数 - 除留余数法得出哈希地址为 4，但是此时 4 的位置已经有了 key 为 4 的元素，这时候可以使用线性探测来解决。

  • 但是线性探测在删除元素的时候可能就会影响到其他的元素，例如我将4 删除掉，然后我再查找 24 的时候查到的是 4 的位置，4 的位置此时为 null，系统就会默认这个哈希表中没有24 这个关键字的元素。这个时候就需要标记的伪删除法来删除一个元素。例如将 4 的位置标记一个 1代表着删除了，0代表着没删除。

如上图中，线性探测在插入哈希地址相同的元素过多时，元素全部集中在一块了，那么就有了二次探测。

二次探测：

二次探测为了避免数据堆积在一块使用了上方的公式，i = 1,2,3...（冲突次数）

假设 4 位置已经有元素，插入 14,H = 4，i = 1(第一次冲突)，即在5 的位置插入元素。

再次插入元素24，H = 4, i = 2(第二次冲突)，即在 8 的 位置上插入元素。

闭散列的缺点就是空间利用率不高，这时候开散列就来了。 

 📢 开散列 - 哈希桶

  • 开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
  • HashMap 底层使用的就是开散列的结构。
  • HashMap 的结构是由 数组 + 链表 + 红黑树组成的

 那么红黑树又是怎么一回事：

当链表的长度超过 8 时，这个链表就会转换成一棵红黑树。

模拟实现哈希桶

注意这里并没有实现链表转换红黑树的操作(本人还没学红黑树🤡🤡)

public class HashBucket {
    //结点
     class Node {
         int key;
         int val;
         Node next;

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

    private Node[]  array;//底层操作数组
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;//负载因子
    private static final int DEFAULT_SIZE = 8;//默认桶的大小

    //设置元素
    public int put(int key, int value) {
        //先找有没有相同的key
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key) {
                cur.val = value;
                return value;
            }
            cur = cur.next;
        }
        //index 没有元素就放入key
        Node node = new Node(key,value);
        cur = array[index];
        if(cur == null) {
            array[index] = node;
            size++;
            //检查负载因子扩容
            if(loadFactor() > LOAD_FACTOR) {
                resize();
            }
            return value;
        }
        //index 位置有元素了，使用尾插法插入
        cur.next = node;
        size++;
        //检查负载因子扩容
        if(loadFactor() > LOAD_FACTOR) {
            resize();
        }
        return value;
    }

    //扩容
    private void resize() {
        //扩容对新数组进行操作，操作完成后赋值给原数组
        //因为新数组可能需要重新散列元素，例如 20 大小数组 key 为14 时位置已经不在原数组(10大小) 4 的位置上
        
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null) {
                int index = cur.key % newArray.length;
                if(newArray[index] == null) {
                    newArray[index] = cur;
                }else {
                    newArray[index].next = cur;
                }
                cur = cur.next;
            }
        }
        array = newArray;
    }

    //检查负载因子
    private double loadFactor() {
        return size * 1.0 / array.length;
    }


    public HashBucket() {
        array = new Node[10];
    }

    //获取key.val
    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;
    }
}

hashCode() 

  • 如果在 HashMap 中传入自定义类会发生什么

如代码中传入 Cup 类，根据上文得知我们传入对象时需要使用哈希函数比较他们的 key 关键字来确定哈希地址存放对象的，但是我们自定义的类是通过哪里的哈希函数求出哈希地址的呢

    static class Cup {//杯子
        String name;
        int price;
        public Cup(String name,int price) {
            this.name = name;
            this.price = price;
        }
    }
    public static void main(String[] args) {
        Cup cup1 = new Cup("猫爪杯子",10);
        Cup cup2 = new Cup("派大星杯子",22);
        Cup cup3 = new Cup("海绵宝宝杯子",25);
        Cup cup4 = new Cup("猫爪杯子",10);
        HashMap<Cup,Integer> hasMap = new HashMap<>();
        System.out.println(cup1.hashCode());
        System.out.println(cup2.hashCode());
        System.out.println(cup3.hashCode());
        System.out.println(cup4.hashCode());
    }

 

当我们点过去发现是使用了Object 下的 hashCode ,他会生成一个随机数，具体了解可以查看这篇文章(7条消息) 源码解读：对象的hashcode是如何生成的_D_下潜的博客-CSDN博客_hashcode是怎么生成的https://blog.csdn.net/qq_38430053/article/details/117931159?spm=1001.2014.3001.5502

  • 重写 hashCode 方法 

在 HashMap 的底层，我们传入元素时是会调用底层Object 的 hashCode 方法来计算哈希地址的

 例如上图中的 cup1 和 cup2 虽然是不同的对象，可是我认为是同一个东西，他们的值都是一样的，那怎么生成一样的哈希地址呢，答案就是重写 hashCode 方法 和 equals 方法。

生成后的代码

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

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

 这里的 hashCode 调用的 Objects 的 hash 方法，哈希值的计算时根据你 hash 传入的类型来调用他们的类底下重写的hashCode 方法来进行计算。

如果不重写 equals 方法，调用的是Object 的 eqauls 方法 - 判断地址是否相等。

put 此时根据哈希码得出索引下标查找到哈希桶，据 equals 在桶中逐一判断，虽然cup1 和 cup4 虽然哈希码是一样的，但是equals 认为是不相等的，所以get(cup4) 时无法获取到 val

    public static void main(String[] args) {
        Cup cup1 = new Cup("猫爪杯子",10);
        Cup cup2 = new Cup("派大星杯子",22);
        Cup cup3 = new Cup("海绵宝宝杯子",25);
        Cup cup4 = new Cup("猫爪杯子",10);
        HashMap<Cup,Integer> hasMap = new HashMap<>();
        hasMap.put(cup1,100);
        hasMap.put(cup2,200);
        hasMap.put(cup3,300);
        System.out.println(hasMap.get(cup4));
    }

  • 重写 equals 后，判断cup1 和 cup4 是相等的，即cup1 和 cup4 的关键字 key 是一样的，put 其中任何一个都会更新之前的 val。
    public static void main(String[] args) {
        public static void main22(String[] args) {
            Cup cup1 = new Cup("猫爪杯子",10);
            Cup cup2 = new Cup("派大星杯子",22);
            Cup cup3 = new Cup("海绵宝宝杯子",25);
            Cup cup4 = new Cup("猫爪杯子",10);
            HashMap<Cup,Integer> hasMap = new HashMap<>();
            hasMap.put(cup1,100);
            hasMap.put(cup2,200);
            hasMap.put(cup3,300);
            hasMap.put(cup4,300);
            System.out.println(hasMap.get(cup1));
    }

 7.Tree 和 Hash 的区别

TreeMapHashMap
底层结构红黑树哈希桶(数组 + 链表 + 红黑树)
插入/删除/查找时间复杂度O(log₂N) - 树的高度O(1)
是否有序关于 key 有序无序
线程安全不安全不安全
插入/删除/查找区别需要进行元素比较通过哈希函数求出哈希码
比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法
应用场景 需要Key有序场景下Key是否有序不关心，需要更高的时间性能
TreeSetHashSet
底层结构红黑树哈希桶(数组 + 链表 + 红黑树)
插入/删除/查找时间复杂度O(log₂N) - 树的高度O(1)
是否有序关于 key 有序不一定有序
线程安全不安全不安全
插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除
比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法
应用场景 需要Key有序场景下Key是否有序不关心，需要更高的时间性能

以上就是我对 Map 和 Set 的全部总结了，有不足望大佬多多指出！！！