数据结构——Map和Set

1. 搜索树

1. 概念

⼆叉搜索树⼜称⼆叉排序树，它可以是⼀棵空树，或者是具有以下性质的⼆叉树:

• 若它的左⼦树不为空，则左⼦树上所有节点的值都⼩于根节点的值

• 若它的右⼦树不为空，则右⼦树上所有节点的值都⼤于根节点的值

• 它的左右⼦树也分别为⼆叉搜索树

2. 查找

3. 插入

插入步骤

1. 如果树为空，则新节点成为根节点。

2. 如果树不为空

1. 从根节点开始，比较插入值与当前节点的值。

2. 根据比较结果，决定向左子树或右子树移动。

3. 重复上述过程，直到找到一个空位置（即当前节点的左子节点或右子节点为空）。

4. 将新节点插入到该空位置。

4. 删除

设待删除结点为 cur, 待删除结点的双亲结点为 parent

1. cur.left == null

     a. cur 是 root，则 root = cur.right

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

     c. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

2. cur.right == null

     a. cur 是 root，则 root = cur.left

     b. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left

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

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

• 找到右子树的最小节点（或左子树的最大节点）。

• 用最小节点的值替换被删除节点的值。

• 删除右子树的最小节点。

public class BinarySearchTree {
//创建内部类，作为节点static class Node{public int val;public Node left;public Node right;//构造方法，初始化节点public Node(int val){this.val = val;}}public Node root;//查找public boolean search(int data){if(root==null){return false;}Node cur = root;while(cur!=null){//如果大于data，右边寻找if(cur.val<data){cur = cur.right;}else if(cur.val>data){//小于data，左边寻找cur = cur.left;}else {return true;}}return false;}//插入public void insert(int data){Node node = new Node(data);//如果根节点为空if(root==null){root = node;//根节点为新节点return;}Node cur = root;Node parent = null;while(cur!=null){parent = cur;//存放父节点//向右子树移动if(cur.val<data){cur = cur.right;}else if(cur.val>data){//向左子树移动cur = cur.left;}else{return;//如果val已经存在，直接退出}}//将新节点插入到末尾空节点if(parent.val<data){parent.right = node;}else if(parent.val > data){parent.left = node;}}//删除public boolean remove(int data){if(root==null){return false;}Node cur = root;Node parent = null;//查找datawhile(cur!=null){if(cur.val<data){parent = cur;cur = cur.right;}else if(cur.val>data){parent = cur;cur = cur.left;}else {//删除delete(parent,cur);return true;}}return false;}private void delete(Node parent,Node cur){//如果cur左节点为空if(cur.left==null){//如果cur为根节点if(cur==root){root = cur.right;root.left=null;}//如果cur在左边if(parent.left==cur){parent.left = cur.right;}//如果cur在右边if(parent.right==cur){parent.right=cur.right;}}else if(cur.right==null){//cur右节点为空if(cur==root){root = cur.left;root.right=null;}if(parent.left==cur) {//在左边parent.left = cur.left;}if(parent.right==cur){//在右边parent.right = cur.right;}}else{//左右节点均不为空leftChild(parent,cur);//rightChild(parent,cur);}}//1.找到cur左节点的最右边节点private void leftChild(Node parent,Node cur){parent = cur;Node child = cur.left;while(child.right!=null){parent = child;child = child.right;}//与cur交换，再删除交换后的节点cur.val = child.val;//如果cur左节点没有右孩子if(parent.left==child){parent.left = child.left;}else{parent.right = child.left;}}//2.找到cur右节点的最左边节点private void rightChild(Node parent,Node cur){parent = cur;Node child = cur.right;//cur右节点的最左边节点while(child.left!=null){parent = child;child = child.left;}//与cur交换，再删除交换后的节点cur.val = child.val;//如果cur右节点没有左孩子if(parent.right==child){parent.right = child.right;}else{parent.left = child.right;}}
}

5. 性能分析

插⼊和删除操作都必须先查找，查找效率代表了⼆叉搜索树中各个操作的性能。

对有n个结点的⼆叉搜索树，若每个元素查找的概率相等，则⼆叉搜索树平均查找⻓度是结点在⼆叉搜索树的深度的函数，即结点越深，则⽐较次数越多。

