Java之HashMap的底层实现
- 摘要
- HashMap的底层原理
- 哈希值转换为数组下标
- 节点
- 初始化
- put(Object key, Object value)
- 重写toString()
- get(Object key)
- 增加泛化
- remove(K key)
摘要
本博客主要讲述了Java的HashMap的底层实现
HashMap的底层原理
底层原理:数组+链表
过程总结:每一个Object的有一个哈希值,通过hashCode()函数获取哈希值,再通过自定义的hash()函数,得到一个值,也就是数组的下标。数组中的每个元素都是一个链表或为空。
哈希值转换为数组下标
//这就是hash函数,val就是key的哈希值,即val = key.hashCode()
//length 必须是2的整数幂
private int hash(int val, int length){return val & (length - 1);}
节点
定义链表中的节点
public class Node2 {int hash;//hash对应数组下标Object key;Object value;Node2 next;
}
初始化
//数组元素的类型为Node2
Node2[] table;
int size;public SxtHashMap02() {table = new Node2[16];
}
put(Object key, Object value)
public void put(Object key, Object value){Node2 newNode = new Node2();newNode.hash = hash(key.hashCode(),table.length);newNode.key = key;newNode.value = value;newNode.next = null;Node2 last = null;//这个学习一下,记录最后一个节点int index = hash(key.hashCode(),table.length);if(table[index] == null){table[index] = newNode;size ++;}else{Node2 tmp = table[index];while(tmp != null){if(key.equals(tmp.key)){System.out.println("key重复了");tmp.value = value;return;}else {last = tmp;tmp = tmp.next;}}last.next = newNode;size ++;//size的增加与减少不要忘记}}
重写toString()
public String toString() {StringBuilder sb = new StringBuilder();sb.append("[");for(int i = 0; i < table.length; i ++){Node2 temp = table[i];while(temp != null){sb.append(temp.key + ":" + temp.value + ",");temp = temp.next;}}//这个套路学一下,将最后改为']'sb.setCharAt(sb.length() - 1,']');return sb.toString();
}
这个toString()有什么用呢?在使用system.out.println()打印的时候,就会用到toString()。
get(Object key)
//根据Map的底层原理,就十分简单
public Object get(Object key){int hashCode = key.hashCode();int hash = hash(hashCode,table.length);Node2 temp = table[hash];while(temp != null){if(temp.key.equals(key)) return temp.value;temp = temp.next;}return null;
}
增加泛化
public class Node3<K,V> {int hash;K key;V value;Node3 next;
}public class SxtHashMap03<K,V> {Node3[] table;int size;public SxtHashMap03() {table = new Node3[16];}public V get(K key){int hashCode = key.hashCode();int hash = hash(hashCode,table.length);V value = null;Node3 temp = table[hash];while(temp != null){if(temp.key.equals(key)){value = (V)temp.value;}temp = temp.next;}return value;}public void put(K key, V value){Node3 newNode = new Node3();newNode.hash = hash(key.hashCode(),table.length);newNode.key = key;newNode.value = value;newNode.next = null;Node3 last = null;int index = hash(key.hashCode(),table.length);if(table[index] == null){table[index] = newNode;size ++;}else{Node3 tmp = table[index];while(tmp != null){if(key.equals(tmp.key)){System.out.println("key重复了");tmp.value = value;return;}else {last = tmp;tmp = tmp.next;}}last.next = newNode;size ++;}}
}
remove(K key)
public void remove(K key){int index = hash(key.hashCode(), table.length);Node3 temp = table[index];if(temp == null) return;if(temp.key.equals(key)){table[index] = temp.next;size --;return;}Node3 last = null;while(temp != null){if(temp.key.equals(key)){last.next = temp.next;size --;return;}last = temp;temp = temp.next;}
}
参考: 手工实现HashMap