Map和Set

梦里梦外; 2024-02-21 10:00 14阅读 0赞

#### 文章目录 ####

*  一、搜索树
 *   *  1.1 概念
     *  1.2 操作-查找
     *  1.3 操作-插入
     *  1.4 操作-删除（难点）
     *  1.5 实现
     *  1.6 性能分析
     *  1.7 和Java类集合的关系
 *  二、搜索
 *   *  2.1 概念及应用场景
     *  2.2 模型
 *  三、Map的使用
 *   *  3.1 Map的说明
     *  3.2 关于Map.Entry<K, V>的说明
     *  3.3 Map常用方法
     *  3.4 TreeMap的使用
 *  四、Set的使用
 *   *  4.1 Set常用方法
     *  4.2 TreeSet的使用
 *  五、哈希表
 *   *  5.1 概念
     *  5.2 冲突的概念以及避免
     *  5.3 冲突-避免-哈希函数设计
     *  5.4 冲突-避免-负载因子调节(重点掌握)
     *  5.5 冲突-解决
     *  5.6 冲突-解决-闭散列
     *  5.7 冲突-解决-开散列/哈希桶（重点掌握）
     *  5.8 冲突严重时的解决办法
     *  5.9 实现
     *  5.10 性能分析
     *  5.11 和Java类集合的关系
 *  六、练习
 *   *  6.1 只出现一次的数字
     *  6.2 复制带随机指针的链表
     *  6.3 宝石与石头
     *  6.4 坏键盘打字
     *  6.5 前K个高频单词

## 一、搜索树 ##

### 1.1 概念 ###

**二叉搜索树**又称**二叉排序树**，它是一棵空树或者是具有以下性质的二叉树：

1.  **若它的左子树不为空，则左子树上所有节点的值都小于根节点的值**
2.  **若它的右子树不为空，则右子树上所有节点的值都大于根节点的值**
3.  **它的左右子树也分别为二叉搜索树**  
    ![在这里插入图片描述][e67cb18dd80d486bb54020d3e1d4b0c8.png_pic_center]

### 1.2 操作-查找 ###

![在这里插入图片描述][59e215dc2af141cd97144e0abbbd5f41.png_pic_center]

### 1.3 操作-插入 ###

![在这里插入图片描述][6506f54a74ad4ba0b6f583feca686ac3.png_pic_center]

### 1.4 操作-删除（难点） ###

![在这里插入图片描述][6bd5674b71134a16b98740667c025cf7.png_pic_center]

### 1.5 实现 ###

/**
     4. 二叉搜索树
    */
    public class BinarySearchTree {
        
        static class TreeNode {
        
            public int key;
            public TreeNode left;
            public TreeNode right;
    
            TreeNode(int key) {
        
                this.key = key;
            }
        }
    
        public TreeNode root;
        /**
         * 插入一个元素
         * true表示插入成功，false表示插入失败
         * @param key
         */
        public boolean insert(int key) {
        
            TreeNode newNode = new TreeNode(key);
            if(root == null){
        
                root = newNode;
                return true;
            }
            TreeNode cur = root;
            TreeNode parent = null;
            while (cur != null){
        
                if(cur.key < key){
        
                    parent = cur;
                    cur = cur.right;
                }else if(cur.key > key){
        
                    parent = cur;
                    cur = cur.left;
                }else {
        
                    return false;
                }
            }
            if(parent.key > key){
        
                parent.left = newNode;
            }else {
        
                parent.right = newNode;
            }
            return true;
        }
        //查找key是否存在
        public TreeNode search(int key) {
        
            TreeNode cur = root;
            while( cur != null){
        
                if(cur.key == key){
        
                    return cur;
                }else if(cur.key < key){
        
                    cur =cur.right;
                }else {
        
                    cur = cur.left;
                }
            }
            //key不存在
            return null;
        }
        //删除节点值为key的节点
        public boolean remove(int key) {
        
            TreeNode cur = root;
            //parent是cur的父节点
            TreeNode parent = null;
            while(cur != null){
        
                if(cur.key == key){
        
                    //删除节点cur
                   removeNode(cur,parent);
                }
                else if(cur.key < key){
        
                    parent = cur;
                    cur = cur.right;
                }else {
        
                    parent = cur;
                    cur = cur.left;
                }
            }
            //二叉搜索树中不存在元素key
            return false;
        }
        //删除节点cur，parent是cur的父节点
        private void removeNode(TreeNode cur, TreeNode parent) {
        
            if(cur.left == null){
        
                //不存在左子树
                if(cur == root){
        
                    //cur是根节点
                    root = cur.right;
                }else if(cur == parent.left){
        
                    //cur是parent的左孩子
                    parent.left = cur.right;
                }else {
        
                    //cur是parent的右孩子
                    parent.right = cur.right;
                }
            }else if(cur.right == null){
        
                //不存在右子树
                if(cur == root){
        
                    //cur是根节点
                    root = cur.left;
                }else if(cur == parent.left){
        
                    //cur是parent的左孩子
                    parent.left = cur.left;
                }else {
        
                    //cur是parent的右孩子
                    parent.right = cur.left;
                }
            }else {
        
                //左右子树都存在
    
                //找到右子树中最小值target和其父节点targetParent
                TreeNode targetParent = cur;
                TreeNode target = cur.right;
                while(target.left != null) {
        
                    targetParent = target;
                    target = target.left;
                }
                //要删除节点的存储的元素是右子树中的最小值
                cur.key = target.key;
                //删除target
                if(target == targetParent.left){
        
                    //最小值节点是targetParent的左孩子
                    targetParent.left = target.right;
                }else {
        
                    //最小值节点是targetParent的右孩子
                    targetParent.right = target.right;
                }
            }
        }
    }

