【JAVA】Map和Set

发布于：2022-11-28 ⋅ 阅读:(1080) ⋅ 点赞:(0)

目录

前言

慢慢来吧

图
分类

  1. TreeSet、TreeMap的底层是一棵特殊的搜索树【红黑树】！
  2. HashSet、HashMap的底层是哈希表。

你一定会得到你想要的！

一、搜索树

1. 概念

  1. 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

（其实简而言之：左边小于根结点，右边大于根结点）
2. 注：以下所有操作的代码都需要结点类以及根结点，所以在以下操作代码之前需要以下代码：

// 定义结点类
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

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

    // 定义根结点
    public TreeNode root;

2. 操作–查找

  1. 二叉搜索树对于数组/链表的查找是比较高效的。
    但是在最坏情况下，也就是数组本身就是有序的，二叉搜索树就成了单分支结构，其时间复杂度会达到O(N)。
    为了解决这种最坏情况出现了AVL树，但是它需要旋转使得左右子树高度差不超过1，又会降低效率，所以出现了红黑树。
  2. 在二叉搜索树中是没有重复数据的。
  3. 源码：
/**
     * 查找key是否存在于二叉搜索树中:
     * 查找时定义一个cur变量指向当前的的结点位置
     * 找到就返回结点位置，找不到就返回空
     */
    public TreeNode search(int key) {
        TreeNode cur = this.root;
        while(cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            } else if(cur.val > key) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }

3. 操作–插入

  1. 思路：

1）如果树为空树，即根 == null，直接插入
2）如果树不是空树，按照查找逻辑确定插入位置，插入新结点

  1. 源码：
