哈希表也叫做散列表（ hash 有“剁碎”的意思）
它是如何实现高效处理数据的？
put("Jack", 666);
put("Rose", 777);
put("Kate", 888);
添加、搜索、删除的流程都是类似的
- 利用哈希函数生成
key对应的index【O(1)】 - 根据
index操作定位数组元素【O(1)】
◼ 哈希表是【空间换时间】的典型应用
◼ 哈希函数，也叫做散列函数
◼ 哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array
哈希冲突（Hash Collision）
哈希冲突也叫做哈希碰撞
2个不同的key，经过哈希函数计算出相同的结果
key1 ≠ key2，hash(key1) = hash(key2)解决哈希冲突的常见方法
- 开放定址法（Open Addressing）
✓ 按照一定规则向其他地址探测，直到遇到空桶 - 再哈希法（Re-Hashing）
✓ 设计多个哈希函数 - 链地址法（Separate Chaining）
✓ 比如通过链表将同一index的元素串起来
JDK1.8的哈希冲突解决方案
◼ 默认使用单向链表将元素串起来
◼ 在添加元素时，可能会由单向链表转为红黑树来存储元素
比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时
◼ 当红黑树节点数量少到一定程度时，又会转为单向链表
◼ JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
◼ 思考：这里为什么使用单链表？
每次都是从头节点开始遍历
单向链表比双向链表少一个指针，可以节省内存空间
单向链表和红黑树的结点中存储的是key+value
哈希函数
◼ 哈希表中哈希函数的实现步骤大概如下
- 先生成
key的哈希值（必须是整数） - 再让
key的哈希值跟数组的大小进行相关运算，生成一个索引值
public int hash(Object key) {
return hash_code(key) % table.length
}
◼ 为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（2^n）】
public int hash(Object key) {
return hash_code(key) & (table.length - 1)
}
%取模\余运算符，例如 1%2 = 1, 5%2 = 2
& 按位与运算符: 参加运算的两个数据，按二进制位进行“与”运算。如果两个相应的二进制位都为１，则该位的结果值为1；否则为0
01 2^1 - 1
011 2^2 - 1
0111 2^3 - 1
01111 2^4 - 1
1001010
&
0000111
---------------------
0000010
得到的hash值取值区间在0 ~ table.length - 1
◼ 良好的哈希函数
让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能
如何生成key的哈希值
◼ key 的常见种类可能有
整数、浮点数、字符串、自定义对象
◼ 不同种类的 key，哈希值的生成方式不一样，但目标是一致的
✓ 尽量让每个 key 的哈希值是唯一的
✓ 尽量让 key 的所有信息参与运算
◼ 在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null
1. 整数
整数值当做哈希值
比如 10 的哈希值就是 10
public static int hashCode(int value) {
return value;
}
2. 浮点数
将存储的二进制格式转为整数值
public static int hashCode(float value) {
return floatToIntBits(value);
}
3. Long和Double的哈希值
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
◼ >>> 和 ^ 的作用是？
高32bit 和 低32bit 混合计算出 32bit 的哈希值
充分利用所有信息计算出哈希值
^ 按位异或运算符 ：参加运算的两个二进制位相同为0，相异为1
4.字符串的哈希值
◼ 整数 5489 是如何计算出来的？
5 ∗ 10^3 + 4 ∗ 10^2 + 8 ∗ 10^1 + 9 ∗ 10^0
◼ 字符串是由若干个字符组成的
比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
因此，jack 的哈希值可以表示为j ∗ n^3 + a ∗ n^2 + c ∗ n^1 + k ∗ n^0，等价于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k
◼ 在JDK中，乘数 n 为 31，为什么使用 31？
✓ 31 是一个奇素数，JVM会将 31 * i 优化成 (i << 5) – i
验证：
int i = 10;
System.out.println(31 * i);
System.out.println((i << 5) - i);
310
310
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;
//hashCode = (hashCode << 5) - hashCode + c;
}
关于31的探讨
◼ 31 * i = (2^5 – 1) * i = i * 2^5 – i = (i << 5) – I
◼ 31不仅仅是符合2^n – 1，它是个奇素数（既是奇数，又是素数，也就是质数）
素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
最终选择31是经过观测分布结果后的选择
质数又称为素数，是一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；
5.自定义对象的哈希值
package com.njf;
public class Person {
private int age;
private float height;
private String name;
public Person(int age, float height, String name) {
super();
this.age = age;
this.height = height;
this.name = name;
}
@Override
public int hashCode() {
int hash = Integer.hashCode(age);
hash = hash * 31 + Float.hashCode(height);
hash = hash * 31 + (name != null ? name.hashCode() : 0);
return hash;
}
@Override
/*
* 比较两个对象是否相等
*/
public boolean equals(Object obj) {
//内存地址一样
if (this == obj) return true;
if (obj == null || obj.getClass() != getClass()) return false;
//比较成员变量
Person person = (Person) obj;
return person.age == age && person.height == height && person.name == null ? name == null : person.name.equals(name);
}
}
package com.njf;
public class Main {
public static void main(String[] args) {
Person p1 = new Person(10, 175, "jack");
Person p2 = new Person(10, 175, "jack");
System.out.println(p1.hashCode());
System.out.println(p2.hashCode());
}
}
585289065
585289065
哈希值太大，整型溢出怎么办？
✓ 不用作任何处理
自定义对象作为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
✓ 传递性：对于任何非 n ll 的 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 同时存在哈希表中
红黑树实现哈希表
package com.njf;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
@SuppressWarnings("unchecked")
public class HashMap<K,V> implements Map<K, V> {
//结点的总数
private int size;
private static final boolean RED = false;
private static final boolean BLACK = true;
private static final int DEFAULT_CAPACITY = 1 << 4;
private Node<K, V>[] table;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
table = new Node[DEFAULT_CAPACITY];
}
@Override
public int size() {
// TODO Auto-generated method stub
return size;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
@Override
public void clear() {
if (size == 0) return;
size = 0;
for (int i = 0; i < table.length; i++) {
table[i] = null;
}
}
@Override
public V put(K key, V value) {
//扩容
resize();
//先获取索引
int index = index(key);
//获取索引位置对应的根结点
Node<K, V> root = table[index];
if (root == null) {
root = new Node<>(key, value, null);
table[index] = root;
size ++;
afterPut(root);
return null;
}
// 添加的不是第一个节点
// 找到父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
int h1 = hash(key);
K k1 = key;
Node<K, V> result = null;
// 是否已经搜索过这个key
boolean searched = false;
do {
parent = node;
int h2 = node.hash;
K k2 = node.key;
if (h1 > h2) {
cmp = 1;
}else if (h1 < h2) {
cmp = -1;
}else if (Objects.equals(k1, k2)) {
cmp = 0;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
}else if (searched) {
cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
}else {
if ((node.right != null && (result = node(node.right, k1)) != null)
|| (node.left != null && (result = node(node.left, k1)) != null)) {//哈希值相等，不equals，且不具备可比性，递归遍历
//已经存在这个key
node = result;
cmp = 0;
}else {//不存在这个key,比较内存地址
searched = true;//避免代码重复扫描
cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
}
}
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
V oldValue = node.value;
node.key = key;
node.value = value;
node.hash = h1;
return oldValue;
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<K, V> newNode = new Node<>(key, value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
afterPut(newNode);
return null;
}
@Override
public V get(K key) {
Node<K, V> node = node(key);
return node != null ? node.value : null;
}
@Override
public V remove(K key) {
Node<K, V> node = node(key);
return remove(node);
}
@Override
public boolean containsKey(K key) {
return node(key) != null;
}
@Override
public boolean containsValue(V value) {
if (size == 0) return false;
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < table.length; i++) {
Node<K, V> root = table[I];
if (root == null) continue;
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (Objects.equals(value, node.value)) return true;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return false;
}
@Override
public void traversal(Visitor<K, V> visitor) {
if (size == 0) return;
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < table.length; i++) {
Node<K, V> root = table[I];
if (root == null) continue;
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (visitor.visit(node.key, node.value)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return;
}
/*
* 删除结点
*/
private V remove(Node<K, V> node) {
if (node == null) return null;
size--;
V oldValue = node.value;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<K, V> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.key = s.key;
node.value = s.value;
node.hash = s.hash;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<K, V> replacement = node.left != null ? node.left : node.right;
Node<K, V> root = table[index(node)];
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
// 删除节点之后的处理
afterRemove(replacement);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
// 删除节点之后的处理
afterRemove(node);
}
return oldValue;
}
/*
* 扩容
*/
private void resize() {
// 装填因子 <= 0.75
if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
Node<K, V> [] oldTable = table;
table = new Node[table.length << 1];
//层序遍历
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < oldTable.length; i++) {
Node<K, V> root = oldTable[I];
if (root == null) continue;
queue.offer(root);
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.key);
//获取索引位置对应的根结点
Node<K, V> root = table[index];
if (root == null) {
root = newNode;
table[index] = root;
afterPut(root);
return;
}
// 添加的不是第一个节点
// 找到父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
int h1 = newNode.hash;
K k1 = newNode.key;
do {
parent = node;
int h2 = node.hash;
K k2 = node.key;
if (h1 > h2) {
cmp = 1;
}else if (h1 < h2) {
cmp = -1;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (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;
}
// 新添加节点之后的处理
afterPut(newNode);
}
/*
* 删除结点之后染色
*/
private void afterRemove(Node<K, V> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
Node<K, V> parent = node.parent;
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<K, V> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
/*
* 后继结点
*/
private Node<K, V> successor(Node<K, V> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<K, V> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
private Node<K, V> node(K key){
int index = index(key);
Node<K, V> root = table[index];
return root == null ? null : node(root, key);
}
/*
* 根据key获取对应的结点
*/
private Node<K, V> node(Node<K, V> node, K k1){
int h1 = hash(k1);
//存储查找结果
Node<K, V> result = null;
int cmp = 0;
while (node != null) {
K k2 = node.key;
int h2 = node.hash;
if (h1 > h2) {
node = node.right;
}else if (h1 < h2) {
node = node.left;
}else if (Objects.equals(k1, k2)) {//哈希值相等，判断值是否相等
return node;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) {//同一类别，且具备可比较性(实现了Comparable接口)
node = cmp > 0 ? node.right : node.left;
//哈希值相等，不equals，且不具备可比较性，递归查找
}else if (node.right != null && (result = node(node.right,k1)) != null) {//递归调用，直到找到node
return result;
}else {
node = node.left;
}
// else if (node.left != null && (result = node(node.left,k1)) != null) {
// return result;
// }else {
// return null;
// }
}
return null;
}
/*
* 结点染色
*/
private void afterPut(Node<K, V> node) {
Node<K, V> parent = node.parent;
// 添加的是根节点 或者 上溢到达了根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<K, V> uncle = parent.sibling();
// 祖父节点
Node<K, V> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterPut(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
private void rotateLeft(Node<K, V> grand) {
Node<K, V> parent = grand.right;
Node<K, V> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand, parent, child);
}
private void rotateRight(Node<K, V> grand) {
Node<K, V> parent = grand.left;
Node<K, V> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand, parent, child);
}
private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
// 让parent称为子树的根节点
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else { // grand是root节点
table[index(grand)] = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
}
private Node<K, V> color(Node<K, V> node, boolean color) {
if (node == null) return node;
node.color = color;
return node;
}
private Node<K, V> red(Node<K, V> node) {
return color(node, RED);
}
private Node<K, V> black(Node<K, V> node) {
return color(node, BLACK);
}
private boolean colorOf(Node<K, V> node) {
return node == null ? BLACK : node.color;
}
private boolean isBlack(Node<K, V> node) {
return colorOf(node) == BLACK;
}
private boolean isRed(Node<K, V> node) {
return colorOf(node) == RED;
}
// /**
// * 比较key大小
// * @param k1
// * @param k2
// * @param h1 k1的hashCode
// * @param h2 k2的hashCode
// * @return
// */
// private int compare(K k1, K k2,int h1, int h2) {
// // 比较哈希值
// int result = h1 - h2;
// if (result != 0) return result;
// //比较euqals
// if (Objects.equals(k1, k2)) return 0;
// //hash值相等， 但是不euqals
// //比较类名
// if (k1 != null && k2 != null) {
// String k1Cls = k1.getClass().getName();
// String k2Cls = k2.getClass().getName();
// result = k1Cls.compareTo(k2Cls);
// if (result != 0) return result;
//
// // 同一种类型并且具备可比较性
// if (k1 instanceof Comparable) {
// return ((Comparable) k1).compareTo(k2);
// }
// }
// // 同一种类型，哈希值相等，但是不equals，但是不具备可比较性
// // k1不为null，k2为null
// // k1为null，k2不为null
// return System.identityHashCode(k1) - System.identityHashCode(k2);
// }
/*
* 打印哈希表
*/
public void print() {
if (size == 0) return;
for (int i = 0; i < table.length; i++) {
final Node<K, V> root = table[I];
System.out.println("【index = " + i + "】");
BinaryTrees.println(new BinaryTreeInfo() {
@Override
public Object string(Object node) {
return node;
}
@Override
public Object root() {
return root;
}
@Override
public Object right(Object node) {
return ((Node<K, V>) node).left;
}
@Override
public Object left(Object node) {
return ((Node<K, V>) node).right;
}
});
System.out.println("---------------------------------------------------");
}
}
/**
* 根据key生成对应的索引（在桶数组中的位置）
*/
private int index(K key) {
return hash(key) & (table.length - 1);
}
private int hash(K key) {
if (key == null) return 0;
int hash = key.hashCode();
return hash ^ (hash >> 16);
}
private int index(Node<K, V> node) {
return node.hash & (table.length - 1);
}
private static class Node<K, V> {
int hash;
K key;
V value;
boolean color = RED;
Node<K, V> left;
Node<K, V> right;
Node<K, V> parent;
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
int hash = key == null ? 0 : key.hashCode();
this.hash = hash ^ (hash >>> 16);
this.value = value;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
public boolean isRightChild() {
return parent != null && this == parent.right;
}
public Node<K, V> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
@Override
public String toString() {
return "Node_" + key + "_" + value;
}
}
}
验证
package com.njf;
import com.njf.Map.Visitor;
public class Main {
static void test2(HashMap<Object, Integer> map) {
for (int i = 1; i <= 20; i++) {
map.put(new Key(i), i);
}
for (int i = 5; i <= 7; i++) {
map.put(new Key(i), i + 5);
}
System.out.println(map.size());
Asserts.test(map.size() == 20);
Asserts.test(map.get(new Key(4)) == 4);
Asserts.test(map.get(new Key(5)) == 10);
Asserts.test(map.get(new Key(6)) == 11);
Asserts.test(map.get(new Key(7)) == 12);
Asserts.test(map.get(new Key(8)) == 8);
}
static void test3(HashMap<Object, Integer> map) {
map.put(null, 1); // 1
map.put(new Object(), 2); // 2
map.put("jack", 3); // 3
map.put(10, 4); // 4
map.put(new Object(), 5); // 5
map.put("jack", 6);
map.put(10, 7);
map.put(null, 8);
map.put(10, null);
Asserts.test(map.size() == 5);
Asserts.test(map.get(null) == 8);
Asserts.test(map.get("jack") == 6);
Asserts.test(map.get(10) == null);
Asserts.test(map.get(new Object()) == null);
Asserts.test(map.containsKey(10));
Asserts.test(map.containsKey(null));
Asserts.test(map.containsValue(null));
Asserts.test(map.containsValue(1) == false);
}
static void test4(HashMap<Object, Integer> map) {
map.put("jack", 1);
map.put("rose", 2);
map.put("jim", 3);
map.put("jake", 4);
map.remove("jack");
map.remove("jim");
for (int i = 1; i <= 10; i++) {
map.put("test" + i, i);
map.put(new Key(i), i);
}
for (int i = 5; i <= 7; i++) {
Asserts.test(map.remove(new Key(i)) == i);
}
for (int i = 1; i <= 3; i++) {
map.put(new Key(i), i + 5);
}
Asserts.test(map.size() == 19);
Asserts.test(map.get(new Key(1)) == 6);
Asserts.test(map.get(new Key(2)) == 7);
Asserts.test(map.get(new Key(3)) == 8);
Asserts.test(map.get(new Key(4)) == 4);
Asserts.test(map.get(new Key(5)) == null);
Asserts.test(map.get(new Key(6)) == null);
Asserts.test(map.get(new Key(7)) == null);
Asserts.test(map.get(new Key(8)) == 8);
map.traversal(new Visitor<Object, Integer>() {
public boolean visit(Object key, Integer value) {
System.out.println(key + "_" + value);
return false;
}
});
}
static void test5(HashMap<Object, Integer> map) {
for (int i = 1; i <= 20; i++) {
map.put(new SubKey1(i), i);
}
map.put(new SubKey2(1), 5);
Asserts.test(map.get(new SubKey1(1)) == 5);
Asserts.test(map.get(new SubKey2(1)) == 5);
Asserts.test(map.size() == 20);
}
public static void main(String[] args) {
test2(new HashMap<>());
test3(new HashMap<>());
test4(new HashMap<>());
test5(new HashMap<>());
}
}
相关类别 Key
package com.njf;
public class Key {
protected int value;
public Key(int value) {
this.value = value;
}
@Override
public int hashCode() {
return value / 10;
}
@Override
public boolean equals(Object obj) {
if (obj == this) return true;
if (obj == null || obj.getClass() != getClass()) return false;
return ((Key) obj).value == value;
}
@Override
public String toString() {
return "v(" + value + ")";
}
}
SubKey1
package com.njf;
public class SubKey1 extends Key {
public SubKey1(int value) {
super(value);
}
@Override
public boolean equals(Object obj) {
if (obj == this) return true;
if (obj == null ||
(obj.getClass() != SubKey1.class
&& obj.getClass() != SubKey2.class)) return false;
return ((Key) obj).value == value;
}
}
SubKey2
package com.njf;
public class SubKey2 extends Key {
public SubKey2(int value) {
super(value);
}
@Override
public boolean equals(Object obj) {
if (obj == this) return true;
if (obj == null ||
(obj.getClass() != SubKey1.class
&& obj.getClass() != SubKey2.class)) return false;
return ((Key) obj).value == value;
}
}
哈希表扩容
装填因子
◼ 装填因子（Load Factor）：节点总数量 / 哈希表桶数组长度，也叫做负载因子
◼ 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍
例如：
一开始哈希表的容量是 2 * 2
1010 //哈希值
& 11 //table.length - 1
-----
10
1110 //哈希值
& 11
-----
10
扩容为 2 * 3
1010 //哈希值
&111 //table.length - 1
-----
010
1110 //哈希值
&111
-----
110
结论：
当哈希表扩容为原来容量的2倍时,节点的索引有两种情况
1.保持不变
2.index = index + 旧容量
参考上例 扩容前 index = 10，扩容后 index = 110 = 10 + 100 ,其中100是 2 ^2 = 旧容量
扩容相关代码
/*
* 扩容
*/
private void resize() {
// 装填因子 <= 0.75
if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
Node<K, V> [] oldTable = table;
table = new Node[table.length << 1];
//层序遍历
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < oldTable.length; i++) {
Node<K, V> root = oldTable[I];
if (root == null) continue;
queue.offer(root);
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.key);
//获取索引位置对应的根结点
Node<K, V> root = table[index];
if (root == null) {
root = newNode;
table[index] = root;
afterPut(root);
return;
}
// 添加的不是第一个节点
// 找到父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
int h1 = newNode.hash;
K k1 = newNode.key;
do {
parent = node;
int h2 = node.hash;
K k2 = node.key;
if (h1 > h2) {
cmp = 1;
}else if (h1 < h2) {
cmp = -1;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (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;
}
// 新添加节点之后的处理
afterPut(newNode);
}
TreeMap vs HashMap
◼ 何时选择TreeMap？
元素具备可比较性且要求升序遍历（按照元素从小到大）
◼ 何时选择HashMap？
无序遍历
LinkedHashMap
◼ 在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
◼ 假设添加顺序是
37、21、31、41、97、95、52、42、83
◼ 删除度为2的节点node时
需要注意更换 node 与 前驱\后继节点 的连接位置
例如删除31
1.图中只是链表中只是画了next指针指向
2.交换的是节点在链表中的连接关系(指针指向)，并不影响红黑树，只有交换才能在遍历节点的时候不改变节点的添加顺序
3.链表是串联了全部的红黑树的节点
LinkedHashMap – 更换节点的连接位置
HashMap代码
package com.njf;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
@SuppressWarnings("unchecked")
public class HashMap<K,V> implements Map<K, V> {
//结点的总数
private int size;
private static final boolean RED = false;
private static final boolean BLACK = true;
private static final int DEFAULT_CAPACITY = 1 << 4;
private Node<K, V>[] table;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
table = new Node[DEFAULT_CAPACITY];
}
@Override
public int size() {
// TODO Auto-generated method stub
return size;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
@Override
public void clear() {
if (size == 0) return;
size = 0;
for (int i = 0; i < table.length; i++) {
table[i] = null;
}
}
@Override
public V put(K key, V value) {
//扩容
resize();
//先获取索引
int index = index(key);
//获取索引位置对应的根结点
Node<K, V> root = table[index];
if (root == null) {
root = createNode(key, value, null);
table[index] = root;
size ++;
fixAfterPut(root);
return null;
}
// 添加的不是第一个节点
// 找到父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
int h1 = hash(key);
K k1 = key;
Node<K, V> result = null;
// 是否已经搜索过这个key
boolean searched = false;
do {
parent = node;
int h2 = node.hash;
K k2 = node.key;
if (h1 > h2) {
cmp = 1;
}else if (h1 < h2) {
cmp = -1;
}else if (Objects.equals(k1, k2)) {
cmp = 0;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
}else if (searched) {
cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
}else {
if ((node.right != null && (result = node(node.right, k1)) != null)
|| (node.left != null && (result = node(node.left, k1)) != null)) {//哈希值相等，不equals，且不具备可比性，递归遍历
//已经存在这个key
node = result;
cmp = 0;
}else {//不存在这个key,比较内存地址
searched = true;//避免代码重复扫描
cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
}
}
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
V oldValue = node.value;
node.key = key;
node.value = value;
node.hash = h1;
return oldValue;
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<K, V> newNode = createNode(key, value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
fixAfterPut(newNode);
return null;
}
@Override
public V get(K key) {
Node<K, V> node = node(key);
return node != null ? node.value : null;
}
@Override
public V remove(K key) {
Node<K, V> node = node(key);
return remove(node);
}
@Override
public boolean containsKey(K key) {
return node(key) != null;
}
@Override
public boolean containsValue(V value) {
if (size == 0) return false;
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < table.length; i++) {
Node<K, V> root = table[i];
if (root == null) continue;
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (Objects.equals(value, node.value)) return true;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return false;
}
@Override
public void traversal(Visitor<K, V> visitor) {
if (size == 0) return;
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < table.length; i++) {
Node<K, V> root = table[i];
if (root == null) continue;
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (visitor.visit(node.key, node.value)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return;
}
/*
* 删除结点
*/
private V remove(Node<K, V> node) {
if (node == null) return null;
size--;
Node<K, V> willNode = node;
V oldValue = node.value;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<K, V> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.key = s.key;
node.value = s.value;
node.hash = s.hash;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<K, V> replacement = node.left != null ? node.left : node.right;
Node<K, V> root = table[index(node)];
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
// 删除节点之后的处理
fixAfterRemove(replacement);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
// 删除节点之后的处理
fixAfterRemove(node);
}
//交给子类去处理
afterRemove(willNode,node);
return oldValue;
}
/*
* 子类处理删除节点的指针指向
*/
protected void afterRemove(Node<K, V> willNode,Node<K, V> removeNode) {}
/*
* 扩容
*/
private void resize() {
// 装填因子 <= 0.75
if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
Node<K, V> [] oldTable = table;
table = new Node[table.length << 1];
//层序遍历
Queue<Node<K, V>> queue = new LinkedList<>();
for (int i = 0; i < oldTable.length; i++) {
Node<K, V> root = oldTable[i];
if (root == null) continue;
queue.offer(root);
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);
}
}
}
protected Node<K, V> createNode(K key, V value,Node<K, V> parent) {
return new Node<K, V>(key, value, parent);
}
/*
* 节点当作新添加的节点在扩容的哈希表中重新添加
*/
private void moveNode(Node<K, V> newNode) {
// 重置
newNode.parent = null;
newNode.left = null;
newNode.right = null;
newNode.color = RED;
//先获取索引
int index = index(newNode.key);
//获取索引位置对应的根结点
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;
int h1 = newNode.hash;
K k1 = newNode.key;
do {
parent = node;
int h2 = node.hash;
K k2 = node.key;
if (h1 > h2) {
cmp = 1;
}else if (h1 < h2) {
cmp = -1;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (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);
}
/*
* 删除结点之后染色
*/
private void fixAfterRemove(Node<K, V> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
Node<K, V> parent = node.parent;
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<K, V> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
fixAfterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
fixAfterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
/*
* 后继结点
*/
private Node<K, V> successor(Node<K, V> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<K, V> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
private Node<K, V> node(K key){
int index = index(key);
Node<K, V> root = table[index];
return root == null ? null : node(root, key);
}
/*
* 根据key获取对应的结点
*/
private Node<K, V> node(Node<K, V> node, K k1){
int h1 = hash(k1);
//存储查找结果
Node<K, V> result = null;
int cmp = 0;
while (node != null) {
K k2 = node.key;
int h2 = node.hash;
if (h1 > h2) {
node = node.right;
}else if (h1 < h2) {
node = node.left;
}else if (Objects.equals(k1, k2)) {//哈希值相等，判断值是否相等
return node;
}else if (k1 != null && k2 != null
&& k1.getClass() == k2.getClass()
&& k1 instanceof Comparable
&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) {//同一类别，且具备可比较性(实现了Comparable接口)
node = cmp > 0 ? node.right : node.left;
//哈希值相等，不equals，且不具备可比较性，递归查找
}else if (node.right != null && (result = node(node.right,k1)) != null) {//递归调用，直到找到node
return result;
}else {
node = node.left;
}
// else if (node.left != null && (result = node(node.left,k1)) != null) {
// return result;
// }else {
// return null;
// }
}
return null;
}
/*
* 结点染色
*/
private void fixAfterPut(Node<K, V> node) {
Node<K, V> parent = node.parent;
// 添加的是根节点 或者 上溢到达了根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<K, V> uncle = parent.sibling();
// 祖父节点
Node<K, V> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
fixAfterPut(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
private void rotateLeft(Node<K, V> grand) {
Node<K, V> parent = grand.right;
Node<K, V> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand, parent, child);
}
private void rotateRight(Node<K, V> grand) {
Node<K, V> parent = grand.left;
Node<K, V> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand, parent, child);
}
private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
// 让parent称为子树的根节点
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else { // grand是root节点
table[index(grand)] = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
}
private Node<K, V> color(Node<K, V> node, boolean color) {
if (node == null) return node;
node.color = color;
return node;
}
private Node<K, V> red(Node<K, V> node) {
return color(node, RED);
}
private Node<K, V> black(Node<K, V> node) {
return color(node, BLACK);
}
private boolean colorOf(Node<K, V> node) {
return node == null ? BLACK : node.color;
}
private boolean isBlack(Node<K, V> node) {
return colorOf(node) == BLACK;
}
private boolean isRed(Node<K, V> node) {
return colorOf(node) == RED;
}
// /**
// * 比较key大小
// * @param k1
// * @param k2
// * @param h1 k1的hashCode
// * @param h2 k2的hashCode
// * @return
// */
// private int compare(K k1, K k2,int h1, int h2) {
// // 比较哈希值
// int result = h1 - h2;
// if (result != 0) return result;
// //比较euqals
// if (Objects.equals(k1, k2)) return 0;
// //hash值相等， 但是不euqals
// //比较类名
// if (k1 != null && k2 != null) {
// String k1Cls = k1.getClass().getName();
// String k2Cls = k2.getClass().getName();
// result = k1Cls.compareTo(k2Cls);
// if (result != 0) return result;
//
// // 同一种类型并且具备可比较性
// if (k1 instanceof Comparable) {
// return ((Comparable) k1).compareTo(k2);
// }
// }
// // 同一种类型，哈希值相等，但是不equals，但是不具备可比较性
// // k1不为null，k2为null
// // k1为null，k2不为null
// return System.identityHashCode(k1) - System.identityHashCode(k2);
// }
/*
* 打印哈希表
*/
public void print() {
if (size == 0) return;
for (int i = 0; i < table.length; i++) {
final Node<K, V> root = table[i];
System.out.println("【index = " + i + "】");
BinaryTrees.println(new BinaryTreeInfo() {
@Override
public Object string(Object node) {
return node;
}
@Override
public Object root() {
return root;
}
@Override
public Object right(Object node) {
return ((Node<K, V>) node).left;
}
@Override
public Object left(Object node) {
return ((Node<K, V>) node).right;
}
});
System.out.println("---------------------------------------------------");
}
}
/**
* 根据key生成对应的索引（在桶数组中的位置）
*/
private int index(K key) {
return hash(key) & (table.length - 1);
}
private int hash(K key) {
if (key == null) return 0;
int hash = key.hashCode();
return hash ^ (hash >> 16);
}
private int index(Node<K, V> node) {
return node.hash & (table.length - 1);
}
protected static class Node<K, V> {
int hash;
K key;
V value;
boolean color = RED;
Node<K, V> left;
Node<K, V> right;
Node<K, V> parent;
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
int hash = key == null ? 0 : key.hashCode();
this.hash = hash ^ (hash >>> 16);
this.value = value;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
public boolean isRightChild() {
return parent != null && this == parent.right;
}
public Node<K, V> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
@Override
public String toString() {
return "Node_" + key + "_" + value;
}
}
}
LinkedHashMap
package com.njf;
import java.util.Objects;
import com.njf.HashMap.Node;
@SuppressWarnings("unchecked")
public class LinkedHashMap<K,V> extends HashMap<K, V> {
private LinkedNode<K,V> first;
private LinkedNode<K,V> last;
@Override
public boolean containsValue(V value) {
LinkedNode<K,V> node = first;
while (node != null) {
if (Objects.equals(value, node.value)) return true;
node = node.next;
}
return false;
}
@Override
protected void afterRemove(Node<K, V> willNode,Node<K, V> removeNode) {
LinkedNode<K,V> node1 = (LinkedNode<K,V>)willNode;
LinkedNode<K,V> node2 = (LinkedNode<K,V>)removeNode;
if (node1 != node2) {//删除的是度为2的节点，实际删除的是后继节点removeNode
// 交换WillNode和removedNode在链表中的位置
// 交换prev
LinkedNode<K,V> tmpPre = node1.pre;
node1.pre = node2.pre;
node2.pre = tmpPre;
if (node1.pre == null) {
first = node1;
}else {
node1.pre.next = node1;
}
if (node2.pre == null) {
first = node1;
}else {
node2.pre.next = node1;
}
// 交换next
LinkedNode<K,V> tmpNext = node1.next;
node1.next = node2.next;
node2.next = tmpNext;
if (node1.next == null) {
last = node1;
}else {
node1.next.pre = node1;
}
if (node2.next == null) {
last = node1;
}else {
node2.next.pre = node1;
}
}
LinkedNode<K,V> pre = node2.pre;
LinkedNode<K,V> next = node2.next;
if (pre == null) {
first = next;
}else {
pre.next = next;
}
if (next == null) {
last = pre;
}else {
next.pre = pre;
}
super.afterRemove(willNode, removeNode);;
}
@Override
public void clear() {
first = null;
last = null;
super.clear();
}
@Override
public void traversal(Visitor<K, V> visitor) {
if (visitor == null) return;
LinkedNode<K, V> node = first;
while (node != null) {
if (visitor.visit(node.key, node.value)) return;
node = node.next;
}
}
@Override
protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
LinkedNode<K,V> node = new LinkedNode(key, value, parent);
if (first == null) {
first = last = node;
}else {
last.next = node;
node.pre = last;
last = node;
}
return node;
}
private static class LinkedNode<K,V> extends Node<K, V>{
LinkedNode<K,V> pre;
LinkedNode<K,V> next;
public LinkedNode(K key, V value, Node<K, V> parent) {
super(key, value, parent);
}
}
}
验证
package com.njf;
import com.njf.Map.Visitor;
public class Main {
static void test(HashMap<Object, Integer> map) {
map.put("jack", 1);
map.put("rose", 2);
map.put("jim", 3);
map.put("jake", 4);
map.remove("jack");
map.remove("jim");
for (int i = 1; i <= 10; i++) {
map.put("test" + i, i);
map.put(new Key(i), i);
}
for (int i = 5; i <= 7; i++) {
Asserts.test(map.remove(new Key(i)) == i);
}
for (int i = 1; i <= 3; i++) {
map.put(new Key(i), i + 5);
}
Asserts.test(map.size() == 19);
Asserts.test(map.get(new Key(1)) == 1);
Asserts.test(map.get(new Key(2)) == 2);
Asserts.test(map.get(new Key(3)) == 3);
Asserts.test(map.get(new Key(4)) == 4);
Asserts.test(map.get(new Key(5)) == null);
Asserts.test(map.get(new Key(6)) == null);
Asserts.test(map.get(new Key(7)) == null);
Asserts.test(map.get(new Key(8)) == 8);
map.traversal(new Visitor<Object, Integer>() {
public boolean visit(Object key, Integer value) {
System.out.println(key + "_" + value);
return false;
}
});
}
public static void main(String[] args) {
test(new LinkedHashMap<>());
}
}
结果打印
rose_2
jake_4
test1_1
v(1)_6
test2_2
v(2)_7
test3_3
v(3)_8
test4_4
v(4)_4
test5_5
test6_6
test7_7
test8_8
v(8)_8
test9_9
v(9)_9
test10_10
v(10)_10
关于使用%来计算索引
◼ 如果使用%来计算索引
建议把哈希表的长度设计为素数（质数）
可以大大减小哈希冲突
10%8 = 2
20%8 = 4
30%8 = 6
40%8 = 0
50%8 = 2
60%8 = 4
70%8 = 6
10%7 = 3
20%7 = 6
30%7 = 2
40%7 = 5
50%7 = 1
60%7 = 4
70%7 = 0
◼ 下面表格列出了不同数据规模对应的最佳素数，特点如下
每个素数略小于前一个素数的2倍
每个素数尽可能接近2的幂（2n）
