目录
1. Map的使用
1.1 Map常用方法
2. Set的使用
2.1 Set常见方法
3. 二叉搜索树(BST)
4. 哈希表
4.1 哈希冲突
4.2 避免哈希冲突
4.2.1 哈希函数的设计
4.2.2 负载因子调节
4.3 解决哈希冲突
4.3.1 开散列(哈希桶)(重点掌握)
4.3.2 闭散列(开放定址法)
1. Map的使用
![](https://img-blog.csdnimg.cn/2c58dfb7d5454c53bc239b849aca455b.png)
Map 是一个接口类,该类没有继承自Collection ,该类中存储的是<K , V>结构的键值对,并且K一定是唯一的,不能重复。
1.1 Map常用方法
返回 key 对应的 value
map.get(key);
返回 key 对应的 value,key 不存在,返回默认值
map.getOrDefault(key, map.get(key, 0) + 1);
设置 key 对应的
value
map.put(key,value);
删除 key 对应的映射关系
map.remove(key);
返回所有 key 的不重复集合
Set<key> keySet();
遍历map集合
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue() == 1) {
return entry.getKey();
}
}
判断是否包含 key
if(containsKey(key)) {}
判断是否包含 value
if(containsKey(value)) {}
注意:
1.
Map
是一个接口,
不能直接实例化对象
,如果
要实例化对象只能实例化其实现类
TreeMap
或者
HashMap。
2.
Map
中存放键值对的
Key
是唯一的,
value是可以重复的
。
3.
在
Map
中插入键值对时,
key不能为空
,否则就会抛
NullPointerException
异常
,但是
value可以为空。
4.
Map
中的
Key
可以全部分离出来,存储到
Set
中
来进行访问
(
因为
Key
不能重复
)
。
5.
Map
中的
value
可以全部分离出来,存储在
Collection
的任何一个子集合中
(value
可能有重复
)
。
6. Map
中键值对的
Key
不能直接修改,
value
可以修改,如果要修改
key
,只能先将该
key
删除掉,然后再来进行重新插入。
Map底层结构 |
TreeMap |
HashMap |
底层结构 |
红黑树 |
哈希桶 |
插入/删除/查找时间 复杂度 |
O(logN)
|
是否有序 |
关于Key有序
|
无序 |
线程安全 |
不安全 |
不安全 |
插入/删除/查找区别 |
需要进行元素比较 |
通过哈希函数计算哈希地址 |
比较与覆写 |
key必须能够比较,否则会抛出 ClassCastException异常 |
自定义类型需要覆写equals和 hashCode方法 |
应用场景 |
需要Key有序场景下 |
Key是否有序不关心,需要更高的 时间性能 |
2. Set的使用
Set与Map主要的不同有两点:Set是继承自Collection的接口类,Set中只存储了Key。
2.1 Set常见方法
添加元素,但重复元素不会被添加成功
set.add(x);
清空集合
set.clear();
判断 x是否在集合中
if(set.contains(x)) {}
删除集合中的 x
boolean remove(x)
返回set中元素的个数
int size = set.size();
检测set是否为空,空返回true,否则返回false
if(set.isEmpty()) {}
将set中的元素转换为数组返回
Object[] toArray()
集合c中的元素是否在set中全部存在,是返回true,否则返回 false
boolean containsAll(Collection<?> c)
注意:
1. Set是继承自Collection的一个接口类。
2. Set中只存储了key,并且要求key一定要唯一。
3. Set的底层是使用Map来实现的。
4. Set最大的功能就是对集合中的元素进行去重。
5. 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet(是在HashSet的基础上维护了一个双向链表来记录元素的插入次序)
。
6. Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入
7. Set中不能插入null的key
。
Set底层结构 |
TreeSet |
HashSet |
底层结构 |
红黑树 |
哈希桶 |
插入/删除/查找时间 复杂度 |
O(logN) |
是否有序 |
关于Key有序 |
不一定有序 |
线程安全 |
不安全 |
不安全 |
插入/删除/查找区别 |
按照红黑树的特性来进行插入和删除 |
1. 先计算key哈希地址 2. 然后进行 插入和删除 |
比较与覆写 |
key必须能够比较,否则会抛出 ClassCastException异常 |
自定义类型需要覆写equals和 hashCode方法 |
应用场景 |
需要Key有序场景下 |
Key是否有序不关心,需要更高的 时间性能 |
3. 二叉搜索树(BST)
二叉搜索树又称二叉排序树,它或者是一棵空树
,或者是具有以下性质的二叉树
:
1. 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树
1. 中序遍历得到的数组是升序的
2. 不一定是个完全二叉树
4. 哈希表
顺序结构以及平衡树
中,元素关键码与其存储位置之间没有对应的关系,因此在
查找一个元素时,必须要经过关键
码的多次比较
。
顺序查找时间复杂度为O(N)
,
平衡树中为树的高度,即O( logN)
,搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以
不经过任何比较,一次直接从表中得到要搜索的元素
。
如果构造一种存储结构,通过某种函
数
(hashFunc)
使
元素的存储位置
与它的
关键码之间
能够建立一一映射的关系,那么在查找时通过该函数可以很快
找到该元素
。
1. 插入元素 :根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
2.
搜索元素:
对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若
关键码相等,则搜索成功。
该方式即为
哈希(散列)方法
,
哈希方法中使用的转换函数称为
哈希(散列)函数
,构造出来的结构称为
哈希表
(Hash
Table)(
或者称散列表
)
例如:数据集合
{1
,
7
,
6
,
4
,
5
,
9}
;
哈希函数设置为:
hash(key) = key % capacity
; capacity
为存储元素底层空间总的大小。
![](https://img-blog.csdnimg.cn/afa060c9779d432f8368ce41cb231515.png)
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
4.1 哈希冲突
key1 != key2 , hash(key1) == hash(key2)
不同关键字通过相同哈
希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞
。
4.2 避免哈希冲突
引起起哈希冲突的一个原因可能是:哈希函数设计不够合理。
4.2.1 哈希函数的设计
key 为整型的时候哈希函数的设计:取模(一般来说,取模使用素数)
哈希函数设计的三个要求:
1. 一致性:无论经过多少次的哈希函数运算,key不变,hash值不变
2. 高效性:哈希函数的运算不能太耗时,尽量可以立即计算得出
3. 均匀性:比如说,通过哈希函数运算之后,得到的值分布在【0,1】区间上,这就不均匀
4.2.2 负载因子调节
负载因子 = 元素个数 / 数组长度
当元素个数 >= 数组长度 * 负载因子,此时认为哈希表中冲突比较多。
负载因子越大,冲突几率越大,效率越低。
负载因子越小,冲突几率越小,但浪费空间。
4.3 解决哈希冲突
当发生哈希冲突时,最常见的两种处理方式:
1. 开散列(拉链法 / 链地址法)
2. 闭散列
4.3.1 开散列(哈希桶)(重点掌握)
开散列法又叫链地址法 (拉链法)
首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
![](https://img-blog.csdnimg.cn/f7ce32f875b34d9486756c7cb1000fea.png)
大部分工程都使用链地址法来解决哈希冲突问题。
链表的长度不会很长,控制在常量范围内。
JDK1.8之后,当链表的长度超过8,这个链表就会变成红黑树,时间复杂从O(N) 变成O(logN)
性能:
虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的, 也就是每个桶中的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。
public class HashBuck {
static class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key =key;
this.val = val;
}
}
public Node[] array;
public int usedSize;
public static final double DEFAULT_LOADFACTOR = 0.75;
public HashBuck(){
this.array = new Node[10];
}
public void put(int key, int val) {
//1. 找到key所在的位置
int index = key % this.array.length;
//2. 遍历这个下标的链表,看是不是有相同的key(更新val)
Node cur = array[index];
while(cur != null) {
if(cur.key == key) {
cur.val = val;
return;
}
cur = cur.next;
}
//3. 没有这个key元素,头插法
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4. 插入元素成功之后,检查当前散列表的负载因子
if(loadFactor() > DEFAULT_LOADFACTOR) {
resize(); //负载因子大于0,75 扩容
// 注意:如果扩容数组,那么数组里面的每个链表上的元素都要重新进行哈希
}
}
/**
* 扩容
*/
private void resize() {
Node[] newArray = new Node[array.length * 2];
for (int i = 0; i < array.length; i++) { //遍历原来的数组
Node cur = array[i];
while(cur != null) {
int index = cur.key % newArray.length; // 获取新的下标
//把cur这个节点以头插或者尾插的形式,插入到新的数组对应的链表下标中
Node curNext = cur.next;
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
}
private double loadFactor() {
return 1.0 * usedSize / array.length;
}
/**
* 根据key获取value值
* @param key
* @return
*/
public int get(int key) {
//1. 找到key所在的位置
int index = key % this.array.length;
//2. 遍历这个下标的链表,看是不是有相同的key(更新val)
Node cur = array[index];
while(cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;
}
}
4.3.2 闭散列(开放定址法)
闭散列:也叫
开放定址法
,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以
把
key
存放到冲突位置中的
“
下一个
”
空位置中去。
如何寻找下一个空位置呢?
1.
线性探测
例如:数据集合
{1
,
7
,
6
,
4
,
5
,
9}
;
哈希函数设置为:
hash(key) = key % capacity
; capacity
为存储元素底层空间总的大小。
现在需要插入元素
44
,先通过哈希函数计算哈希地址,下标为
4
,因此
44
理论上应该插在该
位置,但是该位置已经放了值为
4
的元素,即发生哈希冲突。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
会发现此时,把冲突的元素都放在一块。
2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:
i 表示第几次冲突