数据结构_Map和Set
目录
【搜索树】
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
3、它的左右子树也分别为二叉搜索树。
一、搜索模型
搜索的数据称为关键字 (Key)，关键字对应的称为值 (Value)，将其称之为键值对 (Key-Value)。
1、纯 Key 模型
例如：有一个英文词典，查找一个单词是否在词典中。
2、Key-Value 模型
例如：有一个文件，统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>。
Map 和 Set 是一种专门用来进行动态搜索的数据结构，其搜索的效率与其具体的实例化子类有关。Map 中存储的就是 Key-Value，而 Set 中只存储了 Key。
二、Map
Map 是一个接口类，该类没有继承自 Collection，该类中存储的是 <K,V> 结构的键值对，并且 K 一定是唯一的，不能重复。
2.1 Map.Entry
Map.Entry<K,V> 是 Map 内部实现的用来存放 <key,value> 键值对映射关系的内部类，可以理解为一个存放键值对的容器。
| 方法 | 说明 |
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 将键值对中的 value 替换为指定的 value |
注：Map.Entry<K,V> 中并并没有提供设置 Key 的方法。
2.2 Map 方法
| 方法 | 说明 |
| V get(Object key) | 返回 key 对应的 value |
| V getOrDefault(Object key, V defaultValue) | 返回 key 对应的 value，key 不存在，返回默认值 |
| V put(K key, V value) | 设置 key 对应的 value |
| V remove(Object key) | 删除 key 对应的映射关系 |
| Set<K> keySet() | 返回所有 key 的不重复集合 |
| Collection<V> values() | 返回所有 value 的可重复集合 |
| Set<Map.Entry<K, V>> entrySet() | 返回所有的 key-value 映射关系 |
| boolean containsKey(Object key) | 判断是否包含 key |
| boolean containsValue(Object value) | 判断是否包含 value |
2.3 Map 注意事项
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，需先删除再重新插入。
【TreeMap 和 HashMap 的区别】
| Map底层结构 | TreeMap | HashMap |
| 底层结构 | 红黑树 | 哈希桶 |
| 插入/删除/查找时间复杂度 | O(1) | |
| 是否有序 | 关于Key有序 | 无序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
| 比较与覆写 | key 必须能够比较，否则会抛出 ClassCastException 异常 | 自定义类型需要覆写 equals 和 hashCode 方法 |
| 应用场景 | 需要 Key 有序场景下 | Key 是否有序不关心，需要更高的时间性能 |
三、Set
Set 与 Map 主要的不同有两点：
1、Set 是继承自 Collection 的接口。
2、Set 中只存储了 Key。
3.1 Set 方法
| 方法 | 说明 |
| boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判断 o 是否在集合中 |
| Iterator<E> iterator() | 返回迭代器 |
| boolean remove(Object o) | 删除集合中的 o |
| int size() | 返回 set 中元素的个数 |
| boolean isEmpty() | 检测 set 是否为空，空返回 true，否则返回 false |
| Object[] toArray() | 将 set 中的元素转换为数组返回 |
| boolean containsAll(Collection<?> c) | 集合 c 中的元素是否在 set 中全部存在，是返回 true，否则返回 false |
| boolean addAll(Collection<? extends E> c) | 将集合 c 中的元素添加到 set 中，可以达到去重的效果 |
3.2 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 可以。
【TreeSet 和 HashSet 的区别】
| Set底层结构 | TreeSet | HashSet |
| 底层结构 | 红黑树 | 哈希桶 |
| 插入/删除/查找时间复杂度 | O(1) | |
| 是否有序 | 关于 Key 有序 | 不一定有序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找区别 | 按照红黑树的特性 | 通过哈希函数计算哈希地址 |
| 比较与覆写 | key 必须能够比较，否则会抛出 ClassCastException 异常 | 自定义类型需要覆写 equals 和 hashCode 方法 |
| 应用场景 | 需要 Key 有序场景下 | Key 是否有序不关心，需要更高的时间性能 |
四、哈希表
4.1 哈希表
哈希(散列)方法可以通过哈希(散列)函数使元素的存储位置与它的关键码之间建立一一映射的关系，构造出哈希表(散列表)。哈希表可以在查找时不经过任何比较，一次直接从表中得到要搜索的元素。
例如：数据集合 {1，5，3，7，6，9}；
哈希函数设计为：hash(key) = key % capacity，capacity 为存储元素空间总大小。由此计算出该元素的哈希地址，即可存储该元素。
可以看出，使用哈希方法进行搜索不用进行多次关键码的比较，搜索速度很快。可若往数据集合中插入元素 17，由于 17 % 10 = 7，故元素 7 与元素 17 会产生冲突。
4.2 冲突
不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突 (哈希碰撞)。
把具有不同关键码二具有相同哈希地址的数据元素称为"同义词"。
4.3 哈希函数设计
由于哈希表容量小于实际要存储的关键字数量，所有发生冲突是必然的，我们能做的只是尽量降低冲突率。
引起哈希冲突的一个原因：哈希函数设计不够合理，哈希函数设计原则：
1、哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
2、哈希函数计算出来的地址能均匀分布在整个空间中。
3、哈希函数应该比较简单。
【常见哈希函数】
1、直接定制法
取关键字的某个线性函数为哈希地址：hash(Key) = A*key + B。
优点：简单、均匀。
缺点：需要事先知道关键字的分布情况。
使用场景：适合查找比较小且连续的情况。
2、除留余数法
设哈希表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：hash(key) = key % p(p<=m)，将关键码转换成哈希地址。
【负载因子调节】
哈希表的载荷因子定义为：α = 存入表中的元素个数 / 哈希表的长度。
α 是哈希表装满程度的标志因子。由于表长是定值，故 α 与 "存入表中的元素个数" 成正比，α 越大，"存入表中的元素个数" 越多，产生冲突的可能性就越大。故为了降低冲突率，当 α 达到一定程度时，我们需要扩容 "哈希表的长度"。例如，Java 的系统库中限制了载荷因子为 0.75，超过此值将 resize 哈希表。
解决哈希冲突的两种常见方法是：闭散列和开散列。
4.4 闭散列
闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的"下一个"空位置中去。故又有了两种方法将冲突的元素存至其他位置。
1、线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
例如上文中，需要再插入元素 17，此时通过哈希函数计算出哈希地址为 7，但发生了哈希冲突。故用到线性探测，寻找到下标 8 为空，存入元素 17。
若再插入元素 27，即继续线性探测，寻找到下标 0 为空，存入元素 27。
2、二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，因此二次探测为了避免该问题，找"下一个"空位置的方法为：
，其中 i = 1,2,3,……，
是通过哈希函数计算得到的哈希地址，m 是表的大小。
故若插入元素 17 发生哈希冲突，使用二次探测：
闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
4.5 开散列/哈希桶
开散列法又叫链地址法(开链法)，首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。此时插入元素 17 和 27 会得到：
开散列，可以理解为把一个在大集合中的搜索问题转化为在小集合中的搜索。
【哈希表时间复杂度】
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。
总结
1、Map 和 Set 是一种专门用来进行动态搜索的数据结构。
2、Map 中存储的就是 Key-Value，而 Set 中只存储了 Key。
3、不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突 (哈希碰撞)。
4、开散列中每个桶中放的都是发生哈希冲突的元素。
5、哈希表的插入/删除/查找时间复杂度是 O(1)。
原文地址：https://blog.csdn.net/m0_73620971/article/details/140550669
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！