需求
◼ 设计一个写字楼通讯录，存放所有公司的通讯信息
座机号码作为 key(假设座机号码最长是 8 位)，公司详情(名称、地址等)作为 value
添加、删除、搜索的时间复杂度要求是 O(1)
◼ 存在什么问题?
空间复杂度非常大
空间使用率极其低，非常浪费内存空间
其实数组 companies 就是一个哈希表，典型的【空间换时间】
哈希表(Hash Table)
◼哈希表也叫做散列表( hash 有“剁碎”的意思)
◼它是如何实现高效处理数据的?
put("Jack", 666);
put("Rose", 777);
put("Kate", 888);
◼添加、搜索、删除的流程都是类似的
1.利用哈希函数生成key对应的index【O(1)】
2.根据index操作定位数组元素【O(1)】
◼哈希表是【空间换时间】的典型应用
◼哈希函数，也叫做散列函数
◼哈希表内部的数组元素，很多地方也叫 Bucket(桶)，整个数组叫 Buckets 或者 Bucket Array
哈希冲突(Hash Collision)
◼ 哈希冲突也叫做哈希碰撞
2 个不同的 key，经过哈希函数计算出相同的结果
key1 ≠ key2 ，hash(key1) = hash(key2)
◼ 解决哈希冲突的常见方法
1.开放定址法(OpenAddressing)
✓ 按照一定规则向其他地址探测，直到遇到空桶
2.再哈希法(Re-Hashing)
✓ 设计多个哈希函数
3.链地址法(SeparateChaining)
✓ 比如通过链表将同一index的元素串起来
JDK1.8的哈希冲突解决方案
◼ 默认使用单向链表将元素串起来
◼ 在添加元素时，可能会由单向链表转为红黑树来存储元素
比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时
◼ 当红黑树节点数量少到一定程度时，又会转为单向链表
◼ JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
◼ 思考:这里为什么使用单链表?
每次都是从头节点开始遍历
单向链表比双向链表少一个指针，可以节省内存空间
哈希函数
◼ 哈希表中哈希函数的实现步骤大概如下
1.先生成key的哈希值(必须是整数)
2.再让key的哈希值跟数组的大小进行相关运算，生成一个索引值
public int has(Object key) {
return hash_code(key) % tble.length;
}
◼为了提高效率，可以使用 & 位运算取代 % 运算【前提:将数组的长度设计为 2 的幂(2n】
public int has(Object key) {
return hash_code(key) % (tble.length - 1);
}
◼ 良好的哈希函数
让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能
如何生成key的哈希值
◼key 的常见种类可能有
整数、浮点数、字符串、自定义对象
不同种类的 key，哈希值的生成方式不一样，但目标是一致的
✓尽量让每个 key 的哈希值是唯一的
✓尽量让 key 的所有信息参与运算
◼ 在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null
◼整数
整数值当做哈希值
比如 10 的哈希值就是 10
// 整数
public static int hasHCode(int value) {
return value;
}
◼ 浮点数
将存储的二进制格式转为整数值
// 浮点数
public static int hasHCode(float value) {
return floatToIntBits(value);
}
Long和Double的哈希值
// Long
public static int hasHCode(long value) {
return (int)(value ^ (value >>> 32));
}
// Long
public static int hasHCode(long value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
◼>>> 和 ^ 的作用是?
高32bit 和 低32bit 混合计算出 32bit 的哈希值
充分利用所有信息计算出哈希值
>>> ：无符号右移
^ ：异或，相同为0，不同为1
static void test1() {
Integer a = 110;
Float b = 10.6f;
Long c = 156l;
Double d = 10.9;
String e = "rose";
System.out.println("整数 哈希值 = "+a.hashCode());
System.out.println("浮点数 哈希值 = "+b.hashCode());
System.out.println("Long型 哈希值 = "+c.hashCode());
System.out.println("Double 哈希值 = "+d.hashCode());
System.out.println("字符串 哈希值 = "+e.hashCode());
}
字符串的哈希值
◼整数 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 是一个奇素数，JVM会将 31 * i 优化成 (i << 5) – i
String string = "jack";
int len = string.length();
int hashCode = 0;
for (int i = 0; i < len; i++) {
char c = string.charAt(i);
hashCode = hashCode * 31 + c;
}
System.out.println(hashCode);// 3254239
String string = "jack";
int len = string.length();
int hashCode = 0;
for (int i = 0; i < len; i++) {
char c = string.charAt(i);
hashCode = (hashCode << 5) - hashCode + c;
}
System.out.println(hashCode);// 3254239
关于31的探讨
◼31 * i = (25 – 1) * i = i * 25 – i = (i << 5) – i
◼31不仅仅是符合2n – 1，它是个奇素数(既是奇数，又是素数，也就是质数)
素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
最终选择31是经过观测分布结果后的选择
自定义对象的哈希值
public class Person {
private int age;
private float height;
private String name;
private Car car;
@Override
public int hashCode() {
int hash = Integer.hashCode(age);
hash = hash * 31 + Float.hashCode(height);
hash = hash * 31 + (name != null ? name.hashCode() : 0);
hash = hash * 31 + car.hashCode();
return hash;
}
@Override
/**
* 用来比较2个对象是否相等
*/
public boolean equals(Object obj) {
// 内存地址
if (obj == this) return true;
if (obj == null || obj.getClass() != getClass()) return false;
// 比较成员变量
Person person = (Person) obj;
return person.age == age
&& person.height == height
&& valueEquals(person.name, name)
&&valueEquals(person.car, car);
}
private boolean valueEquals(Object v1, Object v2) {
return v1 == null ? v2 == null : v1.equals(v2);
}
}
static void test() {
Person p1 = new Person(10, 1.67f, "jack");
Person p2 = new Person(10, 1.67f, "jack");
System.out.println(p1.hashCode());
System.out.println(p2.hashCode());
Map<Object, Object> map = new HashMap<>();
map.put(p1, "abc");
map.put(p2, "efg");
System.out.println(map.size());
}
◼ 思考几个问题
1、哈希值太大，整型溢出怎么办?
✓ 不用作任何处理
2、不重写hashCode方法会有什么后果？
Person p1 = new Person(10, 1.67f, "jack");
Person p2 = new Person(10, 1.67f, "jack");
这样，会利用系统默认的内存相关的哈希值，认定为内存地址相等的对象，哈希值才相等，这里是两个对象，所以p1和p2虽然所以内容一样，但内存地址不一样，所以，这个两个对象的哈希值不一样。
自定义对象作为key
◼ 自定义对象作为 key，最好同时重写 hashCode 、equals 方法
equals :用以判断 2 个 key 是否为同一个 key
✓自反性:对于任何非null 的x，x.equals(x)必须返回true
✓ 对称性:对于任何非 null 的 x、y，如果 y.equals(x) 返回 true，x.equals(y) 必须返回 true
✓ 传递性:对于任何非 null 的 x、y、z，如果 x.equals(y)、y.equals(z) 返回 true，那么x.equals(z) 必须 返回 true
✓ 一致性:对于任何非 null 的 x、y，只要 equals 的比较操作在对象中所用的信息没有被修改，多次调用 x.equals(y) 就会一致地返回 true，或者一致地返回 false
✓ 对于任何非 null 的 x，x.equals(null) 必须返回 false
hashCode :必须保证 equals 为 true 的 2 个 key 的哈希值一样
反过来 hashCode 相等的 key，不一定 equals 为 true
◼ 不重写 hashCode 方法只重写 equals 会有什么后果?
✓ 可能会导致 2 个 equals 为 true 的 key 同时存在哈希表中
哈希值的进一步处理:扰动计算
private int hash(K key) {
if (key == null) return 0;
int h = key.hashCode();
return (h ^ (h >>> 16)) & (table.length - 1);
}
扰动计算：(h ^ (h >>> 16))
装填因子
◼装填因子(Load Factor):节点总数量 / 哈希表桶数组长度，也叫做负载因子
◼ 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍
◼ 思考：这里为什么使用单链表？
每次都是从头节点开始遍历
单向链表比双向链表少一个指针，可以节省内存空间
当扩容为原来容量的2倍时，节点的索引有2种情况：
1.保存不变
2.index = index + 旧容量
// 扩容
private static final float DEFAULT_LOAD_FACTOR = 0.75f;// 装填因子
private void resize() {
// 装填因子 <= 0.75
if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
Node<K, V>[] oldTable = table;
table = new Node[oldTable.length << 1];
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < oldTable.length; i++) {
if (oldTable[i] == null) continue;
queue.offer(oldTable[i]);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
// 挪动代码得放到最后面
moveNode(node);
}
}
}
private void moveNode(Node<K, V> newNode) {
// 重置
newNode.parent = null;
newNode.left = null;
newNode.right = null;
newNode.color = RED;
int index = index(newNode);
// 取出index位置的红黑树根节点
Node<K, V> root = table[index];
if (root == null) {
root = newNode;
table[index] = root;
fixAfterPut(root);
return;
}
// 添加新的节点到红黑树上面
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
K k1 = newNode.key;
int h1 = newNode.hash;
do {
parent = node;
K k2 = node.key;
int h2 = node.hash;
if (h1 > h2) {
cmp = 1;
} else if (h1 < h2) {
cmp = -1;
} else if (k1 != null && k2 != null
&& k1 instanceof Comparable
&& k1.getClass() == k2.getClass()
&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
} else {
cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
}
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
}
} while (node != null);
// 看看插入到父节点的哪个位置
newNode.parent = parent;
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
// 新添加节点之后的处理
fixAfterPut(newNode);
}
TreeMap vs HashMap
◼ 何时选择TreeMap?
元素具备可比较性且要求升序遍历(按照元素从小到大)
◼ 何时选择HashMap?
无序遍历
LinkedHashMap
◼ 在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
◼ 假设添加顺序是
37、21、31、41、97、95、52、42、83
◼ 删除度为2的节点node时
需要注意更换 node 与 前驱\后继节点 的连接位置
LinkedHashMap – 删除注意点
◼ 删除度为2的节点node时(比如删除31)
需要注意更换 node 与 前驱\后继节点 的连接位置
LinkedHashMap – 更换节点的连接位置
关于使用%来计算索引
◼ 如果使用%来计算索引
建议把哈希表的长度设计为素数(质数)
可以大大减小哈希冲突
◼ 下面表格列出了不同数据规模对应的最佳素数，特点如下
每个素数略小于前一个素数的2倍
每个素数尽可能接近2的幂(2n)