### 1.6 性能分析 ###

插入和删除操作都必须先查找，查找效率代表二叉搜索树中各操作的性能。  
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。  
![在这里插入图片描述][b8a49740e2f84bd0b168d909bf8c643d.png_pic_center]  
**最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2n  
最差情况下，二叉搜索树退化为单支树，其平均比较次数为: n/2**  
问题：如果是单支树，就失去了二叉搜索树的性能，那能否进行改进，使得不论按照什么次序插入关键码，都可以使二叉搜索树的性能最佳？

### 1.7 和Java类集合的关系 ###

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

## 二、搜索 ##

### 2.1 概念及应用场景 ###

**Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关**。以前常用的搜索方式有：  
5. **直接遍历**，时间复杂度为O(N)，元素如果比较多效率会非常慢  
6. **二分查找**，时间复杂度为 O(log2N),但搜索前提是必须要求序列有序  
上述排序比较**适合静态类型的查找**，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

1.  根据姓名查询考试成绩
2.  通讯录，即根据姓名查询联系方式  
    可能**在查找时进行一些插入和删除的操作**，即**动态查找**，那上述两种方式就不太适合了，本节介绍的**Map和Set是一种适合动态查找的集合容器**。

### 2.2 模型 ###

一般把**搜索的数据称为关键字（Key）**，和**关键字对应的称为值（Value）**，将其称之为Key-value的键值对，所以模型会有两种：  
**1. 纯 key 模型** 比如：快速查找一个单词是否在英文词典中、快速查找某个名字在不在通讯录中。  
**2. Key-Value 模型** 比如：梁山好汉的江湖绰号：每个好汉都有自己的绰号。

## 三、Map的使用 ##

[官方文档][Link 1]  
![在这里插入图片描述][d970205117cf43729886940955727a4e.png_pic_center]

### 3.1 Map的说明 ###

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

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

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

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>K getKey()</td> 
   <td>返回 entry 中的 key</td> 
  </tr> 
  <tr> 
   <td>V getValue()</td> 
   <td>返回 entry 中的 value</td> 
  </tr> 
  <tr> 
   <td>V setValue(V value)</td> 
   <td>将键值对中的value替换为指定value</td> 
  </tr> 
 </tbody> 
</table>

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

### 3.3 Map常用方法 ###

![在这里插入图片描述][7f3a60e8ffb74244bedbe0460efa8e71.png_pic_center]  
注意：

*  **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删除掉，然后再来进行重新插入**。
 *  TreeMap和HashMap的区别（在后文了解HashMap后讲）  
    ![在这里插入图片描述][657f303c938d4343b4d1d2df421c590d.png_pic_center]

### 3.4 TreeMap的使用 ###

