看到这句话的时候证明：此刻你我都在努力
加油陌生人
前言
至今为止已经写了9篇Java实现数据结构的文章了，更新的都是初阶的数据结构，今天要更新的是Map与Set，在这篇文章中会详细讲到Map与Set的关系，以及用TreeMap与HashMap是实现有什么区别。更完这一篇，初阶的数据结构也就快要更完了，预计也就有两三篇也就完成了数据结构初阶的文章了。
什么是Map
在数据结构中，Map 是一种关联容器，它存储了键值对（key-value pairs），并且每个键在 Map 中都是唯一的。Map 提供了通过键快速访问其对应值的能力。简单通俗的说就是，记录两个不同类型的值，一个被定义为键（Key），一个被定义为值（value），其中Key是唯一的，也就是说在Map中的·Key是不允许重复出现的，但value是可以的。
简单代码举例：
如下代码，所谓的Key就是String，value就是Integer。
import java.util.Map; import java.util.TreeMap; public class Test { public static void main(String[] args) { Map<String,Integer> map=new TreeMap(); map.put("小狗",5); map.put("小猫",9); } }
那么肯定有人就会问了，这有什么用呢？记录的作用是什么？那么我们就往下看。
Map的作用：
Map的用途是比较广泛的目前我们常见的就是标红的那些：
- 缓存：Map 可以用来实现缓存系统，其中键是请求的标识符，值是请求的结果。这样可以快速检索之前请求的结果，避免重复计算。
- 计数器：Map 可以用来计数，例如统计文本中每个单词的出现次数，键是单词，值是对应的计数。
- 数据库索引：Map 可以用于实现数据库索引，其中键是搜索条件，值是指向数据库中记录的指针。
- 查找表：Map 可以作为查找表，例如汇率转换，键是货币代码，值是对应的汇率。
- 配置存储：Map 可以用来存储配置信息，其中键是配置项的名称，值是配置项的值。
- 对象属性存储：在某些情况下，Map 可以用来存储对象的属性，特别是当对象属性的集合不是预先定义的，或者属性的数量很大时。
- 会话管理：在 Web 应用程序中，Map 可以用来存储用户会话信息，其中键是会话ID，值是用户会话对象。
- 唯一性检查：Map 可以用来检查数据的唯一性，例如，确保数据库中的用户名是唯一的。
- 多键查找：Map 可以用于需要根据多个键查找数据的场景，例如，根据用户的多个属性（如年龄和地区）来查找用户。
- 状态管理：在某些应用程序中，Map 可以用来管理应用程序的状态，其中键是状态的名称，值是状态的值。
- 路由表：在网络编程中，Map 可以用于实现路由表，其中键是目标地址，值是路由信息。
- 依赖注入：在依赖注入框架中，Map 可以用来存储依赖项，其中键是依赖项的类型，值是依赖项的实例。
- 国际化：Map 可以用于实现国际化，其中键是语言代码，值是翻译后的文本。
- 权限控制：Map 可以用于权限控制，其中键是用户ID或角色，值是权限列表。
- 对象池：Map 可以用于实现对象池，其中键是对象类型，值是对象实例的集合。
Map的接口操作
在 Java 中，Map 是一个接口，它定义了映射的基本操作。Map 接口的实现类，如 HashMap、TreeMap 和 LinkedHashMap。
了解 Map.Entry
Map.Entry 是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了 的获取，value的设置以及Key的比较方式。
K getKey() // 返回 entry 中的 key
V getValue() //返回 entry 中的 value
V setValue(V value) // 将键值对中的value替换为指定value
基本方法：
- put(K key, V value)：将指定的值与此 Map 的指定键关联。
map.put(key, value);
- get(Object key)：返回指定键所映射的值。
V value = map.get(key);
- remove(Object key)：如果存在一个键的映射关系，则将其从 Map 中移除。
map.remove(key);
- containsKey(Object key)：如果 Map 包含指定的键，则返回
true。
boolean containsKey = map.containsKey(key);
- containsValue(Object value)：如果 Map 包含指定的值映射，则返回
true。
boolean containsValue = map.containsValue(value);
- keySet()：返回 Map 中包含的键的 Set 视图。
Set<K> keys = map.keySet();
- values()：返回 Map 中包含的值的 Collection 视图。
Collection<V> values = map.values();
- entrySet()：返回 Map 中包含的键值映射关系的 Set 视图。
Set<Map.Entry<K, V>> entries = map.entrySet();
- isEmpty()：如果 Map 为空，则返回
true。
boolean isEmpty = map.isEmpty();
- size()：返回 Map 中键值映射关系的数目。
int size = map.size();
示例代码：
import java.util.HashMap; import java.util.Map; public class MapExample { public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(); map.put("apple", 1); map.put("banana", 2); map.put("cherry", 3); System.out.println("Get value for 'apple': " + map.get("apple")); System.out.println("Contains 'banana': " + map.containsKey("banana")); System.out.println("Values: " + map.values()); System.out.println("Entry Set: " + map.entrySet()); System.out.println("Key Set: " + map.keySet()); map.remove("cherry"); System.out.println("After removing 'cherry': " + map); } }
TreeMap实现Map
要想了解如何用数实现Map，那么现在就必须认识二叉搜索树。因为TreeMap就是利用二叉搜索树来实现的
二叉搜索树
节点的左子树只包含小于当前节点的键。
节点的右子树只包含大于当前节点的键。
左子树和右子树也必须分别为二叉搜索树。
通俗点来说就是一个这颗树的每个节点的左树都比自身节点小，右树都比自身小，如下：
那么了解完二叉搜索树我们来模拟实现一下实现二叉搜索的一些方法。
我们主要模拟实现插入，搜索，移除接口 。
搜索接口（search）
解析：
从根节点出发，对比当前cur节点的key与目标key的大小，如果 cur.key>key，那么就往左遍历，要是小于就往右走，直到相等，即找到对应的节点了，返回该节点即可。如果遍历完毕还是没有找到就返回null。
public Node search(int key){ Node cur=root; while(cur!=null){ if(cur.key==key){ return cur; }else if(cur.key>key) { cur=cur.left; }else { cur=cur.right; } } return null; }
插入接口（insert）
解析：
类似搜索，我们不断对比cur.key与key的的大小，不断遍历到最后一个叶子节点（左右孩子都为null），然后new一个节点值为key，最后判断cur.key与key的大小，决定新插入的节点是放在左边还是右边。
public boolean insert(int key) { if (root == null) { root = new Node(key); return true; } Node cur = root; Node parent = null; while (cur != null) { if (key == cur.key) { return false; } else if (key < cur.key) { parent = cur; cur = cur.left; } else { parent = cur; cur = cur.right; } } Node node = new Node(key); if (key < parent.key) { parent.left = node; } else { parent.right = node; } return true; }
移除接口（remove）
最难的接口其实是删除接口。
解析：首先我们先是找到要删除的节点，要是没找到直接返回false即可，当然找的时候我们也要在建一个变量prev来记录其父节点，在然后我这里采用的是替换删除法，也就是说我们的删除并不是删除正真意义上的删除该节点而是选择另一个一个合适的节点来替换掉它，那么怎么找到一个合适的节点放到这个位置还能是这颗树还是一颗二叉搜索树。这里就不绕了，我们直接找要删除的节点的左孩子的最右的那个节点。比如下面这棵树要删除5就找到左孩子2，最右边的孩子那就是4，我们把4的节点的值替换到5那里，这样他还是一棵搜索二叉树。最后在讲原本4这个节点直接删除掉即：将3的有孩子置为null。
当然这样删除时需要注意三种情况：
- 要删除的节点左孩子为null。即删除8的情况。
- 要删除节点的左孩子的有孩子为null。即删除7的情况
- 另一种就是正常情况，即要删除5时的情况。
public boolean remove(int key){ Node cur=root; Node prev=null; while(cur!=null){ if(cur.key==key){ break; }else if(cur.key>key) { prev=cur; cur=cur.left; }else { prev=cur; cur=cur.right; } } if(cur==null) return false; Node tail=cur.left; if(tail==null){ if(prev.right==cur){ prev.right=cur.right; return true; }else { prev.left=cur.right; return true; } } //替换交换删除法 if(tail.right==null){ cur.key=tail.key; cur.left=null; return true; } while(tail.right!=null){ prev=tail; tail=tail.right; } //替换交换删除法 cur.key=tail.key; prev.right=null; return true; }
性能分析：
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为:log2N。
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：2/N。
好了看到这里我们就了解完了二叉搜索树了。接下来我们就返回来Map了。
TreeMap方法
我们的TreeMap就是利用二叉搜索树来进行的，不过时优化过二叉搜索树，也就是红黑树。我们现在暂时还不需要了解太多。直到普通二叉搜素树即可。上面模拟的时候key是int类型，但最开始我们讲过其实key是Map.Entry内部类类型的。我们只是为了了解一下二叉搜索树才将key设置为int。
那么二叉搜索树在插入时我们也知道我们需要不断进行比较才能插入数据，所以我们在使用TreeMap实现的Map时我们就必须将我们传入的K类必须是可以比较的，及实现Comparable接口的。
那么我们在看一下使用案例：
public static void TestMap() { Map<String, String> m = new TreeMap<>(); // put(key, value):插入key-value的键值对 // 如果key不存在，会将key-value的键值对插入到map中,返回null m.put("林冲", "豹子头"); m.put("鲁智深", "花和尚"); m.put("武松", "行者"); m.put("宋江", "及时雨"); String str = m.put("李逵", "黑旋风"); System.out.println(m.size()); System.out.println(m); // put(key,value): 注意key不能为空，但是value可以为空 // key如果为空，会抛出空指针异常 //m.put(null, "花名"); str = m.put("无名", null); System.out.println(m.size()); // put(key, value): // 如果key存在，会使用value替换原来key所对应的value，返回旧value str = m.put("李逵", "铁牛"); // get(key): 返回key所对应的value // 如果key存在，返回key所对应的value // 如果key不存在，返回null System.out.println(m.get("鲁智深")); System.out.println(m.get("史进")); //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值 System.out.println(m.getOrDefault("李逵", "铁牛")); System.out.println(m.getOrDefault("史进", "九纹龙")); System.out.println(m.size()); //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN) // 按照红黑树的性质来进行查找 // 找到返回true，否则返回false System.out.println(m.containsKey("林冲")); System.out.println(m.containsKey("史进")); // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N) // 找到返回true，否则返回false System.out.println(m.containsValue("豹子头")); System.out.println(m.containsValue("九纹龙")); // 打印所有的key // keySet是将map中的key防止在Set中返回的 for (String s : m.keySet()) { System.out.print(s + " "); } System.out.println(); // 打印所有的value // values()是将map中的value放在collect的一个集合中返回的 for (String s : m.values()) { System.out.print(s + " "); } System.out.println(); // 打印所有的键值对 // entrySet(): 将Map中的键值对放在Set中返回了 for (Map.Entry<String, String> entry : m.entrySet()) { System.out.println(entry.getKey() + "--->" + entry.getValue()); } System.out.println(); }
HashMap实现Map
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键 码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中： 插入元素 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若 关键码相等，则搜索成功该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
那么假设真如上方所示我们搜索想要的值时是不是简单许多，找4就是arr[4]。当然这只是简单示例。真正的Hash是经过许多优化和调整的。
冲突
什么是冲突呢？ 对于两个数据元素的关键字 和 (key1!=key2)， ，但有：Hash(key1 ) == Hash(key2 )，即：不同关键字通过相同哈 希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
就比如上面的hash(key)=key%capacity，key=1时和key=10时结果都是1，那么这个就是冲突。
注意：冲突无法避免，我们可以减少冲突的发生。也可以解决冲突所带来的问题。
如何减少冲突发生
一、哈希函数的优化
1.直接定制法（常用）
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
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为随机数 函数。
二、负载因子的调节（重点掌握）
在哈希表中，负载因子（Load Factor）是一个重要的概念，它用来衡量哈希表中已存储元素的密度。具体来说，负载因子是已存储元素的数量与哈希表的容量之间的比率。
定义：
n 是哈希表中已存储的元素数量。
m 是哈希表的总容量（即桶的数量）。
重要性：
1.查找效率：
较低的负载因子（例如，< 0.7）通常意味着较少的碰撞，这样查找操作的效率较高。
较高的负载因子（例如，> 0.7）可能导致更多的碰撞，从而降低查找效率。
2.扩展与收缩：
当负载因子超过某个阈值时（如 0.7），许多哈希表实现会自动扩展哈希表的容量，以减少碰撞的发生。这通常会涉及到重新哈希，即将现有的元素重新分配到新的桶中。
有些实现还可能在负载因子过低时（例如，< 0.2）进行收缩，以节省内存。
3.内存使用：
负载因子越高，内存利用率越高，但性能可能下降。反之，负载因子较低时，虽然性能更好，但可能会浪费内存。
如何选择负载因子
- 如果频繁插入和删除操作，可能希望使用较低的负载因子，以保持较高的查找性能。
- 如果内存资源有限，可以接受较高的负载因子，以节省内存。
注意：一般情况我们都是选择负载因子为0.7-0.8，在Java中的定义为0.75.
负载因子是哈希表设计中的一个关键参数，它直接影响到数据结构的性能和效率。理解和合理设置负载因子可以帮助优化哈希表的使用效果。
三、解决冲突问题
1.闭散列
在哈希表中，闭散列（Closed Hashing 或 Open Addressing）是一种处理哈希冲突的方法。当两个或多个元素映射到哈希表的同一个索引位置时，闭散列通过在哈希表内部寻找其他空位置来解决冲突。
线性探测（Linear Probing）
线性探测是最简单的闭散列方法。当发生冲突时，哈希表会逐个检查后续的位置（即当前位置 + 1, + 2, ...）直到找到一个空位。
哈希函数 h(k) = k % m ，如果冲突，检查 h(k) + 1, h(k) + 2, ...，直到 h(k) + n是空的，然后将此地方作为索引位置。
二次探测（Quadratic Probing）
与线性探测不同，二次探测在发生冲突后使用平方增量进行检查，如果冲突就检查h(k)+12,h(k)+22,h(k)+32
直到找到空的位置，然后将此位置作为索引位置。
优点：减少了聚集的可能性。
缺点：仍然可能导致聚集，并且需要考虑表的大小，避免形成完整的循环，空间利用率低。
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
2.开散列（哈希桶)--->重点
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
hash(key)=key%capacity;
这里capacity=10；
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
哈希桶的模拟实现
public class T { } // key-value 模型 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 size; // 当前的数据个数 private static final double LOAD_FACTOR = 0.75; public int put(int key, int value) { int index = key % array.length; // 在链表中查找 key 所在的结点 // 如果找到了，更新 // 所有结点都不是 key，插入一个新的结点 for (Node cur = array[index]; cur != null; cur = cur.next) { if (key == cur.key) { int oldValue = cur.value; cur.value = value; return oldValue; } } Node node = new Node(key, value); node.next = array[index]; array[index] = node; size++; if (loadFactor() >= LOAD_FACTOR) { resize(); } return -1; } private void resize() { Node[] newArray = new Node[array.length * 2]; for (int i = 0; i < array.length; i++) { Node next; for (Node cur = array[i]; cur != null; cur = next) { next = cur.next; int index = cur.key % newArray.length; cur.next = newArray[index]; newArray[index] = cur; } } array = newArray; } private double loadFactor() { return size * 1.0 / array.length; } public HashBucket() { array = new Node[8]; size = 0; } public int get(int key) { int index = key % array.length; Node head = array[index]; for (Node cur = head; cur != null; cur = cur.next) { if (key == cur.key) { return cur.value; } } return -1; } }
Map与Set的关系
Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
也就是你只需要学会了map就大概也就学会了set，set对比map只储存key值。方法层面也是大差不差，只要将vaule排除即可。
但Set是继承了集合类，关于集合类的一些操作Set也是可以进行的。
- Set是继承自Collection的一个接口类
- Set中只存储了key，并且要求key一定要唯一
- TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
- Set最大的功能就是对集合中的元素进行去重
- 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础
上维护了一个双向链表来记录元素的插入次序。 - Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
- TreeSet中不能插入null的key，HashSet可以。
最后最后Tree与Hash的注意事项
Tree实现的Map和Set的底层结构通常是红黑树。Hash则是哈希桶 。
TreeSet/TreeMap：关于key是有序的。 key必须能够比较，否则会抛出 ClassCastException异常 。
HashSet/HashMap： 关于key不一定有序，自定义类型需要覆写equals和 hashCode方法 。
- HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
- java 中使用的是哈希桶方式解决冲突的
- java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
- java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方
法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方
法，而且要做到 equals 相等的对象，hashCode 一定是一致的。