/**
     * 插入的结点都在叶子结点位置：
     * 二叉搜索树中没有重复数据！所以插入相同数据时无法插入成功。
     * 需要定义一个存储上一个结点的节点变量parent，否则当cur走到空进行结点插入时无法得知上一个结点位置
     * 注意：插入结点：每次都是从根结点开始比较的。
     */
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        // 判断是否为空树
        if(this.root == null) {
            this.root = node;
            return true;
        }
        // 不为空就开始插入
        TreeNode cur = this.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 {
                // 有重复的就不能插入成功！
                return false;
            }
        }
        // 来到这儿说明cur为空，即应该要进行结点的插入:判断应该插入左边还是右边
        if(key > parent.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

4. 操作–删除（难点）

  1. 思路：

1） 找到你要删除的结点cur
2） 记住你要删除的结点的父亲结点parent
3） 分情况进行讨论（待删除结点cur左子树为空、右子树为空、都不为空–较复杂，使用“替换删除”的方法）
（替换删除：要么找cur右边的最小值结点替换待删除结点，但是其左子树一定为空；
要么找cur左边的最大值结点替换待删除结点，但是其右子树一定为空）
（最后就转变为：替换后删除该节点）

  1. 源码：
/**
     * 删除结点：
     * 左右不为空的删除才是难点
     * 假设待删除结点是cur，待删除结点的双亲结点是parent
     */
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val > key) {
                parent =cur;
                cur = cur.left;
            } else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                // 找到了结点，开始删除操作
                removeNode(cur,parent);
                return;
            }
        }
    }
    // 进行删除
    private void removeNode(TreeNode cur, TreeNode parent) {
        // 1.删除结点的左子树为空：根结点、父亲结点的左子树、父亲节点右子树
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            } else if(parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if(cur.right == null) {
            // 2. 待删除结点的右子树为空
            if(cur == root) {
                root = root.left;
            } else if(parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            // 3.待删除结点的左右子树均存在
            // 因为比较复杂，所以二叉搜索树的删除在这里使用了：替换删除的方法
            // 替换删除：找右子树里的最小值替换待删除的结点，但是此时其左子树一定是空的；或者找右子树最大值，则其左子树一定是空的
            // 定义所找要替换的结点为target，其父亲节点为targetParent。替换后要将该节点删除
            TreeNode targetParent = cur;
            TreeNode target = cur.right; // 定义了右边，寻找最小值（往左边走）
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            // 找到了左边为空的情况，开始替换+删除
            cur.val = target.val;
            // 注意这里还要分情况（要删除target）
            if(targetParent.left == target) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }
  1. 补充：（可以写一个中序遍历来进行输出）
// 写一个中序遍历：
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

5. 性能分析

  1. 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
  2. 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
  3. 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
  • 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
  • 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
  1. 问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？

6. 和 java 类集的关系

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。

二、搜索（map和set主要用在搜索和查找）

1. 概念及场景

  1. Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。以前常见的搜索方式有：
    1） 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
    2） 二分查找，时间复杂度为O(logN) ,但搜索前必须要求序列是有序的
  2. 上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
  1. 根据姓名查询考试成绩
  2. 通讯录，即根据姓名查询联系方式
  3. 不重复集合，即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。

  1. 时间复杂度：
    搜索树：O(logN)
    哈希表：O(1)

2. 模型

  1. 一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：
    1） 纯 key 模型，比如：
    （set：不能出现重复数据 ；set只有key值）

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

2） Key-Value 模型，比如：
（map：可以有val重复数据，但是key不重复：如统计词频等）

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

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

三、Map的使用

Map的官方文档

1. 关于Map的说明

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

2. 关于Map.Entry<K, V>的说明

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

3. Map 的常用方法说明

  1. Map的常用方法：
    Map方法
  2. 注意：
    1） Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
    2） Map中存放键值对的Key是唯一的，value是可以重复的
    3） Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
    4） Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
    5） Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
    6）TreeMap和HashMap的区别：
    区别

4. Map使用示例

（注意Map.Entry<K,V>的使用！！）

// HashMap使用示例：
    public static void main4(String[] args) {
        // HashMap底层是哈希表，哈希表的插入时不需要比较大小
        Map<String,Integer> map = new HashMap<>();
        // 调用方法：底层是哈希表（统计词频）
        map.put("hustle",8);
        map.put("come on",2);
        map.put("hustle",6); // key值一样，直接替换/覆盖之前的数据
        map.put(null,1);
        // HashMap中key、value都可以存储null
        map.put(null,null);
        System.out.println(map); // 可以直接输出，说明重写了toString方法
        // 打印时，并不是有序的，也并不是按照存储元素的顺序进行打印的，也不会按照大小顺序去存储元素。


        // 把每一组数据分别进行打包（相当于数据变成类型）
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        // Entry 出现了红黑树，它有getKey/getValue方法
        for (Map.Entry<String,Integer> entry : entrySet)  {
            System.out.println("key:"+entry.getKey() + " value:"+entry.getValue());
        }
    }

    // TreeMap使用示例：
    public static void main3(String[] args) {
        // TreeMap底层是搜索树，搜索树的插入时需要比较大小的（通过key来比较大小的）
        Map<String,Integer> map = new TreeMap<>();
        // 调用方法：底层是红黑树（统计词频）
        map.put("hustle",8);
        map.put("come on",2);
        map.put("hustle",6); // key值一样，直接替换之前的数据
        System.out.println(map); // 可以直接输出，说明重写了toString方法
        // 注意输出顺序与插入顺序并不一致，因为搜索树是经过排序的

        // 把每一组数据分别进行打包（相当于数据变成类型）
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        // Entry 出现了红黑树，它有getKey/getValue方法
        for (Map.Entry<String,Integer> entry : entrySet)  {
            System.out.println("key:"+entry.getKey() + " value:"+entry.getValue());
        }

        // 返回所有value的可重复！！合集
        // 注意：可重复的意思是：不同key的value值可以重复，但是相同key只会存在最后一个！！（也就是：只会输出一次相同key）
        Collection<Integer> collection = map.values();
        System.out.println(collection);
        // collection是最高接口，但是一般使用向上转型而不是向下转型

        // 返回所有不重复！！的key合集:
        Set<String> set = map.keySet();
        System.out.println(set); // 注意也是可以直接进行输出！


        System.out.println(map.get("come on")); //根据key值来输出频率
        System.out.println(map.get("hello")); // 如果没找到就返回null
        System.out.println(map.getOrDefault("come on",12));
        // 就是说如果key的数据在之前就已经给定，即使再给默认值也是只会输出之前的频率数据
        // 但是如果是之前未出现过的key值就输出现在给定的默认值

        Map<Student,Integer> map2 = new TreeMap<>();
        // 实现TreeMap，则Student要可以比较，实现可比较接口
        map2.put(new Student(),2);

    }

    public static void main2(String[] args) {
        // Map是一个接口，是不能实例化接口的;要new一个具体的实现类。
        Map<String,Integer> map = new TreeMap<>(); // TreeMap底层是一棵红黑树，必须导入包
        Map<String,Integer> map2 = new HashMap<>(); // HashMap底层是哈希表，导包

        Set<String> set = new TreeSet<>();
        Set<String> set2 = new HashSet<>();

    }

5. 补充

  1. 注意：直接可以输出TreeMap对象map，说明map重写了toString方法；但是注意到输出顺序与输入顺序不一样：因为底层是搜索树，而搜索树是通过key比较大小的。
  2. 进一步思考：搜索树通过key来比较大小，所以key一定是可以进行比较的。（尤其注意自定义类型要可比较【实现Comparable接口，重写compareTo方法】）
  3. TreeMap的参数不可以是null。当key值重复时是不可以插入成功的，而是会直接替换之前的数据。
  4. 打印HashMap时，并不是按照存储元素的顺序进行打印的，也不会按照大小顺序进行存储元素。那么是如何进行元素存储的呢？
    HashMap的存储是根据底层的哈希函数去找对应位置的。如果所打印的顺序恰好是有序的，原因是HashMap根据key值和哈希函数进行存储的时候正好放到的位置是有序的。
  5. HashMap不存在比较关系，所以参数可以是null（key、value都是ok的）。

四、Set的说明

Set的官方文档

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

1. 常见方法说明

  1. Set常见方法：
    Set
  2. 注意：
    1）Set是继承自Collection的一个接口类 （注：Map不是继承自Collection）
    2） Set中只存储了key，并且要求key一定要唯一
    3） Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
    4） Set最大的功能就是对集合中的元素进行去重
    5） 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
    6） Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
    7）TreeSet不能插入null，HashSet可以（HashMap：key、value都ok）。
    8） TreeSet和HashSet的区别：
    区别

2. 重点练习题

  1. 给你10w个数据，把这10w个数据中【重复】的数据删掉
  2. 给你10w个数据，找到这10w个数据中【第一个重复】的数据
  3. 给你10w个数据，统计这10w个数据中每个数据数据出现的【频率】
  • 源码：
// 注意：Map有值 Set无值  Hash高效
    // 给题
    // 1.删重/去重：相关优先考虑Set
    private static void removeRepeat(int[] arr) {
        // 直接使用HashSet进行去重，当然也可以使用TreeSet，但是使用HashSet更加高效
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        System.out.println(set);
    }
    // 2.找到第一个重复数据
    // 使用HashSet且放入时进行检查！（不存在就add，存在就返回！）
    private static int findFirstRepeat(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if(!set.contains(arr[i])) {
                // 不在就进行add
                set.add(arr[i]);
            } else {
                return arr[i];
            }
        }
        return -1; // 就是没有重复的数据
    }
    // 3.统计词频：HashMap比较快（词频就需要Map）
    // key是当前数据，value就是出现的次数
    private static void count(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            // 看map中是否已经存在该元素，存在则value++，不存在则放入置1
            if(map.get(key) == null) {
                // 不存在
                map.put(key,1);
            } else {
                // 注意这里的写法
                // 已经存在，则value++
                int val = map.get(key); // 获取到当前key出现的次数
                map.put(key,val+1); // 进行了覆盖/更新
            }
        }
        System.out.println(map);
    }

