数据结构：哈希表

心已赠人 2023-01-17 08:27 358阅读 0赞

### 目录 ###

*  第一章 哈希表介绍
 *  第二章 哈希冲突
 *  第三章 哈希函数
 *  第四章 哈希表实现

--------------------

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 哈希表介绍 #

设计一个写字楼通讯录，存放该写字楼所有公司的通讯信息，座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value，要求添加、删除、搜索的时间复杂度要求是 O(1)，实现代码如下：

![bec962ac984e81ab30c8705425e0f058.png][]

我们发现上述代码可以实现要求，但是空间复杂度极大，空间利用率极低，非常浪费内存空间，其实数组 companies 就是一个哈希表。

哈希表（Hash Table，也叫散列表），是根据关键码值（Key Value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 **哈希函数（散列函数）** ，存放记录的数组叫做 **哈希表（散列表）** 。

![a76c1d71d39d45777d5c4d6644a625ec.png][]

# 第二章 哈希冲突 #

哈希冲突（Hash Collision，也叫哈希碰撞），简单的来说就是：2 个不同的 key，经过哈希函数计算出相同的结果。

![b697bc2e90861125e4bd1b5804ca55ab.png][]

解决哈希冲突有很多种方法，我们这里重点介绍链地址法（Separate Chaining），简单的来说就是：通过链表将同一index元素串起来。

![dc28ec58e26ab0ca9938d18b8fbe0d23.png][]

# 第三章 哈希函数 #

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希表中哈希函数的实现步骤，大概如下：

*  先生成 key 的哈希值（必须是整数）。
 *  再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值。

![9d6e7fd9422b14125d7b301f5b96d8a4.png][]

为了提高效率，可以使用 & 位运算取代 % 运算，但是这是有前提的，那就是必须将数组的长度设计为 2 的幂（2n）。

![50f7f10dea46d88bd20869b3a4b25579.png][]

良好的哈希函数，可以让哈希值更加均匀分布，减少哈希冲突次数，提升哈希表的性能。

那么问题又来了，对于 key 来说，可能是不同的数据类型，那如何计算他的哈希值呢？

key 的常见种类可能有：整数、浮点数、字符串、自定义对象。不同种类的 key，哈希值的生成方式不一样，但目标是一致的，尽量让每个 key 的哈希值是唯一的，尽量让 key 的所有信息参与运算，并且最终生成的哈希值必须是一个整数。

**Integer整数：** 整数值当做哈希值，比如 10 的哈希值就是 10

![165670e3e2d635a618a1b69ba22c53ed.png][]

**Float浮点数：** 将存储的二进制格式转为整数值

![ae5a9a72e4bd947367dc45953933b226.png][]

**Long整数、Double浮点数：**

![066285ac8bf7c72841c5d2d5a8afac43.png][]

这个 >>> 和 ^ 的作用是什么？

由于Long和Double的底层二进制位数远远超过了Integer的32位，为了满足尽量让 key 的所有信息参与运算，所以通过 >>> 右移，让当前值的高32位和低32位进行运算，混合计算出32位的整数哈希值，最终计算出来的数值高32无意义，舍去即可。这里给出一个案例：

![2171868b8991cbbb9b44bb44547bcf9e.png][]

**字符串：**

我们首先来思考一个问题，整数 5489 是如何计算出来的？

5489 = 5 ∗ 103 \+ 4 ∗ 102 \+ 8 ∗ 101 \+ 9 ∗ 100

而我们的字符串是由若干个字符组成的，比如字符串 jack，由 j、a、c、k 四个字符组成，字符的本质就是一个整数。

因此，jack 的哈希值可以表示为 j ∗ n3 \+ a ∗ n2 \+ c ∗ n1 \+ k ∗ n0，等价于 `[ ( j ∗ n + a ) ∗ n + c ] ∗ n + k` 。

在JDK中，乘数 n 为 31，为什么用 31？

由于 31 不仅仅是符合2n – 1，它还是个奇素数（既是奇数，又是素数，也就是质数），素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突，有那么多素数，那为啥是31呢，是经过观测分布结果后的选择，并且JVM会将 `31 * i` 优化成 `(i << 5) – i`。

![2e4ef4fea8d0b2941f71d9f13bfc4c19.png][]

**自定义对象：**

自定义对象需要实现 equals 和 hashCode 方法，以下示例代码的 equals 和 hashCode 方法由 idea 自动生成。

> 注意：这里实现 equals 方法和生成 hashCode 并没有直接联系，仅仅是为了后边写代码方便，也就一块生成了。

![344276a19b5c73b4db4d0b812bca579d.png][]

这里给出 `Objects.hash(...)` 的底层实现：

![f045fc6fb5ae3129a4df7b208102a27a.png][]

![d90ae6c463394fc341176df7cbb623f3.png][]

# 第四章 哈希表实现 #

【实现代码】

