目录
【搜索树】
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
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)。