3. 补充

  1. Set：存储的都是不重复元素，故：Set的一般是是用于去重！
  2. 为什么Set可以用于去重：
    TreeSet当中存储的元素key必须是可比较的（因为实现了SortedMap接口）
    （看源码可以大致理解为：TreeSet的底层是TreeMap：key值是add的对象，value值是Object对象）
    因为TreeMap的key值不可以重复，所以TreeSet的key值与不可以重复。
  3. HashSet也是同样的参考HashMap，HashSet的底层是HashMap。

五、OJ题练习

  1. 只出现一次的数字only once
  2. 复制带随机指针的链表copy random
  3. 宝石与石头jewels&stones
  4. 坏键盘打字bad keyboards
  5. 前K个高频单词topK

六、哈希表

哈希表的【增删查改CURD】时间复杂度都是：O(1)。

1. 概念

  1. 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( logN)，搜索的效率取决于搜索过程中元素的比较次数。
  2. 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
  3. 当向该结构中：
    1）插入元素：（计算存储位置）
    根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
    2）搜索元素：（计算存储位置+比较关键值key）
    对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
4. 存储元素的顺序不代表该元素在哈希表中的相对位置。
元素存储到哪个位置其实是和哈希函数/散列函数有关系的。
5. 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
1）用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。
2）问题：按照上述哈希方式，向集合中插入元素时，可能会出现什么问题？