public static void main(String[] args) {
        
        Map<String,String> treeMap = new TreeMap<>();
        treeMap.put("宋江","及时雨");
        treeMap.put("林冲","豹子头");
        treeMap.put("武松","行者");
        System.out.println(treeMap.size());//3
        System.out.println(treeMap);//{宋江=及时雨, 林冲=豹子头, 武松=行者}
    
        // put(key,value):key不能为空，但是value可以为空,key如果为空，抛出空指针异常
        treeMap.put("李逵",null);
        System.out.println(treeMap.size());//4
        System.out.println(treeMap);//{宋江=及时雨, 李逵=null, 林冲=豹子头, 武松=行者}
        
        //treeMap.put(null,"黑旋风");  NullPointerException
        // 如果key存在，会使用value替换原来key所对应的value，返回旧value
        String str = treeMap.put("李逵","黑旋风");
        System.out.println(treeMap);//{宋江=及时雨, 李逵=黑旋风, 林冲=豹子头, 武松=行者}
        System.out.println(str);//null
    
        //get(key): 返回key所对应的value，如果key不存在，返回nul
        System.out.println(treeMap.get("宋江"));//及时雨
    
        //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println(treeMap.getOrDefault("李逵", "铁牛"));//黑旋风
        System.out.println(treeMap.getOrDefault("史进", "九纹龙"));//九纹龙
        System.out.println(treeMap.size());//4
    
        //containKey(key)：检测key是否包含在Map中
        System.out.println(treeMap.containsKey("武松"));//true
        System.out.println(treeMap.containsKey("史进"));//false
    
        // 打印所有的key
        // Set<K> keySet()将map中的key防止在Set中返回
       for (String s:treeMap.keySet()) {
        
           System.out.print(s+" ");//宋江 李逵 林冲 武松
       }
       System.out.println();
    
       // 打印所有的value
       // Collection<V> values()将map中的value放在collect的一个集合中返回
       for (String s:treeMap.values()) {
        
           System.out.print(s+" ");//及时雨 黑旋风 豹子头 行者
       }
       System.out.println();
    
       // 打印所有键值对
       // Set<Map.Entry<K, V>> entrySet()将Map中的键值对放在Set中返回
       for (Map.Entry<String,String>  entry : treeMap.entrySet()) {
        
            //宋江-->及时雨 李逵-->黑旋风 林冲-->豹子头 武松-->行者
            System.out.print(entry.getKey()+"-->"+entry.getValue()+" ");
       }
    }

class student{
        
         String name;
         int age;
    
        public student(String name, int age) {
        
            this.name = name;
            this.age = age;
        }
    
        @Override
        public boolean equals(Object o) {
        
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            student student = (student) o;
            return age == student.age && name.equals(student.name);
        }
    
        @Override
        public int hashCode() {
        
            return Objects.hash(name);
        }
    