但对于同⼀个关键码集合，如果各关键码插⼊的次序不同，可能得到不同结构的⼆叉搜索树：

最优情况下，⼆叉搜索树为完全⼆叉树，其平均⽐较次数为： O(logN)

最差情况下，⼆叉搜索树退化为单⽀树，其平均⽐较次数为：N

二叉搜索树可能为单分支树，我们可以使用AVL树（左旋，右旋，左右旋，右左旋），红黑树。

2. 搜索

Map和set是⼀种专⻔⽤来进⾏搜索的容器或者数据结构，其搜索的效率与其具体的实例化⼦类有关。

以前常⻅的搜索⽅式有：

1. 直接遍历，时间复杂度为O(N)，元素如果⽐较多效率会⾮常慢

2. ⼆分查找，时间复杂度为 O(logN) ,但搜索前必须要求序列是有序的

1. 模型

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

1. 纯 key 模型，⽐如：TreeSet , HashSet

◦ 有⼀个英⽂词典，快速查找⼀个单词是否在词典中

◦ 快速查找某个名字在不在通讯录中

2. Key-Value 模型，⽐如：TreeMap , HashMap

   统计⽂件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现     的次数>

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

3. Map 的使用

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

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

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

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

2. Map 的常⽤⽅法

int size()         返回此地图中键值映射的数量

注意：

1. Map是⼀个接⼝，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

2. Map中存放键值对的Key是唯⼀的，value是可以重复的

3. 在TreeMap中插⼊键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。

4. Map中的Key可以全部分离出来，存储到Set中来进⾏访问(因为Key不能重复)。

5. Map中的value可以全部分离出来，存储在Collection的任何⼀个⼦集合中(value可能有重复)。

6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进⾏重新插⼊。