两个不同的关键字key通过相同的哈希函数找到了同一个位置，也就是hash(k1)==hash(k2)这种现象叫做：哈希冲突。

2. 冲突–概念

  1. 对于两个数据元素的关键字Ki 和Kj (i != j)，有Ki != Kj，但有：Hash(Ki) == Hash(Kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
  2. 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

3. 冲突–避免

  1. 首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。
  2. 即：在哈希表中，冲突的发生是必然的。你可以认
    为一般情况下：我们所要存储的元素是远远大于表的长度的。

4. 冲突–避免–哈希函数设计

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

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

  1. 常见哈希函数：
    1）直接定制法（常用）：
    ①取关键字的某个线性函数为散列地址：Hash(Key)= A*Key + B 。
    ②优点：简单、均匀； 缺点：需要事先知道关键字的分布情况。
    ③使用场景：适合查找比较小且连续的情况。
    ④面试题：字符串中的第一个唯一字符

面试题：开辟一个数组（长度为26：因为只有小写字母），然后按照字母下标进行存储，index=‘字母’-96; 存储的是出现的次数。存完遍历原来字符串，遇到==1就输出。

/**
     * 字符串中只出现一次的第一个字符：
     * 返回的是该字符在字符串中的下标！
     * 不用HashMap，而是使用一个数组进行存储字符数量
     */
    public int firstUniqChar(String str) {
        // 遍历字符串（转数组）进行数量统计
        int[] count = new int[26];
        // ‘a':97 所以97位置可以直接使用'a'替换
        for (char ch : str.toCharArray()) {
            count[ch-97]++;
        }

        /*// 遍历字符串获取字符也可以改为：
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            count[ch-97]++;
        }*/

        // 再次遍历字符串 找数组中首次==1的并返回
        /*for (char ch : str.toCharArray()) {
            if(count[ch-97] == 1) {
                return ch;
            }
        }*/

        // 遍历字符串获取字符也可以改为：
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if(count[ch-97]==1) {
                return i; // 返回下标
            }
        }
        return -1;
    }

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）数字分析法（了解）

1） 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
2）即：分布较为均匀的几位数字用作 散列地址。
3）例如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
4）数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

5. 冲突–避免–负载因子调节（重点掌握）

  1. 负载因子：负载
  2. 负载因子和冲突率的关系粗略演示：
    关系
    1）所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
    2）已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

6. 冲突–解决

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

7. 冲突–解决–闭散列

  1. 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
    1） 线性探测
    （假定数组长度10）
    ① 比如需要插入元素44，先通过哈希函数（key%arr.length)计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
    ② 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入 ：

  • 通过哈希函数获取待插入元素在哈希表中的位置
  • 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
  • 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