        @Override
        public String toString() {
        
            return "student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

## 四、Set的使用 ##

[官方文档][Link 2]  
**Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key**。

### 4.1 Set常用方法 ###

![在这里插入图片描述][ecfa81f36673410c976712d421080cf3.png_pic_center]  
注意：

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

### 4.2 TreeSet的使用 ###

public static void main(String[] args) {
        
       Set<String> set = new TreeSet<>();
       //add(key) 如果key不存在，则插入返回ture,否则返回false； key如果是空，抛出空指针异常
       set.add("apple");
       set.add("banana");
       set.add("orange");
       set.add("pear");
       //set.add(null); NullPointerException
       System.out.println(set);//[apple, banana, orange, pear]
    
       // contains(key): 如果key存在，返回true，否则返回false
       System.out.println(set.contains("apple"));//true
       System.out.println(set.contains("watermelen"));//false
    
       // remove(key): key存在，删除成功返回true
       // key不存在，删除失败返回false
       // key为空，抛出空指针异常
       set.remove("apple");
       System.out.println(set);//[banana, orange, pear]
    
       //Iterator<E> iterator()
       Iterator<String> iterable =  set.iterator();
         while (iterable.hasNext()){
        
            System.out.print(iterable.next()+" ");//banana orange pear
         }
    }

## 五、哈希表 ##

### 5.1 概念 ###

**顺序结构以及平衡树**中，元素关键码与其存储位置之间没有对应的关系，因此**在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N )**，搜索的效率取决于搜索过程中元素的比较次数。  
理想的搜索方法：可以**不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素**。  
向该结构中：

*  **插入元素**–根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
 *  **搜索元素**–对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功  
    该方式即为哈希(散列)方法，**哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表或者称散列表**。  
    例如：数据集合\{1，7，6，4，5，9\}；  
    哈希函数设置为：**hash(key) = key % capacity**; capacity为存储元素底层空间总的大小。  
    ![在这里插入图片描述][40c4139ffc1b4e44ba64f9abc2d24b2d.png_pic_center]  
    **用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快** 问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

### 5.2 冲突的概念以及避免 ###

**概念**：对于两个数据元素的关键字 K i和 (i != j)，有 Ki != Kj，但有Hash( Ki) == Hash( Kj)，即**不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞**。  
**把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”**。  
**避免**：由于哈希表底层数组容量往往小于实际要存储的关键字的数量，这导致**冲突的发生是必然**的，但我们**能做的是尽量的降低冲突率**。

### 5.3 冲突-避免-哈希函数设计 ###

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

*  哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
 *  哈希函数计算出来的地址能均匀分布在整个空间中
 *  哈希函数应该比较简单  
    **常见哈希函数**：
 *  **直接定制法**–(常用)  
    **取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况**。面试题：[字符串中第一个唯一的字符][Link 3]
 *  **除留余数法**–(常用)  
    设散列表中允许的**地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址**。
 *  **平方取中法**–(了解)  
    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 **平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况**。
 *  **折叠法**–(了解)  
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。  
    **折叠法适合不需要知道关键字的分布，适合关键字位数比较多的情况**。
 *  **随机数法**–(了解)  
    选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。  
    **通常应用于关键字长度不等时采用此法**。
 *  **数学分析法**–(了解)  
    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。  
    **数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况**。  
    **注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突**。

### 5.4 冲突-避免-负载因子调节(重点掌握) ###

![在这里插入图片描述][80be42319b394c618b811611e9b0375f.png_pic_center]  
**负载因子和冲突率的关系粗略演示**：  
![在这里插入图片描述][79d7104ea8614839927dc5b9b2060782.png]  
当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率，**哈希表中已有的关键字个数不可变，调整的就只有哈希表中的数组大小**。

### 5.5 冲突-解决 ###

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

### 5.6 冲突-解决-闭散列 ###

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

*  插入  
    1.通过哈希函数获取待插入元素在哈希表中的位置  
    2.如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素  
    ![在这里插入图片描述][4b909e1387494e0eb85ba2e6ec3912c5.png_pic_center]  
    采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。  
    2.**二次探测**  
    线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为避免该问题，找下一个空位置的方法为：Hi = (H0 \+ i2)% m, 或者：Hi= (H0 \-i2 )% m。其中：i = 1,2,3… H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：  
    ![在这里插入图片描述][8ea610ecb4414e7492e21d38baed33ea.png_pic_center]  
    当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不  
    会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。  
    故**闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷**

### 5.7 冲突-解决-开散列/哈希桶（重点掌握） ###

开散列法又叫链地址法(开链法)，首先**对关键码集合用散列函数计算散列地址**，**具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中**。  
![在这里插入图片描述][23abfa0e506345e89d8114d54b2e9e28.png_pic_center]**开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索**

### 5.8 冲突严重时的解决办法 ###

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

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

### 5.9 实现 ###

/**
     * key-value模型---哈希桶
     */
    public class HashBucket {
        
        private static class Node{
        
            private int key;
            private int value;
            Node next;
            public Node(int key,int value){
        
                this.key = key;
                this.value = value;
            }
        }
        private Node[] array;
        private int usedSize;
        private static final float DEFULT_LOAD_FACTOR = 0.75f;
        public HashBucket(){
        
            array = new Node[10];
        }
    
        /**
         * 插入元素
         * @param key
         * @param value
         * @return
         */
        public boolean insertt(int key,int value){
        
            int index = key % array.length;
            Node cur = array[index];
            while(cur != null){
        
                if(cur.key == key){
        
                    cur.value = value;
                    return false;
                }else {
        
                    cur = cur.next;
                }
            }
            //走到这里，说明链表中没有key
            Node node = new Node(key,value);
            node.next = array[index];
            array[index] = node;
            usedSize++;
            if (usedSize*1.0/array.length > DEFULT_LOAD_FACTOR){
        
                //扩容
                reSize();
            }
            return true;
        }
    
        /**
         * 扩容
         */
        private void reSize() {
        
            Node[] newArray = new Node[array.length*2];
            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.value;
                }
                cur = cur.next;
            }
            return -1;
        }
    }

### 5.10 性能分析 ###

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

### 5.11 和Java类集合的关系 ###

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

## 六、练习 ##

