image.png
方法一：暴力解法
class MyHashMap {
int [] arr = new int[10000000];
/** Initialize your data structure here. */
//用空映射初始化对象
public MyHashMap() {
for(int i = 0; i<arr.length;i++){
arr[i] = -1;
}
}
/** value will always be non-negative. */
//向HashMap插入一个键值对
public void put(int key, int value) {
arr[key] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
//返回特定的key所映射的value；如果映射不包含key的映射，返回-1
public int get(int key) {
return arr[key];
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
//如果映射中存在key的映射，则移除key和它所对应的value
public void remove(int key) {
arr[key] = -1;
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
方法二：哈希源码（不加红黑树）
class MyHashMap {
Node[] hashArray;
int size = 0;
int used = 0;
double factor = 0.75;//最多当前使用占用比例
/** Initialize your data structure here. */
public MyHashMap() {
hashArray = new Node[(1<<4)];
size = hashArray.length;
}
/** value will always be non-negative. */
public void put(int key, int value) {
//假设哈希效果不佳就rehash
//加一个如果添加元素数量，超过当前数组大小的75%，则进行扩展
if(size*0.75<used+1){
expand();
}
int index = getIndex(key);//获取哈希出的索引值
//当前位置没有元素，则直接添加成为头结点
if(hashArray[index]==null){
hashArray[index] = new Node(key,value);
++used;
}else{
//哈希重复则进行查找
Node curr = hashArray[index];
//看看先到达尾部还是先找到key
while (curr.next!=null && curr.key!=key){
curr = curr.next;
}
//先找到key就赋值，先到达尾部就追加节点
if(curr.key == key){
curr.value = value;
}else{
curr.next = new Node(key,value);
++used;
}
}
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
//找不到就-1
int index = getIndex(key);
if(hashArray[index]==null){
return -1;
}
//找到链表就遍历一次
Node curr = hashArray[index];
while(curr!=null && curr.key!=key){
curr = curr.next;
}
return curr==null?-1:curr.value;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
int index = getIndex(key);
//不存在就不用找了
if(hashArray[index]==null)
return;
//存在且是头结点直接指向一个节点
if(hashArray[index].key == key){
hashArray[index] = hashArray[index].next;
--used;
return;
}
//遍历链表，查下一项是不是
Node curr = hashArray[index];
while(curr.next!=null && curr.next.key!=key){
curr = curr.next;
}
//如果找到，那就没到尾部用前驱指向后继
if(curr.next!=null){
curr.next = curr.next.next;
--used;
}
}
private void expand(){
//扩展为原来的两倍
int newSize = size << 1;
Node[] newArr = new Node[newSize];
for(int i = 0; i < size; i++){
if(hashArray[i]==null)
continue;
//分高低位
Node lowHead = new Node(0,0);
Node highHead = new Node(0,0);
Node low = lowHead;
Node high = highHead;
Node curr = hashArray[i];
while(curr!=null){
//索引不变指向低位（自己试下就知道了）
if(i == getSizeIndex(curr.key,newSize)){
low.next = curr;
curr = curr.next;
low = low.next;
low.next = null;
}else{
//索引变指向高位size+i（自己试下就知道了）
high.next = curr;
curr = curr.next;
high = high.next;
high.next = null;
}
}
//高低位分别赋值
newArr[size+i] = highHead.next;
newArr[i] = lowHead.next;
}
//修改数组和总长
hashArray = newArr;
size = newSize;
}
private int getSizeIndex(int key, int size){
//因为x&(n-1)的范围在0到n-1，所以不会溢出
//但是如果数字较大，哈希总长较小的情况下，高位无法对哈希值产生影响，因此采用高16位右移的方式，增加高位对哈希结果影响
//也就是扰动函数
return (key^(key>>16))&(size-1);
}
private int getIndex(int key){
//因为x&(n-1)的范围在0到n-1，所以不会溢出
//但是如果数字较大，哈希总长较小的情况下，高位无法对哈希值产生影响，因此采用高16位右移的方式，增加高位对哈希结果影响
//也就是扰动函数
return (key^(key>>16))&(size-1);
}
class Node{
int key;
int value;
Node next;
public Node(int key, int value){
this.key = key;
this.value = value;
}
@Override
public String toString() {
String str = "["+key+","+value+"]";
if(next!=null)
str +=","+next.toString();
return str;
}
}
@Override
public String toString() {
return Arrays.deepToString(hashArray);
}
}
方法三：分离链接+红黑树
class MyHashMap {
private static class TreeNode {
private int key;
private int value;
private boolean color;
private TreeNode left;
private TreeNode right;
private TreeNode parent;
private TreeNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private static final boolean RED = false;
private static final boolean BLACK = true;
private TreeNode[] hashtable = new TreeNode[1024];
private int currentSize;
public void put(int key, int value) {
if (currentSize >= hashtable.length) {
resize(); // 从结果来看，加载因子选 1.0 效率较高。
}
int index = key & (hashtable.length - 1);
insert(index, new TreeNode(key, value));
}
public int get(int key) {
int index = key & (hashtable.length - 1);
TreeNode node = getNode(index, key);
return node == null ? -1 : node.value;
}
public void remove(int key) {
int index = key & (hashtable.length - 1);
delete(index, key);
}
// 对哈希表进行扩容。
private void resize() {
TreeNode[] oldTable = hashtable;
hashtable = new TreeNode[hashtable.length << 1];
for (TreeNode root : oldTable) {
postorderTraversal(root);
}
currentSize >>= 1;
}
// 获取指定位置上的指定结点。
private TreeNode getNode(int index, int key) {
TreeNode current = hashtable[index];
while (current != null) {
if (current.key == key) {
break;
}
if (current.key < key) {
current = current.right;
} else {
current = current.left;
}
}
return current;
}
// 在指定位置上插入结点。
private void insert(int index, TreeNode insert) {
TreeNode current = hashtable[index], parent = null; // 分别保存当前结点及其父结点。
while (current != null) {
parent = current;
if (current.key == insert.key) {
current.value = insert.value;
return;
}
if (current.key < insert.key) {
current = current.right;
} else {
current = current.left;
}
}
insert.parent = parent;
if (parent == null) {
hashtable[index] = insert;
} else if (parent.key < insert.key) {
parent.right = insert;
} else {
parent.left = insert;
}
currentSize++;
fixAfterInsertion(index, insert);
}
// 删除指定位置上的指定结点。
private void delete(int index, int key) {
TreeNode delete = getNode(index, key);
if (delete == null) {
return;
}
if (delete.left != null && delete.right != null) {
TreeNode successor = delete.right;
while (successor.left != null) {
successor = successor.left;
}
delete.key = successor.key;
delete.value = successor.value;
delete = successor;
}
TreeNode replacement = delete.left == null ? delete.right : delete.left;
if (replacement == null) {
fixAfterDeletion(index, delete);
if (delete.parent == null) {
hashtable[index] = null;
} else if (delete.parent.left == delete) {
delete.parent.left = null;
} else {
delete.parent.right = null;
}
} else { // 被删除的结点只有一个子结点，那它一定是黑色结点，且它的子结点为红色。
replacement.parent = delete.parent;
if (delete.parent == null) {
hashtable[index] = replacement;
} else if (delete.parent.left == delete) {
delete.parent.left = replacement;
} else {
delete.parent.right = replacement;
}
replacement.color = BLACK;
}
currentSize--;
}
// 对插入后的结点进行调整。
private void fixAfterInsertion(int index, TreeNode insert) {
while (colorOf(insert.parent) == RED) { // 只有父结点是红色才进行处理。
// 分别保存当前结点的父结点、叔父结点、祖父结点。
TreeNode parent = insert.parent, uncle = sibling(parent), grand = parent.parent;
grand.color = RED; // 不管是哪种情况，祖父结点都需要染成红色。
if (colorOf(uncle) == BLACK) { // 叔父结点为黑色。
if (grand.left == parent) {
if (parent.right == insert) {
rotationLeft(index, parent); // LR 情况：先对父结点进行左旋转。
parent = insert;
}
rotationRight(index, grand); // LL 情况：对祖父结点进行右旋转。
} else {
if (parent.left == insert) {
rotationRight(index, parent); // RL 情况：先对父结点进行右旋转。
parent = insert;
}
rotationLeft(index, grand); // RR 情况：对祖父结点进行左旋转。
}
parent.color = BLACK; // 将旋转后的中心结点染成黑色。
insert = hashtable[index]; // 处理完直接退出循环。
} else { // 叔父结点为红色，则将父结点与叔父结点都染成黑色，将祖父结点作为新插入的结点继续处理。
uncle.color = BLACK;
parent.color = BLACK;
insert = grand;
}
}
hashtable[index].color = BLACK; // 根结点必须是黑色。
}
// 对删除后的结点进行调整。
private void fixAfterDeletion(int index, TreeNode delete) {
while (delete.parent != null && delete.color == BLACK) { // 只有删除的是黑色结点才进行处理。
// 分别保存当前结点的父结点、兄弟结点。
TreeNode parent = delete.parent, sibling = sibling(delete);
if (sibling.color == BLACK) { // 兄弟结点是黑色。
if (colorOf(sibling.left) == BLACK && colorOf(sibling.right) == BLACK) { // 兄弟结点没有红色子结点。
if (parent.color == BLACK) {
delete = parent;
}
parent.color = BLACK;
sibling.color = RED;
} else { // 兄弟结点有红色子结点。
if (parent.left == sibling) {
if (colorOf(sibling.left) == BLACK) {
rotationLeft(index, sibling); // LR 情况：先对兄弟结点进行左旋转。
sibling = sibling.parent;
}
rotationRight(index, parent); // LL 情况：对父结点进行右旋转。
} else {
if (colorOf(sibling.right) == BLACK) {
rotationRight(index, sibling); // RL 情况：先对兄弟结点进行右旋转。
sibling = sibling.parent;
}
rotationLeft(index, parent); // RR 情况：对父结点进行左旋转。
}
sibling.color = parent.color; // 旋转后中心结点继承父结点的颜色。
sibling.left.color = BLACK;
sibling.right.color = BLACK;
delete = hashtable[index]; // 处理完直接退出循环。
}
} else { // 兄弟结点是红色。
if (parent.left == sibling) {
rotationRight(index, parent);
} else {
rotationLeft(index, parent);
}
parent.color = RED;
sibling.color = BLACK;
}
}
}
// 获取指定结点的兄弟结点。
private TreeNode sibling(TreeNode node) {
if (node.parent.left == node) {
return node.parent.right;
}
return node.parent.left;
}
// 对指定位置上的指定结点进行左旋转。
private void rotationLeft(int index, TreeNode node) {
TreeNode newRoot = node.right; // 结点的右子结点会成为这颗子树的根结点。
node.right = newRoot.left;
if (newRoot.left != null) {
newRoot.left.parent = node;
}
newRoot.left = node;
newRoot.parent = node.parent;
if (node.parent == null) {
hashtable[index] = newRoot;
} else if (node.parent.left == node) {
node.parent.left = newRoot;
} else {
node.parent.right = newRoot;
}
node.parent = newRoot;
}
// 对指定位置上的指定结点进行右旋转。
private void rotationRight(int index, TreeNode node) {
TreeNode newRoot = node.left; // 结点的左子结点会成为这颗子树的根结点。
node.left = newRoot.right;
if (newRoot.right != null) {
newRoot.right.parent = node;
}
newRoot.right = node;
newRoot.parent = node.parent;
if (node.parent == null) {
hashtable[index] = newRoot;
} else if (node.parent.left == node) {
node.parent.left = newRoot;
} else {
node.parent.right = newRoot;
}
node.parent = newRoot;
}
// 获取指定结点的颜色。
private boolean colorOf(TreeNode node) {
return node == null || node.color;
}
// 对结点进行后序遍历。
private void postorderTraversal(TreeNode node) {
if (node == null) {
return;
}
postorderTraversal(node.left);
postorderTraversal(node.right);
node.left = node.right = node.parent = null;
node.color = RED;
int index = node.key & (hashtable.length - 1);
insert(index, node);
}
}
