稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

Hashing Hash and HashMap

哈希表(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
// Other possible primes are: 31, 131, 1313, 13131, 131313
public static final int P = 33;
public static int hash(String s) {
    return hashBytes(s.toCharArray());
}

/*
 * Polynomial multiplication of prime:
 * hash = c[0]*P^(n-1) + c[1]*P^(n-2) + ... + s[n-1]
 */
public static int hashBytes(char[] chars) {
    int hash = 0;
    for (char ch : chars) {
        hash = P * hash + ch;
    }

    return hash;
}

像Java中的String用的就是这个算法,Prime选择可能不一样,常用的有31, 131, 1313, 13131, 131313。其他对象都可以使用此方法,因为任何对象都可以序列化为byte。可以看到hash算法没有考虑溢出,这样计算P的乘方,很快就会溢出,但是没关系,溢出会变成负数,并不影响hashing。在有些算法中会对一个很大的素数如109+7取余,以让哈希值变得的不那么大。

另外,可以看出哈希算法是O(L)的,这里L是输入数据的长度,比如对于字符串来说就是字符串的长度,假如是一个很长很长很长的字符串,那么计算其hash可能会很久很久,因此当使用HashMap时,可能就会变得很慢。

参考资料

HashMap/HashSet

基于Hashing和Hash构建出来的用于高效查询的数据结构。

参考资料

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
public static ArrayList<Integer> rollingHash(String payload, int window, int p, int mod) {
        final int n = payload.length();
        ArrayList<Integer> hashValues = new ArrayList<>(n - window + 1);
        int power = 1;
        for (int i = 0; i < window - 1; i++) {
            power *= p;
            power %= mod;
        }

        int hash = 0;
        for (int i = 0; i < window; i++) {
            hash = (hash * p + payload.charAt(i)) % mod;
        }
        hashValues.add(hash);

        for (int i = 1; i < n - window + 1; i++) {
            hash = (hash - power * payload.charAt(i - 1)) % mod;
            hash = (hash * p + payload.charAt(i + window - 1)) % mod;
            hashValues.add(hash);
        }

        return hashValues;
    }

    public static void main(String[] args) {
        String payload = "abcabcabc";
        int window = 3;
        ArrayList<Integer> hashes = rollingHash(payload, window, 31, MOD);
        System.out.println("Rolling hash of " + payload + ", window size " + window);
        IntStream.range(0, hashes.size())
                .mapToObj(i -> i + "->" + payload.substring(i, i + window) + " whose hash is " + hashes.get(i))
                .forEach(System.out::println);
    }
    // outputs
    //Rolling hash of abcabcabc, window size 3
    //0->abc whose hash is 96354
    //1->bca whose hash is 97344
    //2->cab whose hash is 98244
    //3->abc whose hash is 96354
    //4->bca whose hash is 97344
    //5->cab whose hash is 98244
    //6->abc whose hash is 96354

可以看出,字符串是”abcabcabc”,有三个重复子串,Rolling hash能清查的找到,看Rolling hash输出中的0,3和6个元素(即子串”abc”),另外两个重复子串”bca”,是1和4,以及”cab”,是2和5。

Rolling hash是O(n)的,每个子串的比较都是O(1),是相当高效的算法,是用于解决子串查找,重复子串查找的利器。

参考资料

典型问题

哈希表作为一种极基础的数据结构,提供以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. 最短回文串 题解
题解

参考资料

Comments