HashMap实现细节,hash对key为 null的处理,对重哈希的处理

时间:2022-12-26 09:57:26

 

一、解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中有:


[java]  ​​view plain​​ ​​copy​​


  1. transient Entry[] table;  


而Entry的定义如下:


[java]  ​​view plain​​ ​​copy​​


  1. static class Entry<K,V> implements Map.Entry<K,V> {  
  2. final K key;  
  3.         V value;  
  4.         Entry<K,V> next;  
  5. final int hash;  
  6.  .........  
  7. }  

简单说就是一个数组+链表,结构如下图: 





2、HashMap的初始化 


[java]  ​​view plain​​ ​​copy​​


  1. public HashMap() {  
  2. this.loadFactor = DEFAULT_LOAD_FACTOR;  
  3. threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);  
  4. table = new Entry[DEFAULT_INITIAL_CAPACITY];  
  5. init();  
  6. }  


  构造方法中出现的几个关键字段: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下标索引 


[java]  ​​view plain​​ ​​copy​​


  1. static int hash(int h) {  
  2. h ^= (h >>> 20) ^ (h >>> 12);  
  3. return h ^ (h >>> 7) ^ (h >>> 4);  
  4. }  


 

这个不深究,结果是获得一个随机点的hash值 


[java]  ​​view plain​​ ​​copy​​


  1. static int indexFor(int h, int length) {  
  2. return h & (length-1);  
  3. }  


    这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度

4、元素添加方法addEntry 


[java]  ​​view plain​​ ​​copy​​


  1. void addEntry(int hash, K key, V value, int bucketIndex) {  
  2.     Entry<K,V> e = table[bucketIndex];  
  3. new Entry<K,V>(hash, key, value, e);  
  4. if (size++ >= threshold)  
  5. 2 * table.length);  
  6. }  
  7. //Entry的构造方法  
  8. Entry(int h, K k, V v, Entry<K,V> n) {  
  9.     value = v;  
  10.     next = n;  
  11.     key = k;  
  12.     hash = h;  
  13. }  

    addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。

    说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图: 



5、HashMap扩容 


[java]  ​​view plain​​ ​​copy​​


  1. void resize(int newCapacity) {  
  2.     Entry[] oldTable = table;  
  3. int oldCapacity = oldTable.length;  
  4. if (oldCapacity == MAXIMUM_CAPACITY) {  
  5.         threshold = Integer.MAX_VALUE;  
  6. return;  
  7.     }  
  8. new Entry[newCapacity];  
  9.     transfer(newTable);  
  10.     table = newTable;  
  11. int)(newCapacity * loadFactor);  
  12. }  


在元素添加方法addEntry中,添加完元素后,有下面两行代码: 


[java]  ​​view plain​​ ​​copy​​


  1. if (size++ >= threshold)  
  2. 2 * table.length);  


    size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
    前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。

6、老table重新hash成新table  



[java]  ​​view plain​​ ​​copy​​


  1. void transfer(Entry[] newTable) {  
  2.     Entry[] src = table;  
  3. int newCapacity = newTable.length;  
  4. for (int j = 0; j < src.length; j++) {  
  5.         Entry<K,V> e = src[j];  
  6. if (e != null) {  
  7. null;  
  8. do {  
  9.                 Entry<K,V> next = e.next;  
  10. int i = indexFor(e.hash, newCapacity);  
  11.                 e.next = newTable[i];  
  12.                 newTable[i] = e;  
  13.                 e = next;  
  14. while (e != null);  
  15.         }  
  16.     }  
  17. }  

    这个方法的主要作用就是,将老的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的情况。 


[java]  ​​view plain​​ ​​copy​​


  1. if (key == null)  
  2. return putForNullKey(value);  
  3. //那就看看这个putForNullKey是怎么处理的吧。  
  4. private V putForNullKey(V value) {  
  5. for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  6. if (e.key == null) {  
  7.             V oldValue = e.value;  
  8.             e.value = value;  
  9. this);  
  10. return oldValue;  
  11.         }  
  12.     }  
  13.     modCount++;  
  14. 0, null, value, 0);  
  15. return null;  
  16. }  


    可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
    如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。 

8、查找元素get(Object key) 


[java]  ​​view plain​​ ​​copy​​


  1. public V get(Object key) {  
  2. if (key == null)  
  3. return getForNullKey();  
  4. int hash = hash(key.hashCode());  
  5. for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {  
  6.         Object k;  
  7. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
  8. return e.value;  
  9.     }  
  10. return null;  
  11. }  


    前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
    如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。


