哈希表(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]*P^n-1 + payload[1]*P^n-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。在有些算法中会对一个很大的素数如10⁹+7取余，以让哈希值变得的不那么大。

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

参考资料

• 什么是哈希算法？
• 加密哈希算法的实现原理
• 图解一致性哈希算法
• 经典Hash函数的实现
• Hash 算法实现
• Hash算法详细介绍与实现(一)
• Hash 算法详细介绍与实现 (二)

HashMap/HashSet

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

参考资料

• Data structure Hash Table
• Hashing Data Structure
• Java 8系列之重新认识HashMap
• Map - HashSet & HashMap 源码解析
• 了解 HashMap 数据结构，超详细！

ConcurrentHashMap

线程安全的哈希表，采用分段式读加锁的方式来提高并发效率。

参考资料

• ConcurrentHashMap源码分析(1.8)
• ConcurrentHashMap 源码分析
• ConcurrentHashMap源码分析

哈希碰撞Hash Collision

哈希算法针对不同的原始数据却产生了相同的键，这就是哈希碰撞，因为最理想的hashing是一一对应，同样的原始数据（也就是相等的两个对象）肯定会产生相同的键，这时我们认为数据是同一份（相等的），但不同的数据（也即不相等）却产生了相同的键，就需要进行特殊处理，这会增加复杂度。哈希碰撞是不可避免的，同时也是一个衡量指标，即好的哈希函数会产生较少的合理碰撞（也就是因为数据边界和算法能力导致的碰撞）。

哈希碰撞会降低效率和安全性，比如说服务器通常会把客户端的request先暂存起来，去异步处理，当有了response后，再找到其对应的request然后给其回复response。这一过程，一般会有哈希表来存储request。假如哈希函数选择的不好，比如用request当中的某一个String字段来作为request的Key的话，就有可能被恶意攻击。哈希表常规的效率是很高的，一旦有哈希碰撞就会变成链表复杂度会上升为O(n²)。而String的hash是容易产生碰撞，假如恶意客户端发现了是用String作为Key的，那么就可以用能产生哈希碰撞的String来生成不同的request，这样就会让服务器短时间内负载特别高而且宕机。这是一种基于哈希碰撞的古老的攻击方式。

所以一般服务器使用的哈希函数都是要特别设计，不能采用太普通 的哈希算法。

参考资料

• 哈希碰撞与生日攻击
• HASH碰撞问题一直没真正搞懂？这下不用慌了
• 哈希理解、哈希碰撞（hash冲突）及处理
• Hash Collision: Weak and Strong Resistance

滚动哈希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)，是相当高效的算法，是用于解决子串查找，重复子串查找的利器。

参考资料

• Introduction to Rolling Hash – Data Structures and Algorithms
• (Rabin-Karp算法)匹配字符串（滚动哈希）
• 滚动哈希（Rolling Hash）
• 滚动hash实现字符串匹配

典型问题

哈希表作为一种极基础的数据结构，提供以O(1)时间查询的能力，所以是刷题当中最为常用的辅助数据结构，没有之一。但其实HashMap/HashSet并不 真的O(1)，它只是摊还分析的时间复杂度能到O(1)，但真实的运行效率不可能达到O(1)，一旦发生哈希碰撞就会上升到O(n²)。并且还有扩容和自动装箱autobox等隐形开销，hash函数本身也有开销一般是O(L)的，所以HashMap真实的运行效率并不高。

但哈希表是一种hashing的实现，更为重要的是体现了hashing的映射思想。所以，在有些时候虽然用到了哈希表，但不一定要用HashMap。比如像英文字母到索引的映射，以及数据范围不大的自然数到索引的映射，这本质上也是hashing，但用数组就可以了，并且这是真正的O(1)。

哈希表一般当作基础设施来使用，所以没有专门的题，关于哈希的题目一般都是滚动哈希的，并且难度都不小。

参考资料

• 哈希算法