数据结构_Map和Set

一、搜索模型

二、Map

2.1 Map.Entry

2.2 Map 方法

【搜索树】

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

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(\log_{2}N)$	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(\log_{2}N)$	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 哈希表。