③ 线性探测弊端：会把尽可能冲突的元素放到一起；且不好删除（因为当删除其中一个冲突元素时，此位置空了之后，在它后面的冲突元素就会被认为没有/找不到。

2）二次探测
① 线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i2)% m, 或者：Hi = (H0 - i2)% m。其中：i = 1,2,3…（i表示第i次冲突）， H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
② 研究表明：当表的长度为质数且表的装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
③ 因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

8. 冲突–解决–开散列/哈希桶（重点掌握）

  1. 开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
  2. 在数组中存放链表，把all冲突元素都放到计算得到的位置（使用链表串起来all冲突元素）
  3. java当中的HashMap就是采用数组+链表（链表在某种情况下也会变成红黑树）【数组+链表+红黑树】
  4. 开散列中每个桶中放的都是发生哈希冲突的元素。
  5. 开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

9. 冲突严重时的解决办法

哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也是不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：
1）每个桶的背后是另一个哈希表
2） 每个桶的背后是一棵搜索树

10. 实现

  1. 思路：

实现哈希桶：
1）先根据key定位到在数组的哪个位置
2）检查当前数组位置的链表是否存在相同的key，存在就要更新对应的value
3）链表当中不存在相同key就进行插入，插入后usedSize++（在JDK1.8中实现
的是尾插法，那么我们这里就来实现头插法）
注意：检查负载因子以及扩容

思考：扩容之后，是不是从原来的0下标的链表开始拷贝到新数组的0下标位置？
答：不是。因为下标位置index是根据key%arr.length来确定的，但是扩容后数组长度 变了，那计算得到的下标位置自然也就改变了，并不是与之前一一对应。
那么：该如何扩容？
答：首先创建新数组进行扩容；然后遍历原数组的每个元素的链表，每遍历到一个结点就重新哈希（新的长度），并且以头插方式插入到新数组中；最后赋值到原数 组上。

  1. 源码：
    1）简单版：
// 简单实现 哈希桶
// 数组+链表

public class HashBuck {

    // 首先定义一个结点类(key-val-next)
    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[] arr;
    // 记录当前哈希桶中有效数据的个数
    public int usedSize;
    // 给一个默认的负载因子：
    public static final float DEFAULT_LOAD_FACTOR = 0.75f; // java底层默认负载因子就是0.75

    // 构造方法进行初始化
    public HashBuck (){
        arr = new Node[2];
        this.usedSize = 0;
    }

    /** 存储key、val
     * 根据key来定位，然后检查是否有相同key，没有就进行插入usedSize++
     * @param key
     * @param val
     * @return
     */
    public void put(int key, int val) {
        // 首先新建一个结点（有了结点才能存入数组中）
        Node node = new Node(key,val);
        // key进行定位
        int index = key % arr.length;
        // 遍历、检查key:因为要考虑冲突的情况
        Node cur = arr[index];
        while(cur != null) { // cur结点不为空就说明：在所要插入的位置上已经存在了结点
            if(cur.key == key) { // 说明该位置上的节点的key值与所要插入的节点的key值一样，就进行更新val值
                //此时说明有重复:更新val值
                cur.val = val;
                return;
            }
            // 说明该位置已经有结点但不是我要存入的node结点，那就继续向当前下标位置节点的next上（也就是链表的下一个结点位置）
            cur = cur.next;
        }
        // 跳出该循环：说明此时已经走到了空的位置，就进行头插
        node.next = arr[index]; // node是此时要插入的新节点，插入到目标位置的前一个位置
        arr[index] = node;
        usedSize++; // 有效大小就++

        // 这里作图很重要，每一个数组的元素下面存的是链表（结点的next、串起来）！！！

        // 检查负载因子 大于就进行扩容：
        if(loadFac() >= DEFAULT_LOAD_FACTOR) {
            // 扩容
            grow();
        }
    }

    // 返回当前的负载因子：
    private float loadFac() {
        return usedSize * 1.0f / arr.length; // * 1.0f的目的是返回float类型
    }

