HashMap实现细节,hash对key为 null的处理,对重哈希的处理
ConcurrentHashMap:https://www.cnblogs.com/200911/p/5800493.html
LinkedHashMap:https://blog.csdn.net/justloveyou_/article/details/71713781
一、解HashMap源码解读
1、HashMap的存储结构
2、HashMap的初始化
3、元素Hash值获取及通过hash值找到talbe下标索引
4、元素添加方法addEntry
5、HashMap扩容
6、老table重新hash成新table
7、key为null,存到哪去了
8、查找元素get(Object key)
9、根据key删除元素
1、HashMap的存储结构
在HashMap的Field中有:
- transient Entry[] table;
而Entry的定义如下:
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- .........
- }
简单说就是一个数组+链表,结构如下图:
2、HashMap的初始化
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
- table = new Entry[DEFAULT_INITIAL_CAPACITY];
- init();
- }
构造方法中出现的几个关键字段:loadFactor ,threshold,CAPACITY,table
其中table上面讲了,是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量,这里使用了系统默认的初始容量,loadFactor 是加载因子,用处是和CAPACITY相乘获得threshold,这个文档的说明如下:The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值,超过这个值,则重新扩容。
这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候,首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证,每一个元素对应不同的talbe数组的索引值,当放入HashMap的元素过多的时候,就容易出现相同的索引值,在算法里叫冲突,这时候元素就会被加到该索引值下的链表当中,这样查找的效率就会大大降低,这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候,就是用了这样一个加载因子,如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候,冲突加剧,这样我们就得扩容解决这样的问题。
所以总结影响HashMap效率的两个因素:1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。
3、元素Hash值获取及通过hash值找到talbe下标索引
- static int hash(int h) {
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
这个不深究,结果是获得一个随机点的hash值
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度
4、元素添加方法addEntry
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- if (size++ >= threshold)
- resize(2 * table.length);
- }
- //Entry的构造方法
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。
说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图:
5、HashMap扩容
- void resize(int newCapacity) {
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- Entry[] newTable = new Entry[newCapacity];
- transfer(newTable);
- table = newTable;
- threshold = (int)(newCapacity * loadFactor);
- }
在元素添加方法addEntry中,添加完元素后,有下面两行代码:
- if (size++ >= threshold)
- resize(2 * table.length);
size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。
6、老table重新hash成新table
- void transfer(Entry[] newTable) {
- Entry[] src = table;
- int newCapacity = newTable.length;
- for (int j = 0; j < src.length; j++) {
- Entry<K,V> e = src[j];
- if (e != null) {
- src[j] = null;
- do {
- Entry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i];
- newTable[i] = e;
- e = next;
- } while (e != null);
- }
- }
- }
这个方法的主要作用就是,将老的table中的所有不为空的元素,重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以,如果不为空,还要遍历这个链表中的每一个元素,并将这些元素重新hash到新table中。下面我们对于代码讲解。
//将第一个元素e后的链表截取出来
Entry<K,V> next = e.next;
//找到e对应新table的下标索引
int i = indexFor(e.hash, newCapacity);
//将e插入到新table下标索引链表的表头
e.next = newTable[i];
//将该新table下标索引重新定位为e,这样就完成了一个元素的重新hash
newTable[i] = e;
//将截取的剩余的链表继续hash
e = next;
示意图如下:
1、Entry<K,V> next = e.next;
2、e.next = newTable[i];
即这里的e就是Entry[j],也就是
3、newTable[i] = e;
因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用,这个时候,我们在将这个引用指向红色Entry[j],这样就完成了老table中一个元素的重新hash到新table中。
7、key为null,存到哪去了
在put方法里头,其实第一行就处理了key=null的情况。
- if (key == null)
- return putForNullKey(value);
- //那就看看这个putForNullKey是怎么处理的吧。
- private V putForNullKey(V value) {
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- addEntry(0, null, value, 0);
- return null;
- }
可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。
8、查找元素get(Object key)
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- int hash = hash(key.hashCode());
- for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。
- public V remove(Object key) {
- Entry<K,V> e = removeEntryForKey(key);
- return (e == null ? null : e.value);
- }
- 调用的还是下面的方法
- final Entry<K,V> removeEntryForKey(Object key) {
- int hash = (key == null) ? 0 : hash(key.hashCode());
- int i = indexFor(hash, table.length);
- Entry<K,V> prev = table[i];
- Entry<K,V> e = prev;
- while (e != null) {
- Entry<K,V> next = e.next;
- Object k;
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) {
- modCount++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
- return e;
- }
这里while循环外面的很好看懂,我们讨论while循环里的。
Entry<K,V> next = e.next;把原有的链表截出表头元素,然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话,我们直接将这个链表的第一个元素删除就OK。
if (prev == e)
table[i] = next;
如果不是,则遍历这个链表,下图展示了这个过程:
步骤1、初始情况
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
步骤2、没找到
Entry<K,V> next = e.next;
……..
prev = e;
e = next;
如果e这个元素不是要删除的话,则遍历下一个元素。
步骤3、找到
prev.next = next;
return e;
将prev的下一个元素指向e.next。这样就相当于删除了e
最后的结果如下:
二.解决hash冲突的办法
- 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
- 再哈希法
- 链地址法
- 建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。
三.实现自己的HashMap
Entry.java
MyHashMap.java
MyHashMapTest.java
- package edu.sjtu.erplab.hash;
- public class MyHashMapTest {
- public static void main(String[] args) {
- MyHashMap<Integer, Integer> map = new MyHashMap<Integer, Integer>();
- map.put(1, 90);
- map.put(2, 95);
- map.put(17, 85);
- System.out.println(map.get(1));
- System.out.println(map.get(2));
- System.out.println(map.get(17));
- System.out.println(map.get(null));
- }
- }
1、HashMap的存储结构
2、HashMap的初始化
3、元素Hash值获取及通过hash值找到talbe下标索引
4、元素添加方法addEntry
5、HashMap扩容
6、老table重新hash成新table
7、key为null,存到哪去了
8、查找元素get(Object key)
9、根据key删除元素
1、HashMap的存储结构
在HashMap的Field中有:
- transient Entry[] table;
而Entry的定义如下:
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- .........
- }
简单说就是一个数组+链表,结构如下图:
2、HashMap的初始化
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
- table = new Entry[DEFAULT_INITIAL_CAPACITY];
- init();
- }
构造方法中出现的几个关键字段:loadFactor ,threshold,CAPACITY,table
其中table上面讲了,是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量,这里使用了系统默认的初始容量,loadFactor 是加载因子,用处是和CAPACITY相乘获得threshold,这个文档的说明如下:The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值,超过这个值,则重新扩容。
这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候,首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证,每一个元素对应不同的talbe数组的索引值,当放入HashMap的元素过多的时候,就容易出现相同的索引值,在算法里叫冲突,这时候元素就会被加到该索引值下的链表当中,这样查找的效率就会大大降低,这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候,就是用了这样一个加载因子,如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候,冲突加剧,这样我们就得扩容解决这样的问题。
所以总结影响HashMap效率的两个因素:1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。
3、元素Hash值获取及通过hash值找到talbe下标索引
- static int hash(int h) {
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
这个不深究,结果是获得一个随机点的hash值
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度
4、元素添加方法addEntry
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- if (size++ >= threshold)
- resize(2 * table.length);
- }
- //Entry的构造方法
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。
说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图:
5、HashMap扩容
- void resize(int newCapacity) {
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- Entry[] newTable = new Entry[newCapacity];
- transfer(newTable);
- table = newTable;
- threshold = (int)(newCapacity * loadFactor);
- }
在元素添加方法addEntry中,添加完元素后,有下面两行代码:
- if (size++ >= threshold)
- resize(2 * table.length);
size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。
6、老table重新hash成新table
- void transfer(Entry[] newTable) {
- Entry[] src = table;
- int newCapacity = newTable.length;
- for (int j = 0; j < src.length; j++) {
- Entry<K,V> e = src[j];
- if (e != null) {
- src[j] = null;
- do {
- Entry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i];
- newTable[i] = e;
- e = next;
- } while (e != null);
- }
- }
- }
这个方法的主要作用就是,将老的table中的所有不为空的元素,重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以,如果不为空,还要遍历这个链表中的每一个元素,并将这些元素重新hash到新table中。下面我们对于代码讲解。
//将第一个元素e后的链表截取出来
Entry<K,V> next = e.next;
//找到e对应新table的下标索引
int i = indexFor(e.hash, newCapacity);
//将e插入到新table下标索引链表的表头
e.next = newTable[i];
//将该新table下标索引重新定位为e,这样就完成了一个元素的重新hash
newTable[i] = e;
//将截取的剩余的链表继续hash
e = next;
示意图如下:
1、Entry<K,V> next = e.next;
2、e.next = newTable[i];
即这里的e就是Entry[j],也就是
3、newTable[i] = e;
因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用,这个时候,我们在将这个引用指向红色Entry[j],这样就完成了老table中一个元素的重新hash到新table中。
7、key为null,存到哪去了
在put方法里头,其实第一行就处理了key=null的情况。
- if (key == null)
- return putForNullKey(value);
- //那就看看这个putForNullKey是怎么处理的吧。
- private V putForNullKey(V value) {
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- addEntry(0, null, value, 0);
- return null;
- }
可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。
8、查找元素get(Object key)
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- int hash = hash(key.hashCode());
- for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。
- public V remove(Object key) {
- Entry<K,V> e = removeEntryForKey(key);
- return (e == null ? null : e.value);
- }
- 调用的还是下面的方法
- final Entry<K,V> removeEntryForKey(Object key) {
- int hash = (key == null) ? 0 : hash(key.hashCode());
- int i = indexFor(hash, table.length);
- Entry<K,V> prev = table[i];
- Entry<K,V> e = prev;
- while (e != null) {
- Entry<K,V> next = e.next;
- Object k;
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) {
- modCount++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
- return e;
- }
这里while循环外面的很好看懂,我们讨论while循环里的。
Entry<K,V> next = e.next;把原有的链表截出表头元素,然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话,我们直接将这个链表的第一个元素删除就OK。
if (prev == e)
table[i] = next;
如果不是,则遍历这个链表,下图展示了这个过程:
步骤1、初始情况
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
步骤2、没找到
Entry<K,V> next = e.next;
……..
prev = e;
e = next;
如果e这个元素不是要删除的话,则遍历下一个元素。
步骤3、找到
prev.next = next;
return e;
将prev的下一个元素指向e.next。这样就相当于删除了e
最后的结果如下:
二.解决hash冲突的办法
- 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
- 再哈希法
- 链地址法
- 建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。
三.实现自己的HashMap
Entry.java
MyHashMap.java
MyHashMapTest.java
- package edu.sjtu.erplab.hash;
- public class MyHashMapTest {
- public static void main(String[] args) {
- MyHashMap<Integer, Integer> map = new MyHashMap<Integer, Integer>();
- map.put(1, 90);
- map.put(2, 95);
- map.put(17, 85);
- System.out.println(map.get(1));
- System.out.println(map.get(2));
- System.out.println(map.get(17));
- System.out.println(map.get(null));
- }
- }