哈希表(HashMap)或者叫做散列表,是非常常用的一种二维的键值对式的数据结构,用以非常高效的解决查询问题的。 其核心是Hashing,这是把一个对象映射到一个索引的过程,实现hashing的函数通常称为hash函数或者叫散列函数,基于hashing实现的数据结构称作HashMap,或者叫做散列表。
Hashing
哈希或者散列,是一个映射的过程,把一个对象,一些值,一些数据,一个文件等等通过某些方式映射成为一个键,用这个键可以非常快速的找到对应的值,也即原数据。通常键都是以索引形式存在的,因为用索引去查找数组的元素是绝对的O(1)时间的。但,这只是哈希过程的一个普通应用实例。
在更广泛的加密领域,哈希过程并不是为了查找,而是为了生成一种代表着原数据的签名,也就是用一个更为小巧的方便的数据(通常是字符串)作为原数据的代表,看到了签名,就认为是看到的是其原数据,当然,其实这也是一种查找过程。
所以,不失一般性,满足这样的关系hash(data) = key,就是一个hashing。还要注意这个过程是不可逆的,也就是不存在反函数g(key) = data,没有办法能从key逆推出data。
Hash
通常称作Hash,Hash function,Hash algorithm,哈希函数,哈希算法或者散列函数,散列算法。是能够实现hashing的一个函数或者算法。
哈希算法是把一个对象转化为int的过程,最为常用的一种哈希方法就是用多项式乘素法,比如一个长度为n的byte数组payload,它的hash = payload[0]*Pn-1 + payload[1]*Pn-2 + … + payload[n-1]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
像Java中的String用的就是这个算法,Prime选择可能不一样,常用的有31, 131, 1313, 13131, 131313。其他对象都可以使用此方法,因为任何对象都可以序列化为byte。可以看到hash算法没有考虑溢出,这样计算P的乘方,很快就会溢出,但是没关系,溢出会变成负数,并不影响hashing。在有些算法中会对一个很大的素数如109+7取余,以让哈希值变得的不那么大。
另外,可以看出哈希算法是O(L)的,这里L是输入数据的长度,比如对于字符串来说就是字符串的长度,假如是一个很长很长很长的字符串,那么计算其hash可能会很久很久,因此当使用HashMap时,可能就会变得很慢。
参考资料
HashMap/HashSet
基于Hashing和Hash构建出来的用于高效查询的数据结构。
参考资料
- Data structure Hash Table
- Hashing Data Structure
- Java 8系列之重新认识HashMap
- Map - HashSet & HashMap 源码解析
- 了解 HashMap 数据结构,超详细!
ConcurrentHashMap
线程安全的哈希表,采用分段式读加锁的方式来提高并发效率。
参考资料
哈希碰撞Hash Collision
哈希算法针对不同的原始数据却产生了相同的键,这就是哈希碰撞,因为最理想的hashing是一一对应,同样的原始数据(也就是相等的两个对象)肯定会产生相同的键,这时我们认为数据是同一份(相等的),但不同的数据(也即不相等)却产生了相同的键,就需要进行特殊处理,这会增加复杂度。哈希碰撞是不可避免的,同时也是一个衡量指标,即好的哈希函数会产生较少的合理碰撞(也就是因为数据边界和算法能力导致的碰撞)。
哈希碰撞会降低效率和安全性,比如说服务器通常会把客户端的request先暂存起来,去异步处理,当有了response后,再找到其对应的request然后给其回复response。这一过程,一般会有哈希表来存储request。假如哈希函数选择的不好,比如用request当中的某一个String字段来作为request的Key的话,就有可能被恶意攻击。哈希表常规的效率是很高的,一旦有哈希碰撞就会变成链表复杂度会上升为O(n2)。而String的hash是容易产生碰撞,假如恶意客户端发现了是用String作为Key的,那么就可以用能产生哈希碰撞的String来生成不同的request,这样就会让服务器短时间内负载特别高而且宕机。这是一种基于哈希碰撞的古老的攻击方式。
所以一般服务器使用的哈希函数都是要特别设计,不能采用太普通 的哈希算法。
参考资料
滚动哈希Rolling Hash
是一种哈希算法,使用一个固定长度的窗口(通常远小于数据本身的长度)在数据中滑动,能以更高的效率计算出数据的哈希值(键)。通常会被用于检查文章的相似性(是否存在抄袭),查找重复的子串等。因为滚动哈希是在一个长的序列中以一个固定的窗口在计算,所以特别擅长在接近无限的序列中探测重复子序列,比如网络流模式探测,视频重复帧识别等等。
一个典型的Rolling hash实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
|
可以看出,字符串是”abcabcabc”,有三个重复子串,Rolling hash能清查的找到,看Rolling hash输出中的0,3和6个元素(即子串”abc”),另外两个重复子串”bca”,是1和4,以及”cab”,是2和5。
Rolling hash是O(n)的,每个子串的比较都是O(1),是相当高效的算法,是用于解决子串查找,重复子串查找的利器。
参考资料
- Introduction to Rolling Hash – Data Structures and Algorithms
- (Rabin-Karp算法)匹配字符串(滚动哈希)
- 滚动哈希(Rolling Hash)
- 滚动hash实现字符串匹配
典型问题
哈希表作为一种极基础的数据结构,提供以O(1)时间查询的能力,所以是刷题当中最为常用的辅助数据结构,没有之一。但其实HashMap/HashSet并不 真的O(1),它只是摊还分析的时间复杂度能到O(1),但真实的运行效率不可能达到O(1),一旦发生哈希碰撞就会上升到O(n2)。并且还有扩容和自动装箱autobox等隐形开销,hash函数本身也有开销一般是O(L)的,所以HashMap真实的运行效率并不高。
但哈希表是一种hashing的实现,更为重要的是体现了hashing的映射思想。所以,在有些时候虽然用到了哈希表,但不一定要用HashMap。比如像英文字母到索引的映射,以及数据范围不大的自然数到索引的映射,这本质上也是hashing,但用数组就可以了,并且这是真正的O(1)。
哈希表一般当作基础设施来使用,所以没有专门的题,关于哈希的题目一般都是滚动哈希的,并且难度都不小。
题目 | 题解 | 说明 |
---|---|---|
187. 重复的DNA序列 | 题解 | |
214. 最短回文串 | 题解 | |
2352. 相等行列对 | 题解 | |
题解 | ||
题解 | ||
题解 |