    // 扩容：
    private void grow() {
        Node[] newArr = new Node[2*arr.length];
        // 遍历原数组
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i]; // 记录当前的数组的元素对应链表的头结点
            // 遍历该链表的每一个结点 并重新进行哈希（新长度）
            while(cur != null) {
                Node curNext = cur.next; // 记录原来cur的下一个结点（很好的保证了原来数据链表的有效）
                int index = cur.key % newArr.length;
                // 然后以头插法的形式插入到新的数组
                cur.next = newArr[index]; // 表示新老数组结点的对应关系
                newArr[index] = cur; // 对新数组开始赋值结点/链表
                // cur = cur.next; // 这样就会丢失原数组的后面的链表结点
                cur = curNext; // 进行循环变化的条件
            }
        }
        // 赋值到原数组
        this.arr = newArr;
    }

    /** 通过key值来获取val值:
     *
     * @param key
     * @return
     */
    public int get(int key) {
        // 首先计算再数组的下标位置
        int index = key % arr.length;
        Node cur = arr[index];
        // 然后遍历该下标位置的链表来找有相同key值的节点来返回val值
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            // 还没有找到相同的就继续遍历该下标位置的链表
            cur = cur.next;
        }
        // 出来说明已经遍历完该位置的所有结点，没有找到
        return -1;
    }
}

2）泛型版：
// 哈希桶的实现2：plus版（泛型）

import java.util.Objects;

public class HashBuck2<K,V> {
//同样西哟啊一个结点类，但是key、val类型是泛型
static class Node<K,V> {
public K key;
public V val;
public Node<K,V> next;

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

    // 重写equals和hashCode方法
    // （其实是需要在泛型K中重写equals和toString方法）！！！

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node<?, ?> node = (Node<?, ?>) o;
        return Objects.equals(key, node.key) && Objects.equals(val, node.val) && Objects.equals(next, node.next);
    }

    @Override
    public int hashCode() {
        return Objects.hash(key, val, next);
    }
}

// 给出一个数组
// 注意：java中不能new泛型类型的数组：如 public Node<K,V>[] arr = new Node<K,V>[10];是error
public Node<K,V>[] arr = (Node<K, V>[]) new Node[10];
// 也可以修改为： public Node<K,V>[] arr = (Node<K, V>[]) new Object[10];

public int usedSize;
public static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 写一个put方法：
public void put(K key, V val) {
    // 变成结点
    Node<K,V> node = new Node<>(key,val);
    // 找数组位置:泛型--注意计算的方式！！
    int index = key.hashCode() % arr.length;
    // 开始遍历该数组位置的链表结点
    Node<K,V> cur = arr[index];
    while (cur != null) {
        // 注意：引用类型比较大小不是直接使用==，而是使用equals--要重写equals方法
        // 此时相当于：hashCode找在数组中的位置，而equals则是遍历该位置下的链表找相同的节点
        if(cur.key.equals(key)) {
            // 替换val
            cur.val = val;
            return;
        }
        // 来到这儿：走向链表的下一个结点位置
        cur = cur.next;
    }
    // 找到了位置开始进行头插
    node.next = arr[index];
    arr[index] = node;
    this.usedSize++;

    // 检查负载因子
    if(loadFac() >= DEFAULT_LOAD_FACTOR) {
        grow();
    }
}

/** 返回当前的负载因子：
 *
 * @return 返回负载因子，用于检查负载因子以及扩容
 */
private float loadFac() {
    return usedSize * 1.0f / arr.length; // * 1.0f的目的是返回float类型
}

/** 扩容：
 *
 */
private void grow() {
    Node<K,V>[] newArr = new Node[2*arr.length];
    // 遍历原数组
    for (int i = 0; i < arr.length; i++) {
        HashBuck2.Node<K,V> cur = arr[i]; // 记录当前的数组的元素对应链表的头结点
        // 遍历该链表的每一个结点 并重新进行哈希（新长度）
        while(cur != null) {
            Node<K,V> curNext = cur.next; // 记录原来cur的下一个结点（很好的保证了原来数据链表的有效）
            int index = cur.key.hashCode() % newArr.length;
            // 然后以头插法的形式插入到新的数组
            cur.next = newArr[index]; // 表示新老数组结点的对应关系
            newArr[index] = cur; // 对新数组开始赋值结点/链表
            // cur = cur.next; // 这样就会丢失原数组的后面的链表结点
            cur = curNext; // 进行循环变化的条件
        }
    }
    // 赋值到原数组
    this.arr = newArr;
}


