长沙网站设计多少钱一个月,网站写手怎么做,wordpress自建会员,网站排名的重要性Set集合, 不能重复,不能修改,顺序无关,可以直接遍历(实现了 Iterable接口)
Map 映射表, 键值对 key - value 随时根据 key 找到对应的 value, 针对 key,也要求不能重复,不能修改,顺序无关.对 value 也无要求 put 插入新的键值对/键已经存在,修改 value get 根据 key 获取到 v…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 就要触发扩容
