Hash散列
一、定义
哈希散列（Hashing）是一种重要的数据结构和算法，它被广泛应用于计算机科学和工程领域。哈希散列通过将任意长度的输入数据映射为固定长度的输出，将数据快速地存储和检索，同时保证数据的完整性和安全性。
二、原理
哈希散列的核心是哈希函数，它是一种将输入数据映射为固定长度的输出的算法。哈希函数的输出通常称为哈希值或散列码。好的哈希函数应该具备以下特性：
- 一致性：对于相同的输入，哈希函数应该始终产生相同的输出。
- 高效性：计算哈希值的时间应该很短。
- 低碰撞率：哈希函数应该将不同的输入均匀地映射到哈希空间中，以尽量减少碰撞的发生。
三、冲突解决
冲突是指不同的输入数据被映射到了相同的哈希值上。为了解决冲突，我们需要使用冲突解决方法，常见的方法包括：
- 链表法：在散列表的每个槽中存储一个链表，冲突的键值对被存储在同一个槽对应的链表中。
- 开放地址法：当发生冲突时，通过一定的算法（如线性探测、二次探测、双重散列等）寻找其他可用的槽位来存储冲突的键值对。
- 再哈希法（Rehashing）：当发生冲突时，通过应用另一个散列函数来计算新的哈希值，然后将键值对存储到新的位置。这个新的位置通常与原始哈希值的一定偏移量相关联。再哈希法可以避免某些特定的冲突序列，但需要保证新的哈希函数满足一致性、高效性和均匀性的要求。
- Cuckoo Hashing：Cuckoo Hashing是一种高效的解决哈希冲突的方法，它通过使用两个散列表来存储数据。当发生冲突时，它会尝试将冲突的键重新哈希到另一个表中，如果另一个表中的位置已经被占用，那么会触发一系列的重新哈希操作，直到找到空闲的位置或达到最大重新哈希次数为止。Cuckoo Hashing通常具有良好的平均性能，但可能会导致插入操作的时间复杂度变为O(n)，其中n是哈希表中的元素数量。
- 线性探测再哈希（Linear Probing with Rehashing）：线性探测再哈希是一种结合了线性探测和再哈希法的冲突解决方法。当发生冲突时，它首先尝试在散列表中寻找下一个空闲的位置，如果找到则插入，如果散列表已满则触发再哈希操作来扩展散列表的大小。
- 分离链接法（Separate Chaining）：分离链接法是一种使用链表来解决冲突的方法，它与传统的链表法类似，但是在每个槽中存储的是一个链表的头指针而不是整个链表。这样可以节省内存空间，并且在处理冲突时只需操作链表的指针而不需要移动数据，因此性能较好。
这些方法都有各自的优缺点，选择合适的冲突解决方法取决于应用的具体需求和性能要求。在实际应用中，可能会根据数据分布的特点和实际情况选择最合适的方法。
四、应用
哈希散列被广泛应用于各种场景：
- 散列表（Hash Table）：散列表是一种基于哈希散列实现的数据结构，用于快速存储和检索数据。它通过哈希函数将键映射到索引位置，并在该位置存储对应的值。这样，在大多数情况下，查找、插入和删除操作的时间复杂度可以达到常数级别，即O(1)。
- 数据完整性检查：哈希函数在密码学中扮演着重要角色，用于验证数据的完整性。通过计算数据的哈希值并将其与预期的哈希值进行比较，可以检测出数据是否被篡改。
- 密码学：哈希函数被用于密码学中的各种算法，如消息摘要算法（MD5、SHA-1、SHA-256等）。它们用于生成消息的数字摘要，用于验证数据的完整性和生成数字签名。
五、实现
5.1 基于红黑树实现
/**
* @Description hashMap
* @Author lcy
* @Date 2021/1/12 9:27
*/
public class HashMap<K,V> {
/**
* 红色节点
*/
private static final boolean RED = true;
/**
* 黑色节点
*/
private static final boolean BLACK = false;
/**
* 排序接口实现
*/
protected Comparator<K> comparator = (o1,o2) -> {
if (o1 != null && o2 != null) {
if (o1.hashCode() == o2.hashCode() && o1.equals(o2)) {
return 0;
} else {
return o1.hashCode() - o2.hashCode();
}
} else {
throw new ServiceException("key could not be null");
}
};
/**
* 大小
*/
private int size;
/**
* hash数组
*/
private Node<K,V>[] table;
/**
* 默认数组长度，2的4次方
*/
private static final int DEFAULT_CAPACITY = 1 << 4;
/**
* 装填因子
*/
private static final float DEFAULT_LOAD_FACTORY = 0.75f;
public HashMap(){
table = new Node[DEFAULT_CAPACITY];
}
public HashMap(int capacity){
table = new Node[capacity];
}
/**
* 添加map
* @param key key
* @param value value
* @author lcy
* @date 2021/1/5 16:17
**/
public V put(K key,V value){
int hash = hash(key);
int index = index(hash);
//红黑树根节点
Node<K,V> root = table[index];
if (root == null) {
root = new Node<>(key,value,null);
table[index] = root;
size++;
changeBlack(root);
return null;
}
Node<K,V> node = root;
Node<K,V> parent;
int cmp;
Node<K,V> tmpNode;
boolean isSearch = false;
do {
parent = node;
if (hash > node.hash) {
cmp = 1;
} else if (hash < node.hash) {
cmp = -1;
} else if (Tools.equals(key,node.key)) {
cmp = 0;
//值不相等，进一步判断
} else if (key != null && node.key != null &&
key.getClass() == node.key.getClass() && key instanceof Comparable
&& (cmp = ((Comparable)key).compareTo(node.key)) != 0) {
//hash相等，不具备可比较性
} else if (isSearch) {
cmp = System.identityHashCode(key) - System.identityHashCode(node.key);
} else {
if ((node.left != null && (tmpNode = node(node.left,key)) != null)
|| node.right != null && (tmpNode = node(node.right,key)) != null) {
node = tmpNode;
cmp = 0;
} else {
//不存在key
isSearch = true;
cmp = System.identityHashCode(key) - System.identityHashCode(node.key);
}
}
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
node.key = key;
V oldValue = node.value;
node.value = value;
return oldValue;
}
//else {
// cmp = compare(key,node.key,hash,node.hash);
// //hashCode相等，值也相等,包含两个值都为null的情况
// if (!Tools.equals(key,node.key)) {
// //红黑树根节点
// int newIndex = (index + (1 << hashIndex)) & (table.length - 1);
// node = table[newIndex];
// hashIndex += 1;
// System.out.println(node);
// if (node == null) {
// node = new Node<>(key,value,null);
// table[newIndex] = node;
// size++;
// changeBlack(node);
// return null;
// } else {
// continue;
// }
// }
// node.key = key;
// V oldValue = node.value;
// node.value = value;
// 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++;
afterAdd(newNode);
return newNode.value;
}
/**
* 判断key是否存在
* @param key key
* @return boolean
* @author lcy
* @date 2021/1/5 16:17
**/
public boolean containsKey(K key){
return node(key) != null;
}
/**
* 判断value是否存在
* @param value value
* @return boolean
* @author lcy
* @date 2021/1/5 16:17
**/
public boolean containsValue(V value){
if (isEmpty()) {
return false;
}
Queue<Node<K,V>> queue = new LinkedBlockingQueue<>();
//遍历数组，数组里的红黑树层序遍历判断value是否存在
for (Node<K,V> kvNode : table) {
if (kvNode == null) {
continue;
}
queue.offer(kvNode);
while (!queue.isEmpty()) {
Node<K,V> node = queue.poll();
if (Tools.equals(node.value,value)) {
return true;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return false;
}
/**
* 根据key获取value
* @param key key
* @return boolean
* @author lcy
* @date 2021/1/5 16:17
**/
public V get(K key){
Node<K,V> node = node(key);
return node == null ? null : node.value;
}
/**
* 返回长度
*/
public int size(){
return size;
}
/**
* 判断是否为空
* @return boolean
* @author lcy
* @date 2020/9/3 20:58
**/
public boolean isEmpty(){
return size == 0;
}
/**
* 遍历打印map数据
* @author lcy
* @date 2021/1/12 19:10
**/
public void traversal(){
if (isEmpty()) {
return;
}
Queue<Node<K,V>> queue = new LinkedBlockingQueue<>();
//遍历数组，数组里的红黑树层序遍历判断value是否存在
for (Node<K,V> kvNode : table) {
if (kvNode == null) {
continue;
}
queue.offer(kvNode);
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);
}
System.out.print("[key={" + node.key + "},value={" + node.value + "},");
}
}
}
/**
* 遍历打印map里红黑树数据
* @author lcy
* @date 2021/1/12 19:10
**/
public void print(){
if (isEmpty()) {
return;
}
//遍历数组，数组里的红黑树层序遍历判断value是否存在
for (int i = 0; i < table.length; i++) {
Node<K,V> kvNode = table[i];
System.out.println("------------------index(" + i + ")-------------------");
BinaryTrees.print(new BinaryTreeInfo() {
@Override public Object root(){
return kvNode;
}
@Override public Object left(Object node){
return ((Node<K,V>)node).left;
}
@Override public Object right(Object node){
return ((Node<K,V>)node).right;
}
@Override public Object string(Object node){
return node;
}
});
System.out.println();
System.out.println("------------------index(" + i + ")-------------------");
}
}
/**
* 清除数二叉树
* @author lcyb
* @date 2020/9/3 20:56
**/
public void clear(){
if (size == 0) {
return;
}
size = 0;
Arrays.fill(table,null);
}
/**
* 删除指定对象
* @param key 需要删除的对象
* @author lcy
* @date 2020/9/3 21:01
**/
public V remove(K key){
return remove(node(key));
}
/**
* 删除指定对象
* @param deleteNode 需要删除的对象
* @author lcy
* @date 2020/9/3 21:01
**/
private V remove(Node<K,V> deleteNode){
if (deleteNode == null) {
return null;
}
size--;
if (deleteNode.hasTwoChildren()) {
//获取后继节点
Node<K,V> successor = successor(deleteNode);
if (successor != null) {
//替换节点值为后继节点值
deleteNode.key = successor.key;
deleteNode.value = successor.value;
deleteNode.hash = successor.hash;
}
//删除节点
deleteNode = successor;
}
int index = index(deleteNode.hash);
Node<K,V> replaceNode = deleteNode.left != null ? deleteNode.left : deleteNode.right;
if (replaceNode != null) {
replaceNode.parent = deleteNode.parent;
if (deleteNode.parent == null) {
table[index] = replaceNode;
} else if (deleteNode.isLeftChild()) {
deleteNode.parent.left = replaceNode;
} else {
deleteNode.parent.right = replaceNode;
}
////删除节点后的操作
//afterRemove(deleteNode,replaceNode);
//删除节点后的操作
afterRemove(replaceNode);
} else if (deleteNode.parent == null) {
table[index] = null;
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
} else {
if (deleteNode.isLeftChild()) {
deleteNode.parent.left = null;
} else {
deleteNode.parent.right = null;
}
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
}
//if (deleteNode.hasTwoChildren()) {
// //获取前驱节点、后继节点
// Node<K,V> successor = successor(deleteNode);
// //替换节点值为后继节点值
// deleteNode.key = successor.key;
// //替换节点值为后继节点值
// deleteNode.key = successor.key;
// //替换值
// parent = successor.parent;
// deleteNode = successor;
//}
////删除结点
//changeNode(parent,deleteNode);
//afterRemove(deleteNode);
return deleteNode.value;
}
/**
* 扩容
* @author lcy
* @date 2021/1/21 16:09
**/
private void resize(){
if (Float.intBitsToFloat(size) / Float.intBitsToFloat(table.length) <= DEFAULT_LOAD_FACTORY) {
return;
}
//扩容
Node<K,V>[] newTable = Arrays.copyOf(table,table.length >>1);
}
/**
* 查找当前节点的后继节点（中序遍历的后一个节点）
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.RedBlackNode<K,V>
* @author lcy
* @date 2020/10/19 17:43
**/
private Node<K,V> successor(Node<K,V> node){
//当前节点
Node<K,V> tmpNode = table[index(node.hash)];
Node<K,V> prev = null;
Stack<Node<K,V>> stack = new Stack<>();
//当节点不为空时
while (tmpNode != null || !stack.isEmpty()) {
//左子树入栈
while (tmpNode != null) {
stack.push(tmpNode);
tmpNode = tmpNode.left;
}
//出栈
tmpNode = stack.pop();
if (prev == node) {
return tmpNode;
}
prev = tmpNode;
if (tmpNode.right != null) {
tmpNode = tmpNode.right;
} else {
tmpNode = null;
}
}
return null;
}
/**
* 根据key生成对应的hash
* @param key key
* @return int
* @author lcy
* @date 2021/1/12 9:50
**/
private int hash(K key){
if (key == null) {
return 0;
} else {
int hash = key.hashCode();
//int类型为32位，无符号右移16位异或上原来的值，即高低位都进行计算，保证hash函数的分布均匀
return hash ^ (hash >>> 16);
}
}
/**
* 根据key生成对应的hash
* @param key key
* @return int
* @author lcy
* @date 2021/1/12 9:50
**/
private int hashAgain(K key){
if (key == null) {
return 0;
} else {
int hash = key.hashCode();
return 5 * hash % 5;
}
}
/**
* 根据key生成对应的数组下标
* @param key key
* @return int
* @author lcy
* @date 2021/1/12 9:50
**/
private int index(K key){
return hash(key) & (table.length - 1);
}
/**
* 根据hash值生成对应的数组下标
* @param hash hash
* @return int
* @author lcy
* @date 2021/1/12 9:50
**/
private int index(int hash){
return hash & (table.length - 1);
}
/**
* 节点染色
* @param node 传入节点值
* @param color 颜色
* @return com.lcy.study.algoithm.tree.set.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeColor(Node<K,V> node,boolean color){
if (node == null) {
return null;
}
//节点染色
node.color = color;
return node;
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeRed(Node<K,V> node){
return changeColor(node,RED);
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeBlack(Node<K,V> node){
return changeColor(node,BLACK);
}
/**
* 获取当前节点的颜色
* @param node 节点对象
* @return boolean
* @author lcy
* @date 2020/11/25 14:09
**/
private boolean colorOf(Node<K,V> node){
return node != null ? node.color : BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isBlack(Node<K,V> node){
return colorOf(node) == BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isRed(Node<K,V> node){
return colorOf(node) == RED;
}
/**
* 比较key
* @param key1 key1
* @param key2 key2
* @param hash1 key1的hash1
* @param hash2 key2的hash2
* @return int
* @author lcy
* @date 2021/1/12 10:11
**/
private int compare(K key1,K key2,int hash1,int hash2){
int cmp = hash1 - hash2;
//说明hashcode不相等，返回差值
if (cmp != 0) {
return cmp;
}
//hashCode相等，值也相等,包含两个值都为null的情况
if (Tools.equals(key1,key2)) {
return 0;
}
System.out.println(key1 + ":" + key2 + ":" + hash1 + ":" + hash2);
//值不相等，进一步判断
if (key1 != null && key2 != null) {
String key1Class = key1.getClass().getName();
String key2Class = key2.getClass().getName();
//通过compareTo方法计算两个类名的差值
cmp = key1Class.compareTo(key2Class);
//类名不相等说明不是同一个对象，返回差值
if (cmp != 0) {
return cmp;
}
//如果类相等，且继承了比较器，使用比较器的比较方法
if (key1 instanceof Comparable) {
return ((Comparable)key1).compareTo(key2);
}
}
//key1和key2可能有一个为null。比较内存地址的hash值
return 0;
}
/**
* 根据对象获取节点值
* @param key 需要查找的对象
* @return com.lcy.study.algoithm.tree.set.RedBlackNode<K,V>
* @author lcy
* @date 2020/11/12 16:18
**/
public Node<K,V> node(K key){
//获取hash桶里的值
Node<K,V> node = table[index(key)];
return node == null ? null : node(node,key);
}
/**
* 根据对象获取节点值
* @param node 需要查找的节点
* @param key 需要查找的对象
* @return com.lcy.study.algoithm.tree.set.RedBlackNode<K,V>
* @author lcy
* @date 2020/11/12 16:18
**/
public Node<K,V> node(Node<K,V> node,K key){
int hash = hash(key);
Stack<Node<K,V>> stack = new Stack<>();
if (node != null) {
stack.push(node);
}
int cmp;
while (!stack.isEmpty()) {
node = stack.pop();
if (hash > node.hash) {
stack.push(node.right);
//node = node.right;
} else if (hash < node.hash) {
stack.push(node.left);
//node = node.left;
//equals相等
} else if (Tools.equals(key,node.key)) {
return node;
//值不相等，进一步判断
} else if (key != null && node.key != null &&
key.getClass() == node.key.getClass() && key instanceof Comparable
&& (cmp = ((Comparable)key).compareTo(node.key)) != 0) {
stack.push(cmp > 0 ? node.right : node.left);
//hash相等，不具备可比较性
} else {
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
}
return null;
}
protected void afterAdd(Node<K,V> node){
Stack<Node<K,V>> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
Node<K,V> parent = node.parent;
//如果是根节点
if (parent == null) {
//变成黑色
changeBlack(node);
continue;
}
//如果父节点是黑色--维持红黑树平衡，不需要操作
if (isBlack(parent)) {
continue;
}
//获取uncle节点--叔父节点
Node<K,V> uncle = parent.sibling();
//祖父节点--祖父节点一定染成红色
Node<K,V> grandParent = changeRed(parent.parent);
//叔父节点是红色
if (isRed(uncle)) {
//父节点和叔父节点染成黑色
changeBlack(parent);
changeBlack(uncle);
//将祖父节点当成新添加的节点处理
stack.push(grandParent);
continue;
}
if (parent.isLeftChild()) {
if (node.isLeftChild()) {
//LL--父节点染成黑色，祖父节点染成红色
changeBlack(parent);
} else {
//LR--当前节点和祖父节点染成黑色，父节点染成红色
//父节点左旋转，祖父节点右旋转
changeBlack(node);
rotateLeft(parent);
}
rotateRight(grandParent);
} else {
if (node.isLeftChild()) {
//RL--当前节点和祖父节点染成黑色，父节点染成红色
//父节点右旋转，祖父节点左旋转
changeBlack(node);
rotateRight(parent);
} else {
//RR--父节点染成黑色，祖父节点染成黑色,左旋转
changeBlack(parent);
}
rotateLeft(grandParent);
}
}
}
protected void afterRemove(Node<K,V> node){
Stack<Node<K,V>> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
//二叉搜索树删除以后的操作，如果删除的节点是度为2的节点，即有两个子节点，node为该节点的后继节点。
node = stack.pop();
//如果替换的节点是红色
//如果是删除的节点是红色节点，直接删除。如果是用于取代删除节点的子节点是红色，进行染色。然后直接返回。
if (isRed(node)) {
//改成黑色，保持4阶B树和红黑树性质，根节点一定要有黑色，因为删除了黑色节点，必须重新生成一个黑色。
changeBlack(node);
continue;
}
Node<K,V> parent = node.parent;
//如果黑色节点是根节点--不需要处理
if (parent == null) {
continue;
}
//兄弟节点--如果是叶子节点，parent已经不指向node了。即原本指向node节点的指针已经为null。
//但是如果是下溢的情况，parent递归调用，因为parent的父节点还是它，所以要再增加一个不为空的情况判断。
boolean left = parent.left == null || node.isLeftChild();
//如果node节点是左子节点，取右子节点
Node<K,V> siblingNode = left ? parent.right : parent.left;
//如果被删除的子节点在左边
if (left) {
//如果被删除的子节点在左边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateLeft(parent);
//兄弟节点改变
siblingNode = parent.right;
}
} else {
//如果被删除的子节点在右边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateRight(parent);
//兄弟节点改变
siblingNode = parent.left;
}
}
//兄弟节点是黑色,一定是黑色
//如果兄弟节点的子节点都是黑色
if (isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
//如果都不为黑色，说明没有子节点。因为没有子节点，父节点要向下合并。即染色
boolean isParentBlack = isBlack(parent);
changeBlack(parent);
changeRed(siblingNode);
//如果父节点是黑色，说明上面的节点还存在下溢
if (isParentBlack) {
//相当于二叉搜索树的叶子节点
stack.push(parent);
}
} else {
if (left) {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.right)) {
rotateRight(siblingNode);
siblingNode = parent.right;
}
//对父节点进行右旋转
rotateLeft(parent);
} else {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.left)) {
rotateLeft(siblingNode);
siblingNode = parent.left;
}
//对父节点进行右旋转
rotateRight(parent);
}
//旋转以后中心节点的颜色为parent的颜色，新的子节点颜色为黑色
changeColor(siblingNode,colorOf(parent));
changeBlack(siblingNode.left);
changeBlack(siblingNode.right);
}
}
}
/**
* 左旋转
* @param node 需要旋转的节点
* @author lcy
* @date 2020/11/18 16:21
**/
protected void rotateLeft(Node<K,V> node){
//左旋转node节点的右节点--parentNode
Node<K,V> parentNode = node.right;
//需要node节点的右子树改为当前parentNode的左子树
node.right = parentNode.left;
//父节点值替换
if (node.right != null) {
node.right.parent = node;
}
//parent节点的左节点为node节点
parentNode.left = node;
//父节点替换
parentNode.parent = node.parent;
//node节点的父节点指向--旋转以后子树根节点变换
if (node.isLeftChild()) {
parentNode.parent.left = parentNode;
} else if (node.isRightChild()) {
parentNode.parent.right = parentNode;
} else {
//如果是根节点,取随便一个节点的hash值然后计算下标。因为红黑树里的key的下标都是一致
table[index(parentNode.hash)] = parentNode;
}
node.parent = parentNode;
}
/**
* 右旋转
* @param node 需要旋转的节点
* @author lcy
* @date 2020/11/18 16:21
**/
protected void rotateRight(Node<K,V> node){
//左旋转node节点的右节点--parentNode
Node<K,V> parentNode = node.left;
//需要node节点的右子树改为当前parentNode的左子树
node.left = parentNode.right;
//父节点值替换
if (node.left != null) {
node.left.parent = node;
}
//parent节点的左节点为node节点
parentNode.right = node;
//父节点替换
parentNode.parent = node.parent;
//node节点的父节点指向--旋转以后子树根节点变换
if (node.isLeftChild()) {
parentNode.parent.left = parentNode;
} else if (node.isRightChild()) {
parentNode.parent.right = parentNode;
} else {
//如果是根节点,取随便一个节点的hash值然后计算下标。因为红黑树里的key的下标都是一致
table[index(parentNode.hash)] = parentNode;
}
node.parent = parentNode;
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class Node<K,V> {
/**
* key的hash值
*/
int hash;
/**
* 当前节点key--比较值
*/
K key;
/**
* 当前节点value
*/
V value;
/**
* 左节点值
*/
Node<K,V> left;
/**
* 右节点值
*/
Node<K,V> right;
/**
* 父节点值
*/
Node<K,V> parent;
/**
* 节点颜色，红色为true，黑色为false。新添加的默认为红色节点
*/
boolean color = RED;
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;
}
/**
* 判断是否有左右子树
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean hasTwoChildren(){
return left != null && right != null;
}
/**
* 判断是否左子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isLeftChild(){
return parent != null && parent.left == this;
}
/**
* 判断是否右子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isRightChild(){
return parent != null && parent.right == this;
}
/**
* 返回兄弟节点
* @return Node<K,V>
* @author lcy
* @date 2020/11/18 15:23
**/
public Node<K,V> sibling(){
//如果是左子节点，返回父节点的右子节点
if (isLeftChild()) {
return parent.right;
}
//如果是右子节点，返回父节点的左子节点
if (isRightChild()) {
return parent.left;
}
//如果是根节点，返回null
return null;
}
@Override public String toString(){
return "(" + (color ? "red" : "black") + ")" + key
//+ ",value={" + value + "}"
;
}
}
}六、总结
哈希散列是一种强大的数据结构和算法，它提供了高效的数据存储和检索机制，并且可以保证数据的完整性和安全性。通过合适的哈希函数和冲突解决方法，我们可以在大规模数据处理中获得出色的性能。然而，设计一个好的哈希函数并不是一件容易的事情，需要考虑到多方面的因素，如输入数据的特点、哈希空间的大小等。因此，在实际应用中，我们需要综合考虑各种因素，选择合适的哈希函数和冲突解决方法，以满足特定场景的需求。