哈希表
我们先解决 LeetCode 上的 387 号问题来引入哈希表，问题描述如下：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
这里给出两种方式来解决这个问题，重点关注第二种解题思路。
方式一：
public static int firstUniqChar(String s) {
TreeMap<Character, Integer> treeMap = new TreeMap<>();
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if (treeMap.containsKey(c)) {
treeMap.put(c, treeMap.get(c) + 1);
} else {
treeMap.put(c, 1);
}
}
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if (treeMap.get(c) == 1) {
return i;
}
}
return -1;
}
方式二：
public static int firstUniqChar2(String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (freq[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
上述方式二中，int[26] 就是一个哈希表，每一个字符都和一个索引相对应 index = ch - 'a' ，因为已知索引值，所以对存储的内容进行操作，都是 O(1) 级别的。哈希表充分表现了用空间换时间的思想，达到时间和空间之间的平衡。
我们这里储存的是字符出现的频率，其实哈希表可以存储任意类型，只需要把相应的键转换成对应的索引即可，将键转换成索引的这个函数，称为哈希函数。上述问题的哈希函数为： f(ch) = ch - 'a' 。
由于我们的键是任意类型的，比如字符串、浮点数、日期等等，所以很难保证每一个键通过哈希函数转换后都对应不同的索引，有时候转换成的索引会相同，这就是哈希冲突，那么哈希函数的设计非常重要，键通过哈希函数得到的索引分布越均匀越好。
Java 中的哈希函数
代码示例如下：
public static void main(String[] args) {
Integer a = -42;
Double b = 3.1415926;
String c = "leetcode";
System.out.println(a.hashCode());
System.out.println(b.hashCode());
System.out.println(c.hashCode());
System.out.println(new Student(3, 9, "zeng", "fanda").hashCode());
System.out.println(new Student(3, 9, "zeng", "fanda").hashCode());
}
public static class Student {
private int grade;
private int cls;
private String firstName;
private String lastName;
public Student(int grade, int cls, String firstName, String lastName) {
this.grade = grade;
this.cls = cls;
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public int hashCode() {
return super.hashCode();
}
}
结果：
-42
219937201
1690245589
1967205423
42121758
Java 中的 Object 类有一个 hashCode() 方法，用于将一个对象转换成一个整型(整型可正可负)，哈希表需要设计自己的哈希函数，将整形再转换成相应的索引。
在上述代码中，我们直接打印 Student 对象的哈希值，返回的哈希值是不一样的，即使对象所有的内容完全一致。这是因为系统的哈希值实现方法是跟对象所储存的内存地址有关，不同的内存地址所得出的哈希值不一样。如果想对内容完全一致的对象得到的哈希值也完全一致，那么需要复写对应的 hashCode() 和 equals() 方法。
示例代码如下：
public static class Student {
private int grade;
private int cls;
private String firstName;
private String lastName;
public Student(int grade, int cls, String firstName, String lastName) {
this.grade = grade;
this.cls = cls;
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public int hashCode() {
// int B = 31;
// int hash = 0;
// hash = hash * B + grade;
// hash = hash * B + cls;
// // 字符串不区分大小写
// hash = hash * B + firstName.toLowerCase().hashCode();
// hash = hash * B + lastName.toLowerCase().hashCode();
// return hash;
return Objects.hash(grade, cls, firstName, lastName);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return grade == student.grade &&
cls == student.cls &&
firstName.equals(student.firstName) &&
lastName.equals(student.lastName);
}
}
重新运行上述测试代码，结果如下：
-42
219937201
1690245589
214006675
214006675
此时，得到的哈希值完全一致。复写 equals() 方法是因为当哈希值一致的时候，即产生哈希冲突时，用来判断两个对象是否是同一个对象。
哈希冲突的处理
链地址法：
Java 标准库中的哈希表的实现在 java 8 之前用的是链表，从java 8 开始，初始的时候，每一个位置还是对应一个链表，但当哈希冲突达到一定程度(平均每个位置存储的元素达到一定的数量)，每一个位置从链表转成红黑树。
按照上图分析所得，哈希表每个元素用链表的话，时间复杂度为 O(N/M)，用平衡树的话，时间复杂度为 O(log(N/M))。那么我们应该怎样做才能保证哈希表的时间复杂度为 O(1) 级别呢？
答：动态的扩展地址 M 的数量，让所有的元素都能均匀地分布在每个位置。
这里的复杂度是平均复杂度，即均摊复杂度为 O(1) 。
哈希表代码
public class HashTable<K, V> {
// 合适的素数数组
private final int[] capacity
= {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
// 每个位置平均存储的元素达到的数量上界，达到即扩容
private static final int UPPER_TOL = 10;
// 每个位置平均存储的元素达到的数量下界，达到即缩容
private static final int LOWER_TOL = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
// 合适的素数
private int M;
private int size;
public HashTable() {
// 默认取第一个素数
this.M = capacity[capacityIndex];
// 创建数组
hashtable = new TreeMap[M];
// 创建数组每个位置的 TreeMap
for (int i = 0; i < M; i++) {
hashtable[i] = new TreeMap<>();
}
}
/**
* 哈希函数，转换为对应的索引
*/
private int hash(K key) {
// & 0x7fffffff 是为了去掉符号位，变为正数
return (key.hashCode() & 0x7fffffff) % M;
}
public int getSize() {
return size;
}
/**
* 添加
*/
public void add(K key, V value) {
TreeMap<K, V> treeMap = hashtable[hash(key)];
if (treeMap.containsKey(key)) {
treeMap.put(key, value);
} else {
treeMap.put(key, value);
// 维护数量
size++;
// 这里将除法运算转为乘法运算，避免出现类型转换等情况
if (size >= UPPER_TOL * M && capacityIndex + 1 < capacity.length) {
capacityIndex++;
resize(capacity[capacityIndex]);
}
}
}
private void resize(int newM) {
TreeMap<K, V>[] newHashTable = new TreeMap[newM];
for (int i = 0; i < newM; i++) {
newHashTable[i] = new TreeMap<>();
}
// 注意这里，此时hash函数用到的M ，应该是newM
this.M = newM;
for (TreeMap<K, V> treeMap : hashtable) {
for (K k : treeMap.keySet()) {
newHashTable[hash(k)].put(k, treeMap.get(k));
}
}
this.hashtable = newHashTable;
}
/**
* 删除
*/
public V remove(K key) {
TreeMap<K, V> treeMap = hashtable[hash(key)];
V ret = null;
if (treeMap.containsKey(key)) {
ret = treeMap.remove(key);
// 维护数量
size--;
if (size < LOWER_TOL * M && capacityIndex - 1 >= 0) {
capacityIndex--;
resize(capacity[capacityIndex]);
}
}
return ret;
}
/**
* 修改
*/
public void set(K key, V value) {
TreeMap<K, V> treeMap = hashtable[hash(key)];
if (!treeMap.containsKey(key)) {
throw new IllegalArgumentException(key + " does not exist");
} else {
treeMap.put(key, value);
}
}
public boolean contains(K key) {
return hashtable[hash(key)].containsKey(key);
}
public V get(K key) {
return hashtable[hash(key)].get(key);
}
}
总结
我们这里实现的哈希表还有 bug ，因为树存储的元素是需要有可比较性的，而我们的哈希表没设计成要传能够比较的元素。其实系统标准库中的哈希表默认是用链表的，哈希冲突达到一定数量后，如果元素是不可比较的，也无法动态转为红黑树，如果是可比较的，才会做转换处理。