/**
 * 通过key获取val
 */
public V get(K key) {
    // 找数组下标 并进行链表的遍历比较key值返回val
    int hash = key.hashCode();
    int index = hash % arr.length;

    Node<K,V> cur = arr[index];
    while(cur != null) {
        if(cur.key.equals(key)) {
            return cur.val;
        }
        cur = cur.next;
    }
    // 来到这儿 找不到
    return null;
}

}

11. 性能分析

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

12. 和JAVA类级的关系

  1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
  2. java 中使用的是哈希桶方式解决冲突的
  3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
  4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

13. 补充（面试题）

  1. 注意面试问题：HashMap在扩容的时候要注意什么？
    –重新哈希
  2. 思考：假设所给的key是一个引用数据类型，怎么办呐？怎么计算数组下标的位置index？
    我们要想办法把不是整数的引用类型转为整数。（即：使用hashCode）
  3. 面试问题：
    1） 两个对象的hashCode一样，那么equals一定一样吗？
    不一定。因为：hashCode一样只能说明在数组的同一位置，但是该位置底下会存储很多结点，是不一定一样的。
    2） 两个对象的equals一样，那么hashCode一定一样吗？
    一定。equals一样，那一定在同一个位置，那么hashCode一定一样。
    （注：hashCode找数组中的位置，equals是比较该位置下的节点）
  4. 面试问题：
    1） HashMap<String,String> map = new HashMap<>(); 底层数组多大？
    2） HashMap<String,String> map = new HashMap<>(25); 底层数组多大？
    3） 扩容需要注意什么？
    4） 讲一下你知道或者了解的HashMap的源码？

解析：

① 要看底层数组，那就去分析HashMap源码：
默认初始容量=1<<4：也就是24=16；
最大容量=1<<30:也就是230
（其实说数组长度最好是一个素数）
② 【ps：默认负载因子0.75；
解树化的条件UNTREEIFY_THRESHOLO=6：树结点个数>6
链表树化条件之一TREEIFY_THRESHOLO=8：链表结点个数>8；&& 链表树化条件之二MIN_TREEIFY_CAPACITY=64：数组长度超过64】
③ HashMap<String,String> map = new HashMap<>(); 没有传参数的构造方法底层并没有为数组开辟空间
HashMap<String,String> map = new HashMap<>(initicalCapacity); 传入容量大小的参数时，实际底层数组开辟空间的大小是接近传入容量参数的【向上取整】的2的次方值。（即：不管你给的容量是多少，返回的都是 一个接近当前数字的2次幂的向上取整值）
面试问题：为什么这么做（就是2的次幂向上取整）？

补充：
计算hash时，将低16位与高16位进行了异或，目的是让尽可能的信息都存在于当前计算出来的值中。冲突概率就会降低。
计算下标：源码是(n-1)&hash ，实际我们写代码hash%arr.length ：如果数组长度是2等的次幂，那么这两个计算结果就是一样的。
补充：实际上hashCode的很多位是用不上的，因此再hashMap的哈希函数中才使用了移位运算符，并且只取了hashCode的前16位来做映射；另外，&操作比取模效率更高。

答案:

  1. 0 第一次put的时候就把容量变成了16
  2. 32 2的次幂
  3. 扩容需要注意重新哈希

THINK

  1. Map（有） 和 Set（无val）的有序、无序等
  2. Map和Set的区别
  3. HashMap/HashSet 与TreeMap/TreeSet 区别
  4. 代码实现
  5. Map.Entry<K,V> 的使用
  6. 冲突解决
  7. 哈希桶
  8. 面试问题！！
本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布