数据结构与算法——（Hash）哈希表与哈希算法

1.哈希表

给每份数据分配一个编号，放入表格(数组)
建立编号与表格索引的关系，将来就可以通过编号快速查找数据

1. 理想情况编号当唯一，表格能容纳所有数据
2. 现实是不能说为了容纳所有数据造一个超大表格，编号也有可能重复

解决方案

1. 有限长度的数组，以拉链方式存储数据
2. 允许编号适当重复，通过数据自身来进行区分

代码（不包含扩容）

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点，初始容量为16private int size;//哈希表中元素个数，初始值为0//获取值public V get(int hash, K key) {/*** 求模运算替换为位运算* 前提：*      1.数组长度是2的n次方*      2.hash % table.length 等价于 hash & (table.length - 1)*///1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.获取链表的头节点Entry<K, V> entry = table[index];while (entry != null) {if (key.compareTo(entry.key) == 0) {return entry.value;}entry = entry.next;}return null;}//添加，key存在就修改，否则添加public void put(int hash, K key, V value) {//1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.判断链表中是否有这个key，有则替换Entry<K, V> entry = table[index];Entry<K, V> parent = null;while (entry != null) {parent = entry;if (key.compareTo(entry.key) == 0) {entry.value = value;return;}entry = entry.next;}//3.需要新增Entry<K, V> add = new Entry<>(hash, key, value);if (parent == null) {table[index] = add;} else {parent.next = add;}//4.修改长度size++;}//删除public V remove(int hash, K key) {int index = hash & (table.length - 1);Entry<K, V> entry = table[index];if (entry == null) {return null;}Entry<K, V> prev = null;//上一节点while (entry != null) {if (key.compareTo(entry.key) == 0) {if (prev == null) {table[index] = entry.next;} else {prev.next = entry.next;}size--;return entry.value;}prev = entry;entry = entry.next;}return null;}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

扩容

负载因子：$loadfactor(\alpha )=\frac{n}{m}$ ，n表示hash表中元素的个数，m表示hash表数组的长度，在Java中的取值是 0.75

扩容代码

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点，初始容量为16private int size;//哈希表中元素个数，初始值为0private float loadFactor = 0.75f;//负载因子，在Java中是 0.75private int threshold = (int) (loadFactor * table.length);//预值，也就是当数组长度达到 12的时候进行扩容//扩容方法private void resize() {//1.扩容一倍Entry<K, V>[] newTable = new Entry[table.length << 1];for (int i = 0; i < table.length; i++) {//2.获取每个链表的头节点，把链表进行拆分 a 和 bEntry<K, V> p = table[i];if (p != null) {/*** 拆分链表规律* hash & (table.length - 1) == 0 分为一组* hash & (table.length - 1) != 0 分为一组** 例如：*      0->8->16->24->32->40->48->56->64->72->80->null*      p**      a:0->16->32->48->64->80->null**      b:8->24->40->56->72->null*/Entry<K, V> aHead = null;Entry<K, V> bHead = null;Entry<K, V> a = null;Entry<K, V> b = null;while (p != null) {if ((p.hash & (table.length)) == 0) {//分配给aif (a != null) {a.next = p;} else {aHead = p;}a = p;} else {//分配给bif (b != null) {b.next = p;} else {bHead = p;}b = p;}p = p.next;}if (a != null) {a.next = null;table[i] = aHead;//放在原来的数组位置}if (b != null) {b.next = null;table[i + table.length] = bHead;}}}table = newTable;threshold = (int) (loadFactor * table.length);//预值}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

问题总结
前提：数组长度是 2 的 n 次方

1. 为什么计算索引位置用式子：hash & (数组长度-1)
   - hash & (数组长度-1) 等价于 hash % 数组长度
2. 为什么旧链表会拆分成两条，一条 hash & 旧数组长度 == 0，另一条 != 0
   - 旧数组长度换算成二进制后，其中的 1 就是我们要检查的倒数第几位
   - hash & 8，8的二进制是 1000

2.哈希算法

1.概述

哈希算法（Hash Algorithm）是一种将任意长度的输入（称为预映射或消息）转换成固定长度输出（称为哈希值或散列值）的函数。哈希值通常是一个较短的、固定长度的数字串，它几乎唯一地对应于原始数据。

2.特点

