程序员必读书单：https://github.com/silently9527/ProgrammerBooks
微信公众号：贝塔学 Java
前言
前几篇我们一起学习了基于数组、链表、二叉树、红黑树来实现 Map 的操作，本篇我们将会一起来学习基于散列表来实现 Map，这种方式对应着 java 里面的 HashMap，这也是使用最多的一种方式
散列表实现 Map 主要分为了两个步骤:
基于散列函数将被查找键转换为数组的下标
处理散列值冲突的情况，有两种方式来处理冲突：拉链式和线性探测
散列函数
实现散列表的第一步就是需要考虑如何把一个键转换为数组的下标，这时候就需要使用到散列函数，先把键值转换成一个整数然后在使用除留余数法计算出数组的下标。每种类型的键我们都需要一个不同的散列函数。
在 java 中对于常用的数据类型已经实现了 hashCode，我们只需要根据 hashCode 的值使用除留余数法即可转换成数组的下标
java 中的约定：如果两个对象的 equals 相等，那么 hashCode 一定相同；如果 hashCode 相同，equals 不一定相同。对于自定义类型的键我们通常需要自定义实现 hashCode 和 equals；默认的 hashCode 返回的是对象的内存地址，这种散列值不会太好。
下面我来看看 Java 中常用类型的 hashCode 计算方式
Integer
由于 hashCode 需要返回的值就是一个 int 值，所以 Integer 的 hashCode 实现很简单，直接返回当前的 value 值
@Overridepublic int hashCode() { return Integer.hashCode(value);}public static int hashCode(int value) { return value;}
复制代码
Long
Java 中 Long 类型的 hashCode 计算是先把值无符号右移 32 位，之后再与值相异或，保证每一位都用用到，最后强制转换成 int 值
@Overridepublic int hashCode() { return Long.hashCode(value);}
public static int hashCode(long value) { return (int)(value ^ (value >>> 32));}
复制代码
Double、Float
浮点类型的键 java 中 hashCode 的实现是将键表示为二进制
public static int hashCode(float value) { return floatToIntBits(value);}public static int floatToIntBits(float value) { int result = floatToRawIntBits(value); // Check for NaN based on values of bit fields, maximum // exponent and nonzero significand. if ( ((result & FloatConsts.EXP_BIT_MASK) == FloatConsts.EXP_BIT_MASK) && (result & FloatConsts.SIGNIF_BIT_MASK) != 0) result = 0x7fc00000; return result;}
复制代码
String
java 中每个 char 都可以表示成一个 int 值，所以字符串转换成一个 int 值
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value;
for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h;}
复制代码
软缓存
如果计算一个散列值比较耗时，那么我可以这个计算好的值缓存起来，即使用一个变量把这个值保存起来，在下一次调用时直接返回。Java 中的 String 就是采用的这种方式。
拉链式的散列表
散列函数能够将键值转换成数组的下标；第二步就是需要处理碰撞冲突，也就是需要处理遇到了两个散列值相同的对象应该如何存储。有一种方式是数组中的每一个元素都指向一个链表用来存放散列值相同的对象，这种方式被称为拉链法
拉链法可以使用原始的链表保存键，也可以采用我们之前实现的红黑树来表示，在 java8 中采用的这两种方式的混合，在节点数超过了 8 之后变为红黑树。
这里我们就采用简单的链表来实现拉链式散列表，数据结构使用在前几篇中已经实现的LinkedMap，可以参考前面的文章《基于数组或链表实现Map》。
public class SeparateChainingHashMap<K, V> implements Map<K, V> {
private int size; private LinkedMap<K, V>[] table;
public SeparateChainingHashMap(int capacity) { this.table = (LinkedMap<K, V>[]) new LinkedMap[capacity]; for (int i = 0; i < capacity; i++) { this.table[i] = new LinkedMap<>(); } }
@Override public void put(K key, V value) { this.table[hash(key)].put(key, value); size++; }
private int hash(K key) { return (key.hashCode() & 0x7fffffff) % table.length; }
@Override public V get(K key) { return this.table[hash(key)].get(key); }
@Override public void delete(K key) { this.table[hash(key)].delete(key); size--; }
@Override public int size() { return size; }
}
复制代码
这的 hash 函数使用 key 的 hashCode 与上 0x7fffffff 得到一个非负的整数，然后再使用除留余数法计算出数组的下标。其中 0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是 1，也就是说，这是最大的整型数 int（因为第一位是符号位，0 表示他是正数）,可以使用 Integer.MAX_VALUE 代替
散列表的主要目的在于把键值均匀的分布到数组中，所以散列表是无序的，如果你需要的 Map 需要支持取出最大值，最小值，那么散列表都不适合。
这里我们实现的拉链式散列表的数组大小是固定的，但是通常在随着数据量的增大，越短的数组出现碰撞的几率会增大，所以需要数组支持动态的扩容，扩容之后需要把原来的值重新插入到扩容之后的数组中。数组的扩容可以参考之前的文章《老哥是时候来复习下数据结构与算法了》
线性探测式散列表
实现散列表的另一种方式就是用大小为 M 来保存 N 个键值，其中 M>N；解决碰撞冲突就需要利用数组中的空位；这种方式中最简单的实现就是线性探测。
线性探测的主要思路：当插入一个键，发生碰撞冲突之后直接把索引加一来检查下一个位置，这时候会出现三种情况:
下一个位置和待插入的键相等，那么值就修改值
下一个位置和待插入的键不相等，那么索引加一继续查找
如果下一个位置还是一个空位，那么直接把待插入对象放入到这个空位
初始化
线性探测式散列表使用两个数组来存放 keys 和 values，capacity表示初始化数组的大小
private int size;private int capacity;private K[] keys;private V[] values;
public LinearProbingHashMap(int capacity) { this.capacity = capacity; this.keys = (K[]) new Object[capacity]; this.values = (V[]) new Object[capacity];}
复制代码
插入
当插入键的位置超过了数组的大小，就需要回到数组的开始位置继续查找，直到找到一个位置为 null 的才结束；index = (index + 1) % capacity
当数组已存放的容量超过了数组总容量的一半，就需要扩容到原来的 2 倍
@Overridepublic void put(K key, V value) { if (Objects.isNull(key)) { throw new IllegalArgumentException("Key can not null"); } if (this.size > this.capacity / 2) { resize(2 * this.capacity); } int index; for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) { if (this.keys[index].equals(key)) { this.values[index] = value; return; } } this.keys[index] = key; this.values[index] = value; size++;}
复制代码
动态调整数组的大小
我们可以参考之前在文章《老哥是时候来复习下数据结构与算法了》中实现的动态调整数据的大小；在线性探测中需要把原来的数据重新插入到扩容之后的数据，因为数组的大小变了需要重新计算索引的位置。
private void resize(int cap) { LinearProbingHashMap<K, V> linearProbingHashMap = new LinearProbingHashMap<>(cap); for (int i = 0; i < capacity; i++) { linearProbingHashMap.put(keys[i], values[i]); } this.keys = linearProbingHashMap.keys; this.values = linearProbingHashMap.values; this.capacity = linearProbingHashMap.capacity;}
复制代码
查询
线性探测散列表中实现查询的思路：根据待查询 key 的 hash 函数计算出索引的位置，然后开始判断当前位置上的 key 是否和待查询 key 相等，如果相等那么就直接返回 value，如果不相等那么就继续查找下一个索引直到遇到某个位置是 null 才结束，表示查询的 key 不存在；
@Overridepublic V get(K key) { if (Objects.isNull(key)) { throw new IllegalArgumentException("Key can not null"); } int index; for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) { if (this.keys[index].equals(key)) { return this.values[index]; } } return null;}
复制代码
删除元素
线性探测式的删除稍微麻烦一些，首先需要查找出待删除的元素位置，删除元素之后需要把当前索引之后的连续位置上的元素重新插入；因为是否有空位对于线性探测式散列表的查找至关重要；例如：5->7->9，删除了 7 之后，如果不重新插入 7 的位置就是空位，那么 get 方法将无法查询到 9 这个元素；
每次删除之后都需要检测一次数组中实际元素的个数，如果与数组的容量相差较大，就可以进行缩容操作；
@Overridepublic void delete(K key) { if (Objects.isNull(key)) { throw new IllegalArgumentException("Key can not null"); } int index; for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) { if (this.keys[index].equals(key)) { this.keys[index] = null; this.values[index] = null; break; } }
for (index = (index + 1) % capacity; this.keys[index] != null; index = (index + 1) % capacity) { this.size--; this.put(this.keys[index], this.values[index]); this.keys[index] = null; this.values[index] = null; } this.size--; if (size > 0 && size < capacity / 4) { resize(capacity / 2); }
}
复制代码
文中所有源码已放入到了 github 仓库:https://github.com/silently9527/JavaCore
最后（点关注，不迷路）
文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。
最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏
评论