### 6.1 只出现一次的数字 ###

[只出现一次的数字][Link 4]

/**
    * 计数法
    */
    public int singleNumber(int[] nums) {
        
    		//集合中的最小值和最大值
            int minValue = nums[0];
            int maxValue = nums[0];
            for(int i =1; i < nums.length; i++){
        
                if(nums[i] < minValue){
        
                    minValue = nums[i];
                }
                if(nums[i] > maxValue){
        
                    maxValue = nums[i];
                }
            }
            //新建数组存放每个数出现次数，数组下标为数的相对值
            int[] count = new int[maxValue-minValue+1];
            for(int i = 0; i < nums.length; i++){
        
                count[nums[i]-minValue]++;
            }
            //找到出现一次的数字
            int ret = 0;
            for(int i =0; i < count.length; i++){
        
                if(count[i] == 1){
        
                    ret = i+minValue;
                }
            }
            return ret;
        }

/**
    * 位运算
    */
    public int singleNumber(int[] nums) {
        
            //位运算  a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b
            int ret = 0;
            for(int i =0; i < nums.length; i++){
        
                ret ^= nums[i];
            }
            return ret;
        }

/**
    * 哈希表
    */
    public int singleNumber(int[] nums) {
        
            //哈希表
            Map<Integer,Integer> map = new HashMap<>();
            //将数字和出现次数构成映射关系，存于哈希表中
            for(int num :  nums){
        
                map.put(num,map.getOrDefault(num,0)+1);
            }
            //找出现一次的数字
            for(int value : map.keySet()){
        
                if(map.get(value) == 1){
        
                    return value;
                }
            }
            return 0;
        }

### 6.2 复制带随机指针的链表 ###

[复制带随机指针的链表][Link 5]

/**
    * 哈希表
    */
    public Node copyRandomList(Node head) {
        
            if(head == null){
        
                return null;
            }
            // 哈希表
            Map<Node,Node> map = new HashMap<>();
            
            Node cur = head;
            // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
            while(cur != null){
        
                Node node = new Node(cur.val);
                map.put(cur,node);
                cur = cur.next;
            }
            cur = head;
            //  构建新链表的 next 和 random 指向
            while(cur != null){
        
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }

### 6.3 宝石与石头 ###

[宝石与石头][Link 6]

/**
    * 暴力法---遍历字符串
    */
    public int numJewelsInStones(String jewels, String stones) {
        
            int count = 0;
            for(int i = 0; i < stones.length(); i++){
        
                char ch = stones.charAt(i);
                for(int j = 0; j < jewels.length(); j++){
        
                    if(jewels.charAt(j) == ch){
        
                        count++;
                        continue;
                    }
                }
            }
            return count;
        }

/**
    * 哈希表
    */
    public int numJewelsInStones(String jewels, String stones) {
        
            int count = 0;
            char[] ch = stones.toCharArray();
            //建立哈希表，存储每个字符对应个数
            Map<Character,Integer> map = new HashMap<>(ch.length);
            for(int i = 0; i < stones.length(); i++){
        
                char ch1 = stones.charAt(i);
                map.put(ch1,map.getOrDefault(ch1,0)+1);
            }
            //找宝石
            for(int i = 0; i < jewels.length(); i++){
        
                char ch1 = jewels.charAt(i);
                Integer value = map.get(ch1);
                if(value != null){
        
                    count += value;
                }
            }
            return count;
        }

### 6.4 坏键盘打字 ###

[坏键盘打字][Link 7]

//坏键盘打字
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            //测试的数据
            String text = in.nextLine();
            //真实数据
            String str = in.nextLine();
            Set<Character> set = new TreeSet<>();
            int i = 0;
            for(Character ch : str.toUpperCase().toCharArray()){
         
                set.add(ch);
            }
            //找到没有的键并排除已经遍历过而且重复的键
            Set<Character> set2 = new TreeSet<>();
            for(Character ch : text.toUpperCase().toCharArray()){
        
                if(!set.contains(ch) && !set2.contains(ch)){
        
                    System.out.print(ch);
                    set2.add(ch);
                }
            }
        }

### 6.5 前K个高频单词 ###

[前K个高频单词][K]

