字体排版网站桂林漓江悦府
Set集合, 不能重复,不能修改,顺序无关,可以直接遍历(实现了 Iterable接口)
Map 映射表, 键值对 key - value
随时根据 key 找到对应的 value, 针对 key,也要求不能重复,不能修改,顺序无关.对 value 也无要求
put 插入新的键值对/键已经存在,修改 value
get 根据 key 获取到 value ,如果 key 不存在,返回 null
不可以直接遍历, 想要遍历就把 Map 转成 entrySet
Map 和 Set 都是有两种实现的
TreeMap/TreeSet => 二叉搜索树
HashMap/HashSet => 哈希表
哈希表
1.工作中最常用
2.面试中最常考
虽然 Set 和 Map 提供了两种实现,实际上 Tree 系列使用的频率非常少,主要都是 Hash 系列
二叉搜索树,目的是为了高效的查找,对于红黑树这样的平衡二叉搜索树, 查询的时间复杂度O(logN)
哈希表这个数据结构,也是高效查找,查找的时间复杂度O(1),插入时间复杂度,也是O(1)
场景:给定一个整型数组(任意长度),约定这个数组里面的元素的范围是 0 - 99, 统计这个数组中 每次数字,出现的次数
其实可以通过"键值对"这样的方式来表示完成的
把每个要统计的数字,作为"键"
该数字出现的次数,作为"值"
如果不使用键值对的方案,还有另一个办法,使用数组
int[] arr = new int[100]
使用数组下标表示要统计的整数是啥, 数组的元素,表示该下标出现的次数
如果这个数据的范围更大?
如果这个数据里面存在负数/小数?
如果这个数据里面存在字符串?
需要有一系列的手段,把要表示的元素,进行转换到数组的下标上(这个转换过程,称为"哈希函数")
如果任意的 int -21亿 => +21亿, 通过一系列数学变化,把这个 int 映射到一个相对较小的数组下标上,不需要创建 int[] count = new int[42亿],只创建一个 new int[10000](这样的用来表示映射关系的数组就称为 哈希表)
哈希表 O(1) 的奥秘,在于核心操作,就是数组访问下标.哈希函数(原始的值 => 下标转换过程)通常也是 O(1)根据下标进行增删改查,也是O(1)
此处存在"空间不对等"问题.如果要存储的是任意整数,范围 42亿个.此时要创建的保存的数据的数组,范围 1w 个,此时,一定存在重复,两个不同的数据,映射到同一个数组下标上了(哈希冲突)
举个具体的例子: 对于 key 为整数来说, 一个常见的 hash 函数的设计方式, 直接求余数
key 的范围是 0 => 42亿
哈希表的数组长度是 1w
hash函数 => key % 1w
10001
20001
30001
都映射到下标为 1
哈希表设计中的一个关键要点,如何解决哈希冲突
哈希冲突的解决方案:
1.闭散列
这个过程"线性探测", 挨着一个一个的往后找空闲位置
此时来了一个数字 10001 % 1w => 1
此时再来一个数字 20001 % 1w => 1 发现下标 1 不在空闲,就继续往后找,找到空闲位置
如果再来一个数字 30001 % 1w => 1 发现下标 1 不在空闲,发现 下标 2 也不空闲,就找到下标 3 就放到下标 3 上
如果在来一个 30002 % 1w => 发现下标为 2 不空闲, 下标 3 不空闲,放到下标 4 上
还可以采取其他的往后找的方式,不过闭散列 这样的方案,基本上没有实用价值, 开发中真实实用的哈希表没有用闭散列
2.开散列
会确保哈希函数计算的下标是准确位置, 使用一个链表,保存"冲突"的元素, 此时,这个数组的每个元素,都是"链表节点"
计算 哈希函数,任然是O(1)
但是如果进行查找/删除,就有可能会遍历这个链表...这个时候,时间复杂度还是O(1)吗?
可以通过一些手段,限制链表的最大长度(虽然是链表,但是长度非常短)
此处的链表,不是"长度为N" 的链表,而是有限长度的链表
负载因子 = 整个哈希表保存的元素个数 / 数组的长度 (相当于链表的平均长度)
实践中可以根据负载因子,设定阈值,随着哈希表元素个数的增加,使得哈希表元素个数增加,使得负载因子到达阈值,就会自动触发扩容操作
哈希表,本质上是利用了数组下标操作比较高效的特点,实现的一个数据结构.通过哈希表,把要保存的内容,映射到数组下标上.如果出现冲突,在开散列的方式,来解决冲突(哈希表的设定是一个数学问题)
对于 Java 标准库的 HashMap 来说,还有一些额外的优化手段
扩容,本身也是有一定成本的(大量的元素的拷贝),尤其是,还可能会出现一些极端的情况.比如,整体链表的平均长度不是很长,在阈值之下,但是个别的链表长度特别长(小概率)
Java 的 HashMap 会在元素往链表上插入的时候 做一个判定,判定如果当前链表达到一定的值,就直接把链表转化成 红黑树
HashMap 标准库中 ,要求 0.75 就要触发扩容