public class HashTable<Key, Value> { 
        private int M;                              //哈希表的大小
        private int N;                              //键值对的对数
        private SymbolTable<Key, Value>[] table;    //存放链表对象的数组，这里采用无序符号表，也可以用红黑树
    
        public HashTable(int M) { 
            this.M = M;
            table = new SymbolTable[M];
            for (int i = 0; i < M; i++) { 
                table[i] = new SymbolTable<>();
            }
        }
    
        //获取哈希表键值个数
        public int size() { 
            return N;
        }
    
        //判断哈希表是否为空
        public boolean isEmpty() { 
            return N == 0;
        }
    
        //获取指定key哈希值
        private int hash(Key key) { 
            return key.hashCode() & (table.length - 1);
        }
    
        //向哈希表中添加键值
        public void put(Key key, Value value) { 
            table[hash(key)].put(key, value);
            N++;
        }
    
        //删除哈希表中的key
        public void delete(Key key) { 
            table[hash(key)].delete(key);
            N--;
        }
    
        //获取key对应的value
        public Value get(Key key) { 
            return table[hash(key)].get(key);
        }
    
        //获取哈希表中所有key的集合
        public Set<Key> keySet() { 
            Set<Key> keySet = new HashSet<>();
            for (SymbolTable<Key, Value> keyValueSymbolTable : table) { 
                keySet.addAll(keyValueSymbolTable.keySet());
            }
            return keySet;
        }
    
        //获取哈希表中所有value的集合
        public Set<Value> valueSet() { 
            Set<Value> valueSet = new HashSet<>();
            for (SymbolTable<Key, Value> keyValueSymbolTable : table) { 
                valueSet.addAll(keyValueSymbolTable.valueSet());
            }
            return valueSet;
        }
    }

【测试代码】

public class HashTableTest { 
        public static void main(String[] args) { 
            HashTable<Integer, String> hashTable = new HashTable<>(16);
    
            hashTable.put(1, "刘备");
            hashTable.put(2, "张飞");
            hashTable.put(3, "关羽");
            hashTable.put(4, "赵云");
            hashTable.put(5, "曹操");
            hashTable.put(6, "吕布");
    
            System.out.println(hashTable.size());
            System.out.println(hashTable.isEmpty());
            System.out.println(hashTable.keySet());
            System.out.println(hashTable.valueSet());
            for (Integer key : hashTable.keySet()) { 
                System.out.println(key + "：" + hashTable.get(key));
            }
            for (Integer key : hashTable.keySet()) { 
                hashTable.delete(key);
            }
            System.out.println(hashTable.size());
            System.out.println(hashTable.isEmpty());
            System.out.println(hashTable.keySet());
            System.out.println(hashTable.valueSet());
        }
    }

【运行效果】

6
    false
    [1, 2, 3, 4, 5, 6]
    [关羽, 张飞, 吕布, 刘备, 曹操, 赵云]
    1：刘备
    2：张飞
    3：关羽
    4：赵云
    5：曹操
    6：吕布
    0
    true
    []
    []

[bec962ac984e81ab30c8705425e0f058.png]: /images/20221021/f80c5bb9d44f419fa1c1f34b902eb7a0.png
[a76c1d71d39d45777d5c4d6644a625ec.png]: /images/20221021/8e48f0fe2c39435e9048a2378586a92f.png
[b697bc2e90861125e4bd1b5804ca55ab.png]: /images/20221021/31553100d09d4c9dba050b987eb6cb1a.png
[dc28ec58e26ab0ca9938d18b8fbe0d23.png]: /images/20221021/777fce735be74128aae414d463e5ee69.png
[9d6e7fd9422b14125d7b301f5b96d8a4.png]: /images/20221021/8e73c404a6f543608542ee9f1632cdf9.png
[50f7f10dea46d88bd20869b3a4b25579.png]: /images/20221021/0070debac5ed4593b92ff1912ff20010.png
[165670e3e2d635a618a1b69ba22c53ed.png]: /images/20221021/b45bfd7156054a9897f9b3e9d73fa455.png
[ae5a9a72e4bd947367dc45953933b226.png]: /images/20221021/82f97c4d29bb4cb5b31437e25eecfc77.png
[066285ac8bf7c72841c5d2d5a8afac43.png]: /images/20221021/73e15b186beb4b5b91e9d3f2f10032a0.png
[2171868b8991cbbb9b44bb44547bcf9e.png]: /images/20221021/e8c88570f15147dbb63263643237f6cb.png
[2e4ef4fea8d0b2941f71d9f13bfc4c19.png]: /images/20221021/2a15dc7c171545ccba8655aaec10949a.png
[344276a19b5c73b4db4d0b812bca579d.png]: /images/20221021/50882bf304304820b0c78671bb66c3e2.png
[f045fc6fb5ae3129a4df7b208102a27a.png]: /images/20221021/e96adcba01e74bd29f9e871e854cb5e2.png
[d90ae6c463394fc341176df7cbb623f3.png]: /images/20221021/13afe700353f414f98eb0143262a45d3.png