1. 确定性：相同的输入总是产生相同的哈希值。
2. 不可逆性：从哈希值很难反推出原始输入数据。
3. 雪崩效应：输入数据的微小变化会导致哈希值的显著不同。
4. 抗碰撞性：找到两个不同的输入产生相同哈希值的难度非常高。

3.Object.hashCode()

• Object 的 hashCode 方法默认是生成随机数作为 hash 值（会缓存在对象头当中）
• 缺点是包含相同值的不同对象，他们的 hashCode 不一样，不能够用 hash 值来反映对象的值特征，因此诸多子类都会重写 hashCode 方法

结论：同一对象的hashCode相同

4.String.hashCode()

结论：相同值不同对象的hashCode相同
String对象的hashCode怎么实现的呢？？？

public class HashCode {public static void main(String[] args) {String s1 = "abc";int hash = 0;for (int i = 0; i < s1.length(); i++) {int code = s1.charAt(i);hash = 10 * hash + code;//对于 abc : a * 100 + b * 10 + c}System.out.println(hash);//10779}
}

如果把倍数改成31（一个质数）

完整代码

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点，初始容量为16private int size;//哈希表中元素个数，初始值为0private float loadFactor = 0.75f;//负载因子，在Java中是 0.75private int threshold = (int) (loadFactor * table.length);//预值，也就是当数组长度达到 12的时候进行扩容//获取值private V get(int hash, K key) {/*** 求模运算替换为位运算* 前提：*      1.数组长度是2的n次方*      2.hash % table.length 等价于 hash & (table.length - 1)*///1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.获取链表的头节点Entry<K, V> entry = table[index];while (entry != null) {if (key.compareTo(entry.key) == 0) {return entry.value;}entry = entry.next;}return null;}//获取值public V get(K key) {return get(hash(key), key);}//添加，key存在就修改，否则添加private void put(int hash, K key, V value) {//1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.判断链表中是否有这个key，有则替换Entry<K, V> entry = table[index];Entry<K, V> parent = null;while (entry != null) {parent = entry;if (key.compareTo(entry.key) == 0) {entry.value = value;return;}entry = entry.next;}//3.需要新增Entry<K, V> add = new Entry<>(hash, key, value);if (parent == null) {table[index] = add;} else {parent.next = add;}//4.修改长度size++;//5.当数据长度达到预值时进行扩容if (size > threshold) {resize();}}//添加，key存在就修改，否则添加public void put(K key, V value) {put(hash(key), key, value);}//删除private V remove(int hash, K key) {int index = hash & (table.length - 1);Entry<K, V> entry = table[index];if (entry == null) {return null;}Entry<K, V> prev = null;//上一节点while (entry != null) {if (key.compareTo(entry.key) == 0) {if (prev == null) {table[index] = entry.next;} else {prev.next = entry.next;}size--;return entry.value;}prev = entry;entry = entry.next;}return null;}//删除public V remove(K key) {return remove(hash(key), key);}//根据key获取hashCodeprivate int hash(K key) {if (key instanceof String k) {return k.hashCode();}int hash = key.hashCode();return hash ^ (hash >>> 16);}//扩容方法private void resize() {//1.扩容一倍Entry<K, V>[] newTable = new Entry[table.length << 1];for (int i = 0; i < table.length; i++) {//2.获取每个链表的头节点，把链表进行拆分 a 和 bEntry<K, V> p = table[i];if (p != null) {/*** 拆分链表规律* hash & (table.length - 1) == 0 分为一组* hash & (table.length - 1) != 0 分为一组** 例如：*      0->8->16->24->32->40->48->56->64->72->80->null*      p**      a:0->16->32->48->64->80->null**      b:8->24->40->56->72->null*/Entry<K, V> aHead = null;Entry<K, V> bHead = null;Entry<K, V> a = null;Entry<K, V> b = null;while (p != null) {if ((p.hash & (table.length)) == 0) {//分配给aif (a != null) {a.next = p;} else {aHead = p;}a = p;} else {//分配给bif (b != null) {b.next = p;} else {bHead = p;}b = p;}p = p.next;}if (a != null) {a.next = null;table[i] = aHead;//放在原来的数组位置}if (b != null) {b.next = null;table[i + table.length] = bHead;}}}table = newTable;threshold = (int) (loadFactor * table.length);//预值}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

LeetCode题目

1题
3题
49题
217题
136题
242题
387题
819题