[java]  ​​view plain​​ ​​copy​​


  1. public V remove(Object key) {  
  2.     Entry<K,V> e = removeEntryForKey(key);  
  3. return (e == null ? null : e.value);  
  4. }  
  5. 调用的还是下面的方法  
  6. final Entry<K,V> removeEntryForKey(Object key) {  
  7. int hash = (key == null) ? 0 : hash(key.hashCode());  
  8. int i = indexFor(hash, table.length);  
  9.         Entry<K,V> prev = table[i];  
  10.         Entry<K,V> e = prev;  
  11. while (e != null) {  
  12.             Entry<K,V> next = e.next;  
  13.             Object k;  
  14. if (e.hash == hash &&  
  15. null && key.equals(k)))) {  
  16.                 modCount++;  
  17.                 size--;  
  18. if (prev == e)  
  19.                     table[i] = next;  
  20. else  
  21.                     prev.next = next;  
  22. this);  
  23. return e;  
  24.             }  
  25.             prev = e;  
  26.             e = next;  
  27.         }  
  28. return e;  
  29.     }  

    这里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冲突的办法

  1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
  2. 再哈希法
  3. 链地址法
  4. 建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法。

三.实现自己的HashMap

Entry.java




[java]  ​​view plain​​ ​​copy​​


  1. package edu.sjtu.erplab.hash;  
  2.   
  3. public class Entry<K,V>{  
  4. final K key;  
  5.     V value;  
  6. //下一个结点  
  7.    
  8. //构造函数  
  9. public Entry(K k, V v, Entry<K,V> n) {  
  10.         key = k;  
  11.         value = v;  
  12.         next = n;  
  13.     }  
  14.   
  15. public final K getKey() {  
  16. return key;  
  17.     }  
  18.   
  19. public final V getValue() {  
  20. return value;  
  21.     }  
  22.   
  23. public final V setValue(V newValue) {  
  24.     V oldValue = value;  
  25.         value = newValue;  
  26. return oldValue;  
  27.     }  
  28.   
  29. public final boolean equals(Object o) {  
  30. if (!(o instanceof Entry))  
  31. return false;  
  32.         Entry e = (Entry)o;  
  33.         Object k1 = getKey();  
  34.         Object k2 = e.getKey();  
  35. if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
  36.             Object v1 = getValue();  
  37.             Object v2 = e.getValue();  
  38. if (v1 == v2 || (v1 != null && v1.equals(v2)))  
  39. return true;  
  40.         }  
  41. return false;  
  42.     }  
  43.   
  44. public final int hashCode() {  
  45. return (key==null   ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());  
  46.     }  
  47.   
  48. public final String toString() {  
  49. return getKey() + "=" + getValue();  
  50.     }  
  51.   
  52. }  



MyHashMap.java




[java]  ​​view plain​​ ​​copy​​


  1. package edu.sjtu.erplab.hash;  
  2.   
  3. //保证key与value不为空  
  4. public class MyHashMap<K, V> {  
  5. private Entry[] table;//Entry数组表  
  6. static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度  
  7. private int size;  
  8.   
  9. // 构造函数  
  10. public MyHashMap() {  
  11. new Entry[DEFAULT_INITIAL_CAPACITY];  
  12.         size = DEFAULT_INITIAL_CAPACITY;  
  13.     }  
  14.   
  15. //获取数组长度  
  16. public int getSize() {  
  17. return size;  
  18.     }  
  19.       
  20. // 求index  
  21. static int indexFor(int h, int length) {  
  22. return h % (length - 1);  
  23.     }  
  24.   
  25. //获取元素  
  26. public V get(Object key) {  
  27. if (key == null)  
  28. return null;  
  29. int hash = key.hashCode();// key的哈希值  
  30. int index = indexFor(hash, table.length);// 求key在数组中的下标  
  31. for (Entry<K, V> e = table[index]; e != null; e = e.next) {  
  32.             Object k = e.key;  
  33. if (e.key.hashCode() == hash && (k == key || key.equals(k)))  
  34. return e.value;  
  35.         }  
  36. return null;  
  37.     }  
  38.   
  39. // 添加元素  
  40. public V put(K key, V value) {  
  41. if (key == null)  
  42. return null;  
  43. int hash = key.hashCode();  
  44. int index = indexFor(hash, table.length);  
  45.   
  46. // 如果添加的key已经存在,那么只需要修改value值即可  
  47. for (Entry<K, V> e = table[index]; e != null; e = e.next) {  
  48.             Object k = e.key;  
  49. if (e.key.hashCode() == hash && (k == key || key.equals(k))) {  
  50.                 V oldValue = e.value;  
  51.                 e.value = value;  
  52. return oldValue;// 原来的value值  
  53.             }  
  54.         }  
  55. // 如果key值不存在,那么需要添加  
  56. // 获取当前数组中的e  
  57. new Entry<K, V>(key, value, e);// 新建一个Entry,并将其指向原先的e  
  58. return null;  
  59.     }  
  60.   
  61. }  



MyHashMapTest.java




[java]  ​​view plain​​ ​​copy​​


  1. package edu.sjtu.erplab.hash;  
  2.   
  3. public class MyHashMapTest {  
  4.   
  5. public static void main(String[] args) {  
  6.   
  7. new MyHashMap<Integer, Integer>();  
  8. 1, 90);  
  9. 2, 95);  
  10. 17, 85);  
  11.       
  12. 1));  
  13. 2));  
  14. 17));  
  15. null));  
  16.     }  
  17. }