import java.util.Collection;
import java.util.TreeMap;
import java.util.Map;
import java.util.Set;public class TestMap {public static void main(String[] args){Map<String,Integer> map = new TreeMap<>();TreeMap<String,Integer> treeMap = new TreeMap<>();//TreeMap重写了接口Map的所有方法map.put("the",3);map.put("early",5);map.put("bird",4);map.put("catches",7);map.put("the",6);//key已存在，可以改变key对应的value值map.put("worm",4);System.out.println(map.size());//返回此地图中键值映射的数量System.out.println(map.get("the"));//key存在，返回key对应的valueSystem.out.println(map.get("word"));//key不存在，返回nullSystem.out.println(map.getOrDefault("bird",0));//key存在，返回key对应的valueSystem.out.println(map.getOrDefault("time",0));//key不存在，返回自定义valueSystem.out.println(map.remove("the"));//删除key对应的映射关系，并返回key对应的value值System.out.println(map.remove("the"));//key不存在则返回nullSet<String> keyset = map.keySet();//将map中所有的key放入keyset中System.out.println(keyset);for(String s : map.keySet()){System.out.print(s+" ");}System.out.println();Collection<Integer> con =map.values();//将map中所有的value放入con中System.out.println(con);for(Integer cot:map.values()){System.out.print(cot+" ");}System.out.println();//将map中的所有映射关系放入entry中Set<Map.Entry<String,Integer>> entry = map.entrySet();System.out.println(entry);for(Map.Entry<String,Integer> entry1:map.entrySet()){System.out.println("key: "+entry1.getKey()+" ; value: "+entry1.getValue());}}
}

4. set 的使用

Set (Java Platform SE 8 )

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

1. set 的常用方法

1. Set是继承⾃Collection的⼀个接⼝类

2. Set中只存储了key，并且要求key⼀定要唯⼀

3. TreeSet的底层是使⽤Map来实现的，其使⽤key与Object的⼀个默认对象作为键值对插⼊到Map中的

4. Set最⼤的功能就是对集合中的元素进⾏去重

5. 实现Set接⼝的常⽤类有TreeSet和HashSet，还有⼀个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了⼀个双向链表来记录元素的插⼊次序。

6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插⼊

7. TreeSet中不能插⼊null的key，HashSet可以。

import java.util.*;public class TestSet {public static void main(String[] args) {Set<String> set = new TreeSet<>();TreeSet<String> treeSet = new TreeSet<>();//TreeSet重写了接口set的所有方法//为set添加元素System.out.println(set.add("the"));System.out.println(set.add("early"));System.out.println(set.add("bird"));System.out.println(set.add("catches"));System.out.println(set.add("the"));//key已存在，不添加System.out.println(set.add("worm"));System.out.println(set.size());//返回set中元素的个数System.out.println(set.isEmpty());//判断set是否为空，不为空返回false//判断元素是否存在System.out.println(set.contains("the"));//存在，trueSystem.out.println(set.contains("world"));//不存在，false//删除set中指定的元素System.out.println(set.remove("the"));//存在要删除的元素，删除并返回trueSystem.out.println(set.remove("the"));//不存在要删除的元素，返回false//创建顺序表，作为集合使用ArrayList<String> arrayList = new ArrayList<>();arrayList.add("bird");arrayList.add("worm");判断set是否包含顺序表中的所有元素System.out.println(set.containsAll(arrayList));//包含，truearrayList.add("the");System.out.println(set.containsAll(arrayList));//不包含，false//将set中的元素全部转换为数组String[] s = set.toArray(new String[0]);//原代码直接使用 set.toArray() 会返回 Object[] 而不是 String[]System.out.print(Arrays.toString(s));//打印数组System.out.println();System.out.println(set.addAll(arrayList));//将集合arraylist中的元素添加到set中,重复元素不添加//迭代器Iterator<String> it = set.iterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();set.clear();//清空集合System.out.println(set.isEmpty());//set为空，返回true}
}

5. 哈希表

1. 概念

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

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

当向该结构中：

• 插⼊元素

• 根据待插⼊元素的关键码，以此函数计算出该元素的存储位置并按此位置进⾏存放

• 搜索元素

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

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

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的⼤⼩。

⽤该⽅法进⾏搜索不必进⾏多次关键码的⽐较，因此搜索的速度⽐较快

问题：按照上述哈希⽅式，向集合中插⼊元素44，会出现冲突

2. 冲突

1. 概念

对于两个数据元素的关键字Ki 和 Kj(i != j)，有Ki != Kj，但有：Hash(Ki ) == Hash(Kj)，

即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码⽽具有相同哈希地址的数据元素称为“同义词

2. 避免

由于我们哈希表底层数组的容量往往是⼩于实际要存储的关键字的数量的，这就导致⼀个问题，冲突的发⽣是必然的，但我们能做的应该是尽量的降低冲突率。

-哈希函数设计

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

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

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

• 哈希函数应该⽐较简单

3. 常⻅哈希函数

1. 直接定制法 --(常⽤)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况使⽤场景：适合查找⽐较⼩且连续的情况

⾯试题： 387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

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. 数学分析法--(了解)

设有n个d位数，每⼀位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不⼀定相同，可能在某些位上分布⽐较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某⼏种符号经常出现。可根据散列表的⼤⼩，选择其中各种符号分布均匀的若⼲位作为散列地址。

例如：

假设要存储某家公司员⼯登记表，如果⽤⼿机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后⾯的四位作为散列地址，如果这样的抽取⼯作还容易出现 冲突，还可以对抽取出来的数字进⾏反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等⽅法。

数字分析法通常适合处理关键字位数⽐较⼤的情况，如果事先知道关键字的分布且关键字的若⼲位分布较均匀的情况

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

4. 负载因⼦调节

负载因⼦和冲突率的关系粗略演⽰：

所以当冲突率达到⼀个⽆法忍受的程度时，我们需要通过降低负载因⼦来变相的降低冲突率。

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的⼤⼩。

5. 解决

1. 闭散列

闭散列：也叫开放地址法，当发⽣哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。

1. 线性探测

⽐如上⾯的场景，现在需要插⼊元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发⽣哈希冲突。

线性探测：从发⽣冲突的位置开始，依次向后探测，直到寻找到下⼀个空位置为⽌。

插⼊

◦ 通过哈希函数获取待插⼊元素在哈希表中的位置

◦ 如果该位置中没有元素则直接插⼊新元素，如果该位置中有元素发⽣哈希冲突，使⽤线性探测找到下⼀个空位置，插⼊新元素

采⽤闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。⽐如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采⽤标记的伪删除法来删除⼀个元素。

2. ⼆次探测

线性探测的缺陷是产⽣冲突的数据堆积在⼀块，这与其找下⼀个空位置有关系，因为找空位置的⽅式就是挨着往后逐个去找，因此⼆次探测为了避免该问题，找下⼀个空位置的⽅法为：Hi = (H 0 +i^2)% m, 或者：Hi = (H0 - i^2)% m其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码key 进⾏计算得到的位置，m是表的⼤⼩。插⼊44：

3. 总结

1. 优点：

   • 不需要额外的数据结构（如链表），空间利⽤率⾼。

   • 实现相对简单。

   • 缓存性能好，因为数据都存储在连续的内存空间中。

   • 不需要存储指针，节省空间。

2. 缺点：

   • 容易产⽣聚集现象（尤其是线性探测）。

   • 删除操作复杂（需要特殊处理以保持查找链的完整性）。

   • 装载因⼦不能太⼤，否则性能会急剧下降。

   • ⼆次聚集（对于⼆次探测）。

2. 开散列/哈希桶

开散列法⼜叫链地址法(开链法)，⾸先对关键码集合⽤散列函数计算散列地址，具有相同地址的关键码归于同⼀⼦集合，每⼀个⼦集合称为⼀个桶，各个桶中的元素通过⼀个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发⽣哈希冲突的元素。

开散列，可以认为是把⼀个在⼤集合中的搜索问题转化为在⼩集合中做搜索了。

插入：

jdk1.8之前是头插，jdk1.8之后是尾插

key和val为int类型：

public class HashBack {//创建节点static class Node{public int key;//存放关键码public int val;//存在value值public Node next;//存在下一个节点的地址//构造方法public Node(int key,int val){this.key = key;this.val = val;}}//创建一个数组，存放具有相同地址的关键码public Node[] arr;//数组中关键码的个数public int usedSize;//构造方法public final int capacity = 1;public HashBack(){this.arr = new Node[capacity];}//插入数据public void put(int keys,int value){//判断负载因子loadFactor();//尾插//lastPut(keys,value);//头插headPut(keys,value);}private void lastPut(int keys,int value){int n = keys % arr.length;//寻找关键码的地址//如果头节点为空，将新节点作为头节点if(arr[n]==null){arr[n] = new Node(keys,value);}else{Node cur = arr[n];Node parent = null;while(cur!=null){parent = cur;//保存当前节点的地址if(cur.key==keys){cur.val = value;//更新value值return ;}cur = cur.next;//更新节点}//创建新节点Node node = new Node(keys,value);parent.next = node;//尾插}usedSize++;}//头插private void headPut(int keys,int value){int n = keys % arr.length;//计算关键码地址Node cur = arr[n];//查找keys是否存在while(cur!=null){if(cur.key == keys){cur.val = value;return;}cur = cur.next;}Node node = new Node(keys,value);//创建新节点//头插node.next = arr[n];arr[n] = node;usedSize++;}//判断负载因子private void loadFactor(){double factor = (usedSize+1)*1.0/arr.length;if(factor<=0.75){return;}//大于0.75，2倍扩容Node[] temp = new Node[2*arr.length];int n = temp.length;//将cur中的节点全部放入temp中for(int i =0;i<arr.length;i++){Node cur = arr[i];while (cur!=null){Node curNext = cur.next;//保存下一个节点地址//计算该cur中的关键码的地址int k = cur.key % n;//头插cur.next = temp[k];temp[k] = cur;cur = curNext;//更新节点}}arr = temp;}//获取keys对应的valpublic int get(int keys){int n = keys % arr.length;Node cur = arr[n];while (cur!=null){if(cur.key == keys){return cur.val;}cur = cur.next;}return -1;}//删除数据public int remove(int keys){//此步骤可以不用，因为在实例化对象时，我们已经将数组实例化，不可能为null
//        if(arr==null){
//            return -1;
//        }int n = keys % arr.length;Node cur = arr[n];Node parent = cur;while(cur!=null){//如果要删除的是头节点if(arr[n].key==keys){arr[n] = arr[n].next;usedSize--;return cur.val;}if(cur.key == keys){parent.next = cur.next;usedSize--;return cur.val;}parent = cur;cur = cur.next;}return -1;}
}

key和val不为int类型：需要重写equals和hashcode方法

import java.util.Objects;//创建学生类
class Student{public String name;//构造方法public Student(String name){this.name = name;}//重写equals方法，比较值是否相同@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return Objects.equals(name, student.name);}//重写hashCode方法，获取对象地址@Overridepublic int hashCode() {return Objects.hashCode(name);}
}
public class CEHashBack<K,V> {//创建静态内部类，作为节点static class Node<K,V>{public K key;//存放关键码public V val;//存放value值public Node<K,V> next;//存放下一个节点地址//构造方法public Node(K key,V val){this.key = key;this.val = val;}}public Node<K,V>[] arr;//创建存放节点地址数组public int usedSize;//数组中节点个数public final double loadFactor = 0.75;//负载因子的最大值public final int capacity =10;//初始化数组长度//构造方法public CEHashBack(){this.arr = (Node<K, V>[]) new Node[capacity];//实例化数组}//插入(头插）public void put(K key,V val){if(key==null){System.out.println("key为空,无法插入");return;}if((double)(usedSize+1)/arr.length>loadFactor){expansion();//2倍扩容}int hash = Math.abs(key.hashCode());//防止为负数int n = hash % arr.length;//求key对应的数组下标Node<K,V> cur = arr[n];//查找key是否存在while(cur!=null){if(cur.key.equals(key)){cur.val = val;return;}cur = cur.next;}Node<K,V> node = new Node<>(key,val);//创建新节点//头插node.next = arr[n];arr[n] = node;usedSize++;}//2倍扩容private void expansion(){//创建一个新2倍数组Node<K,V>[] temp = (Node<K, V>[])new Node[2*arr.length];//将arr中的节点全部放入temp中for(int i=0;i< arr.length;i++){Node<K,V> cur =arr[i];while(cur!=null){int hash = Math.abs(cur.key.hashCode());//计算关键码的数字地址(防止为负数）int n = hash % temp.length;//在新数组中的下标Node<K,V> curNext = cur.next;//保存下一个节点地址//头插cur.next = temp[n];temp[n] =cur;cur = curNext;//更新节点}}arr = temp;//更新数组arr的地址}//获取key对应的valpublic V get(K key){if(key==null){System.out.print("key为空,无法查找");return null;}int hash = Math.abs(key.hashCode());int n = hash%arr.length;Node<K,V> cur = arr[n];while(cur!=null){if(cur.key.equals(key)){return cur.val;}cur = cur.next;}return null;}//删除public V remove(K key){if(key==null){System.out.print("key为空，无法删除");return null;}int hash = Math.abs(key.hashCode());int n = hash%arr.length;Node<K,V> cur = arr[n];Node<K,V> parent = null;while(cur!=null){//如果要删除头节点if(arr[n].key.equals(key)){arr[n] = arr[n].next;usedSize--;return cur.val;}if(cur.key.equals(key)){parent.next = cur.next;usedSize--;return cur.val;}parent = cur;cur = cur.next;}return null;}
}

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

刚才我们提到了，哈希桶其实可以看作将⼤集合的搜索问题转化为⼩集合的搜索问题了，那如果冲突严重，就意味着⼩集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的⼩集合搜索问题继续进⾏转化，例如：

1. 每个桶的背后是⼀棵搜索树

2. 每个桶的背后是另⼀个哈希表

3. 哈希函数重新设计

4. 如果

6. 性能分析

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

7. 和 java 类集的关系

1. HashMap 和 HashSet 即 java 中利⽤哈希表实现的 Map 和 Set

2. java 中使⽤的是哈希桶⽅式解决冲突的

3. java 会在冲突链表⻓度⼤于⼀定阈值后，将链表转变为搜索树（红⿊树）

4. java 中计算哈希值实际上是调⽤的类的 hashCode ⽅法，进⾏ key 的相等性⽐较是调⽤ key 的equals ⽅法。所以如果要⽤⾃定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写hashCode 和 equals ⽅法，⽽且要做到 equals 相等的对象，hashCode ⼀定是⼀致的。

例题：

138. 随机链表的复制 - 力扣（LeetCode）

771. 宝石与石头 - 力扣（LeetCode）

旧键盘 (20)__牛客网

692. 前K个高频单词 - 力扣（LeetCode）