数据结构：哈希表
目录
- 第一章 哈希表介绍
- 第二章 哈希冲突
- 第三章 哈希函数
- 第四章 哈希表实现
项目地址：https://gitee.com/caochenlei/data-structures
第一章 哈希表介绍
设计一个写字楼通讯录，存放该写字楼所有公司的通讯信息，座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value，要求添加、删除、搜索的时间复杂度要求是 O(1)，实现代码如下：
我们发现上述代码可以实现要求，但是空间复杂度极大，空间利用率极低，非常浪费内存空间，其实数组 companies 就是一个哈希表。
哈希表（Hash Table，也叫散列表），是根据关键码值（Key Value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 哈希函数（散列函数） ，存放记录的数组叫做 哈希表（散列表） 。
第二章 哈希冲突
哈希冲突（Hash Collision，也叫哈希碰撞），简单的来说就是：2 个不同的 key，经过哈希函数计算出相同的结果。
解决哈希冲突有很多种方法，我们这里重点介绍链地址法（Separate Chaining），简单的来说就是：通过链表将同一index元素串起来。
第三章 哈希函数
哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希表中哈希函数的实现步骤，大概如下：
- 先生成 key 的哈希值（必须是整数）。
- 再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值。
为了提高效率，可以使用 & 位运算取代 % 运算，但是这是有前提的，那就是必须将数组的长度设计为 2 的幂（2n）。
良好的哈希函数，可以让哈希值更加均匀分布，减少哈希冲突次数，提升哈希表的性能。
那么问题又来了，对于 key 来说，可能是不同的数据类型，那如何计算他的哈希值呢？
key 的常见种类可能有：整数、浮点数、字符串、自定义对象。不同种类的 key，哈希值的生成方式不一样，但目标是一致的，尽量让每个 key 的哈希值是唯一的，尽量让 key 的所有信息参与运算，并且最终生成的哈希值必须是一个整数。
Integer整数： 整数值当做哈希值，比如 10 的哈希值就是 10
Float浮点数： 将存储的二进制格式转为整数值
Long整数、Double浮点数：
这个 >>> 和 ^ 的作用是什么？
由于Long和Double的底层二进制位数远远超过了Integer的32位，为了满足尽量让 key 的所有信息参与运算，所以通过 >>> 右移，让当前值的高32位和低32位进行运算，混合计算出32位的整数哈希值，最终计算出来的数值高32无意义，舍去即可。这里给出一个案例：
字符串：
我们首先来思考一个问题，整数 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。
自定义对象：
自定义对象需要实现 equals 和 hashCode 方法，以下示例代码的 equals 和 hashCode 方法由 idea 自动生成。
注意：这里实现 equals 方法和生成 hashCode 并没有直接联系，仅仅是为了后边写代码方便，也就一块生成了。
这里给出 Objects.hash(...) 的底层实现：
第四章 哈希表实现
【实现代码】
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++;}//删除哈希表中的keypublic void delete(Key key) {table[hash(key)].delete(key);N--;}//获取key对应的valuepublic 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());}}
【运行效果】
6false[1, 2, 3, 4, 5, 6][关羽, 张飞, 吕布, 刘备, 曹操, 赵云]1：刘备2：张飞3：关羽4：赵云5：曹操6：吕布0true[][]
系统管理员
梦里梦外;
忘是亡心i
￡神魔★判官ぃ
淩亂°似流年
还没有评论，来说两句吧...