/**
    * 哈希表+优先级队列
    */
    public List<String> topKFrequent(String[] words, int k) {
        
            List<String> ret = new LinkedList<>();
            //哈希表记录每个单词出现的次数
            Map<String,Integer> map = new TreeMap<>();
            for(String word : words){
        
                map.put(word, map.getOrDefault(word,0)+1);
            }
            //构建小根堆 这里需要自己构建比较规则
            PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>(){
        
                public int compare(String word1,String word2){
        
                    int count1 = map.get(word1);
                    int count2 = map.get(word2);
                    return count1 == count2 ? word2.compareTo(word1) : count1-count2;
                } 
            });
            //向堆中放元素
            for(String x : map.keySet()){
        
                priorityQueue.offer(x);
                if(priorityQueue.size() > k){
        
                    //堆中元素超过k个，将最小元素出堆
                    priorityQueue.poll();
                }
            }
            //将堆中元素出堆，放入结果集合中
            while(!priorityQueue.isEmpty()){
        
                ret.add(priorityQueue.poll());
            }
            //走到这，结合集合中的元素为升序
            //反转结合集合中的元素--》元素为降序排列在结果集合中
            Collections.reverse(ret);
            return ret;
        }

/**
    * 哈希表+排序
    */
    public List<String> topKFrequent(String[] words, int k) {
        
            List<String> ret = new LinkedList<>();
            //记录每个单词出现的次数
            Map<String,Integer> map = new TreeMap<>();
            for(String word : words){
        
                map.put(word, map.getOrDefault(word,0)+1);
            }
            //将单词放入集合中
            for(Map.Entry<String,Integer> entry : map.entrySet()){
        
                ret.add(entry.getKey());
            }
            //对集合进行降序排序
            Collections.sort(ret,new Comparator<String>(){
        
                public int compare(String word1,String word2){
        
                    int count1 = map.get(word1);
                    int count2 = map.get(word2);
                    return  count1==count2 ? word1.compareTo(word2):count2-count1;
                } 
            });
            return ret.subList(0,k);
    
        }

[e67cb18dd80d486bb54020d3e1d4b0c8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/46e3651421eb440db533184354dcca07.png
[59e215dc2af141cd97144e0abbbd5f41.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/dd4a8e28724d48f6ad9811c868231364.png
[6506f54a74ad4ba0b6f583feca686ac3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/a9df2946e59343568f8b72fdb88d3b02.png
[6bd5674b71134a16b98740667c025cf7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/593a0753bb02480eb1d2c55ef8338700.png
[b8a49740e2f84bd0b168d909bf8c643d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/7a0a12f852824ae4bdf02244029ebc08.png
[Link 1]: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html
[d970205117cf43729886940955727a4e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/1b2005196c1c4e05996301bc812da0f2.png
[7f3a60e8ffb74244bedbe0460efa8e71.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/dea0e753ba534f438feae359667be927.png
[657f303c938d4343b4d1d2df421c590d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/60e9347e4de0419e8d0d0d7f395b7fcb.png
[Link 2]: https://docs.oracle.com/javase/8/docs/api/java/util/Set.html
[ecfa81f36673410c976712d421080cf3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/7c1040087398495588fd05f98c2040d3.png
[af2a2b5816804c1aaf25818b6bfec98c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/88aaccf8c24f455b8510e1ae6c193c4c.png
[40c4139ffc1b4e44ba64f9abc2d24b2d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/b8470209be7e4d0889ed71b2049bf554.png
[Link 3]: https://leetcode.cn/problems/first-unique-character-in-a-string/description/
[80be42319b394c618b811611e9b0375f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/47da0182c1c444d585d16453527a74d7.png
[79d7104ea8614839927dc5b9b2060782.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/903edd5c278a4c268ce21a2c7194879c.png
[4b909e1387494e0eb85ba2e6ec3912c5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/e21b3ddc50534a6998d51eee9077cf9a.png
[8ea610ecb4414e7492e21d38baed33ea.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/cc52a547150647dd8755da21a5d4ad47.png
[23abfa0e506345e89d8114d54b2e9e28.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/73d91a06e75f4d289d80153cafd142f3.png
[Link 4]: https://leetcode.cn/problems/single-number/description/
[Link 5]: https://leetcode.cn/problems/copy-list-with-random-pointer/description/
[Link 6]: https://leetcode.cn/problems/jewels-and-stones/description/
[Link 7]: https://www.nowcoder.com/practice/f88dafac00c8431fa363cd85a37c2d5e?tab=note
[K]: https://leetcode.cn/problems/top-k-frequent-words/description/