详解HashMap的使用及其实现

1.概述

HashMap可以说是在java中应用最频繁Map类型了。HashMap 是基于哈希表的 Map 接口的非同步实现====>这里可以说明，它不能保证映射的顺序，特别是它不能保证该顺序亘古不变，因为加入的元素是根据哈希值来存储的。HashMap允许存储null的key值和null的value值。

专注于为中小企业提供成都网站设计、做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业夷陵免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了1000+企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

由于HashMap是基于哈希表来实现的，所以此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高或将加载因子设置得太低。

需要注意的是：HashMap 不是同步的，如果多个线程同时访问一个 HashMap，而其中至少一个线程从结构上（指添加或者删除一个或多个映射关系的任何操作）修改了，则必须保持外部同步，以防止对映射进行意外的非同步访问。

2.实现原理

HashMap中的存储方式是数组+链表+红黑树。其中数组的类型是Entry类型的数组，当我们往HashMap内填充元素时，首先会计算其key的hashcode来重新计算key的hash值，并找到数组中对应的下标，如果该位置目前并没有元素，则直接将该元素放入数组中；如果该位置目前已经有了元素，则把新的元素加入到链表中。当元素的长度超过阈值（JDK1.8中该值为8）时，链表则会转换为红黑树（转换为红黑树还需要满足其他的条件，链表长度达到阈值只是其中的一个条件），这样会大大提高我们查找的效率。

HashMap的存储结构图。当链表过长时（>=8），会转换成红黑树来存储，以便提高查找效率：

使用这种存储方式是为了解决哈希碰撞的问题，换言之，链表中的每个key，都具有相同的哈希值。最极端的情况就是，当所有的元素都具有相同的哈希值，那么HashMap会退化为一个链表，查找时间也从O(1)上升到O(N)。当N越来越大时，get(key)方法的开销也越来越大。因此，在JDK1.8里面加入了一个红黑树：当某个桶内的记录过大的话（>=8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。它是如何去工作的呢：

前面产生冲突的那些key对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。

3.源码及分析

首先看一下HashMap的定义以及一些属性

 
 
 
 
    
  
  
  
  
  1. public class HashMap extends AbstractMap 
    2. 
  
  
  
  
  2.     implements Map, Cloneable, Serializable { 
    3. 
  
  
  
  
  3.     private static final long serialVersionUID = 362498820763181265L; 
    4. 
  
  
  
  
  4.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
    5. 
  
  
  
  
  5.     static final int MAXIMUM_CAPACITY = 1 << 30; 
    6. 
  
  
  
  
  6.     static final float DEFAULT_LOAD_FACTOR = 0.75f; 
    7. 
  
  
  
  
  7.     static final int TREEIFY_THRESHOLD = 8; 
    8. 
  
  
  
  
  8.     transient Node[] table; 
    9. 
  
  
  
  
  9.     transient Set> entrySet; 
    10. 
  
  
  
  
  10.     transient int size; 
    11. 
  
  
  
  
  11.     transient int modCount; 
    12. 
  
  
  
  
  12.     int threshold; 
    13. 
  
  
  
  
  13.     final float loadFactor; 
    14.

在这里我们可以看到，HashMap是继承于AbstractMap，并且实现了Map, Cloneable, Serializable接口。其默认的初始容量为16（DEFAULT_INITIAL_CAPACITY = 1 << 4），最大容量为2的30次幂（MAXIMUM_CAPACITY = 1 << 30），默认的加载因子为0.75（即当HashMap目前存储的元素超过其初始值加载因子，即160.75=12时，HashMap会进行扩容）。其他的我们可以看到TREEIFY_THRESHOLD = 8;表明当链表长度超过8时，会转化为红黑树。

HashMap中涉及的数据结构：

 
 
 
 
    
  
  
  
  
  1. static class Node implements Map.Entry { 
    2. 
  
  
  
  
  2.       //以下4行即为一个Entry  
    3. 
  
  
  
  
  3.        final int hash; 
    4. 
  
  
  
  
  4.         final K key;        V value;        Node next; 
    5. 
  
  
  
  
  5.         Node(int hash, K key, V value, Node next) { 
    6. 
  
  
  
  
  6.             this.hash = hash;            this.key = key;            this.value = value;            this.next = next; 
    7. 
  
  
  
  
  7.         } 
    8.

HashMap的构造函数：

 
 
 
 
    
  
  
  
  
  1. //构造函数1：指定初始容量和加载因子 
    2. 
  
  
  
  
  2.     public HashMap(int initialCapacity, float loadFactor) { 
    3. 
  
  
  
  
  3.         if (initialCapacity < 0) 
    4. 
  
  
  
  
  4.             throw new IllegalArgumentException("Illegal initial capacity: " + 
    5. 
  
  
  
  
  5.                                                initialCapacity); 
    6. 
  
  
  
  
  6.         /*指定的初始容量如果大于最大容量，则默认以最大容量座作为初始容  
    7. 
  
  
  
  
  7.          *量，则2的30次幂 
    8. 
  
  
  
  
  8.           */    
    9. 
  
  
  
  
  9.         if (initialCapacity > MAXIMUM_CAPACITY) 
    10. 
  
  
  
  
  10.             initialCapacity = MAXIMUM_CAPACITY; 
    11. 
  
  
  
  
  11.         //加载因子必须为正数 
    12. 
  
  
  
  
  12.         if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
    13. 
  
  
  
  
  13.             throw new IllegalArgumentException("Illegal load factor: " + 
    14. 
  
  
  
  
  14.                                                loadFactor); 
    15. 
  
  
  
  
  15.         this.loadFactor = loadFactor; 
    16. 
  
  
  
  
  16.         //新的扩容阈值 
    17. 
  
  
  
  
  17.         this.threshold = tableSizeFor(initialCapacity); 
    18. 
  
  
  
  
  18.     } 
    19. 
  
  
  
  
  19. //构造函数2：指定初始容量 
    20. 
  
  
  
  
  20.     public HashMap(int initialCapacity) { 
    21. 
  
  
  
  
  21.         this(initialCapacity, DEFAULT_LOAD_FACTOR); 
    22. 
  
  
  
  
  22.     } 
    23. 
  
  
  
  
  23. //构造函数3：无参数 
    24. 
  
  
  
  
  24.    /** 
    25. 
  
  
  
  
  25.      * Constructs an empty HashMap with the default initial capacity 
    26. 
  
  
  
  
  26.      * (16) and the default load factor (0.75). 
    27. 
  
  
  
  
  27.      */ 
    28. 
  
  
  
  
  28. //可以通过注释看到默认的初始值和加载因子 
    29. 
  
  
  
  
  29.     public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 
    30. 
  
  
  
  
  30.     }//构造函数4： 
    31. 
  
  
  
  
  31.     public HashMap(Map m) { 
    32. 
  
  
  
  
  32.         this.loadFactor = DEFAULT_LOAD_FACTOR; 
    33. 
  
  
  
  
  33.         putMapEntries(m, false); 
    34. 
  
  
  
  
  34.     } 
    35.

我们可以看到，即便我们指定了初始容量，初始容量也未必就是我们指定的大小，因为HashMap的容量始终都是2的次幂，所以当我们传入一个指定的容量时，还会调用一个tableSizeFor(int cap)方法来计算容量的大小：

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.      * Returns a power of two size for the given target capacity. 
    3. 
  
  
  
  
  3.      */ 
    4. 
  
  
  
  
  4.     static final int tableSizeFor(int cap) { 
    5. 
  
  
  
  
  5.         int n = cap - 1; 
    6. 
  
  
  
  
  6.         n |= n >>> 1; 
    7. 
  
  
  
  
  7.         n |= n >>> 2; 
    8. 
  
  
  
  
  8.         n |= n >>> 4; 
    9. 
  
  
  
  
  9.         n |= n >>> 8; 
    10. 
  
  
  
  
  10.         n |= n >>> 16; 
    11. 
  
  
  
  
  11.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    12. 
  
  
  
  
  12.     } 
    13.

HashMap的存取：

1）首先来看存储：

 
 
 
 
    
  
  
  
  
  1. public V put(K key, V value) { 
    2. 
  
  
  
  
  2.         return putVal(hash(key), key, value, false, true); 
    3. 
  
  
  
  
  3.     } 
    4. 
  
  
  
  
  4.     /** 
    5. 
  
  
  
  
  5.      * Implements Map.put and related methods. 
    6. 
  
  
  
  
  6.      * 
    7. 
  
  
  
  
  7.      * @param hash hash for key 
    8. 
  
  
  
  
  8.      * @param key the key 
    9. 
  
  
  
  
  9.      * @param value the value to put 
    10. 
  
  
  
  
  10.      * @param onlyIfAbsent if true, don't change existing value 
    11. 
  
  
  
  
  11.      * @param evict if false, the table is in creation mode. 
    12. 
  
  
  
  
  12.      * @return previous value, or null if none 
    13. 
  
  
  
  
  13.      */ 
    14. 
  
  
  
  
  14.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
    15. 
  
  
  
  
  15.                    boolean evict) { 
    16. 
  
  
  
  
  16.         Node[] tab; Node p; int n, i; 
    17. 
  
  
  
  
  17.         //当当前数组为空时，先进行扩容 
    18. 
  
  
  
  
  18.         //可以看出，在我们第一次调用put方法往HashMap添加元素之和，HashMap的size才开始是初始容量 
    19. 
  
  
  
  
  19.         if ((tab = table) == null || (n = tab.length) == 0) 
    20. 
  
  
  
  
  20.             n = (tab = resize()).length; 
    21. 
  
  
  
  
  21.         //当数组的当前位置为空时，直接创建一个新的节点并放进去 
    22. 
  
  
  
  
  22.         if ((p = tab[i = (n - 1) & hash]) == null) 
    23. 
  
  
  
  
  23.             tab[i] = newNode(hash, key, value, null); 
    24. 
  
  
  
  
  24.         //当前位置非空，产生哈希冲突 
    25. 
  
  
  
  
  25.         else { 
    26. 
  
  
  
  
  26.             Node e; K k; 
    27. 
  
  
  
  
  27.             if (p.hash == hash && 
    28. 
  
  
  
  
  28.                 ((k = p.key) == key || (key != null && key.equals(k)))) 
    29. 
  
  
  
  
  29.                 e = p; 
    30. 
  
  
  
  
  30.             //判断当前是否已经是以红黑树为存储结构 
    31. 
  
  
  
  
  31.             else if (p instanceof TreeNode) 
    32. 
  
  
  
  
  32.                 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 
    33. 
  
  
  
  
  33.             else { 
    34. 
  
  
  
  
  34.                 for (int binCount = 0; ; ++binCount) { 
    35. 
  
  
  
  
  35.                     //当遍历到链表的尾端时，则把需要put的元素加进去 
    36. 
  
  
  
  
  36.                     if ((e = p.next) == null) { 
    37. 
  
  
  
  
  37.                         p.next = newNode(hash, key, value, null); 
    38. 
  
  
  
  
  38.                         //判断冲突的节点数是否已经达到阈值8 
    39. 
  
  
  
  
  39.                         //如果达到8，则判断HashMap的size是否已经>=64，如果没有则只进行扩容 
    40. 
  
  
  
  
  40.                         //当HashMap的size >= 64并且冲突的节点数达到8时，用红黑树去存储产生冲突的节点 
    41. 
  
  
  
  
  41.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
    42. 
  
  
  
  
  42.                             treeifyBin(tab, hash); 
    43. 
  
  
  
  
  43.                         break; 
    44. 
  
  
  
  
  44.                     } 
    45. 
  
  
  
  
  45.                     if (e.hash == hash && 
    46. 
  
  
  
  
  46.                         ((k = e.key) == key || (key != null && key.equals(k)))) 
    47. 
  
  
  
  
  47.                         break; 
    48. 
  
  
  
  
  48.                     p = e; 
    49. 
  
  
  
  
  49.                 } 
    50. 
  
  
  
  
  50.             } 
    51. 
  
  
  
  
  51.             //如果有相同的key，则用新的value覆盖旧的value，并把旧的value返回 
    52. 
  
  
  
  
  52.             if (e != null) { // existing mapping for key 
    53. 
  
  
  
  
  53.                 V oldValue = e.value; 
    54. 
  
  
  
  
  54.                 if (!onlyIfAbsent || oldValue == null) 
    55. 
  
  
  
  
  55.                     e.value = value; 
    56. 
  
  
  
  
  56.                 afterNodeAccess(e); 
    57. 
  
  
  
  
  57.                 return oldValue; 
    58. 
  
  
  
  
  58.             } 
    59. 
  
  
  
  
  59.         } 
    60. 
  
  
  
  
  60.         ++modCount; 
    61. 
  
  
  
  
  61.         if (++size > threshold) 
    62. 
  
  
  
  
  62.             resize(); 
    63. 
  
  
  
  
  63.         afterNodeInsertion(evict); 
    64. 
  
  
  
  
  64.         return null; 
    65. 
  
  
  
  
  65.     } 
    66.

通过源码可以看到，put(key, value)的过程为：

①检查tab[]是否为空或null，如果是，则进行扩容

②根据键值计算其在数组中的下标i，如果tab[i] == null，则直接插入新建的节点

③若tab[i]已经有元素存储了，则判断当前处理节点的方式为链表还是红黑树，分别处理

在存储的时候，有一个细节需要注意一下：注意到p = tab[i = (n - 1) & hash]，其中的数组下标是通过（n-1）&hash的方式来计算出来的，这里处理的非常巧妙：

对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序得到的 hash 码值总是相同的。我们首先想到的就是把 hash 值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，而HashMap的底层数组的大小总是为2的n次幂，此时，h& (length-1)运算等价于对 length 取模，也就是 h%length。

举个例子说明：

我们可以看到，当数组长度为15时，8或9与其相遇，都会产生相同的结果，此时就会发生哈希冲突，8和9都会放到数组中的同一个位置，形成链表，这样会降低了查询的效率。同时，我们可以发现，当数组长度不为2的n次幂时，table.length-1永远会有0存在，而0无论是和1还是0相与，结果都为0。比如说，长度为15，那么15-1=14，其二进制为1110，此时，无论什么数与1110相与，末尾都为0，这时候，0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组的长度为2的n次幂时，table.length-1得到的二进制数的每个位上的值都为 1，这使得在低位上&时，得到的和原 hash 的低位相同，就使得只有相同的 hash 值的两个值才会被放到数组中的同一个位置上形成链表。所以说，当数组长度为 2 的 n 次幂的时候，不同的 key 算得得 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了

2）HashMap的读取：

 
 
 
 
    
  
  
  
  
  1. public V get(Object key) { 
    2. 
  
  
  
  
  2.         Node e; 
    3. 
  
  
  
  
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value; 
    4. 
  
  
  
  
  4.     } 
    5. 
  
  
  
  
  5.     /** 
    6. 
  
  
  
  
  6.      * Implements Map.get and related methods. 
    7. 
  
  
  
  
  7.      * 
    8. 
  
  
  
  
  8.      * @param hash hash for key 
    9. 
  
  
  
  
  9.      * @param key the key 
    10. 
  
  
  
  
  10.      * @return the node, or null if none 
    11. 
  
  
  
  
  11.      */ 
    12. 
  
  
  
  
  12.     final Node getNode(int hash, Object key) { 
    13. 
  
  
  
  
  13.         Node[] tab; Node first, e; int n; K k; 
    14. 
  
  
  
  
  14.         //找到第一个插入的node 
    15. 
  
  
  
  
  15.         if ((tab = table) != null && (n = tab.length) > 0 && 
    16. 
  
  
  
  
  16.             (first = tab[(n - 1) & hash]) != null) { 
    17. 
  
  
  
  
  17.             if (first.hash == hash && // always check first node 
    18. 
  
  
  
  
  18.                 ((k = first.key) == key || (key != null && key.equals(k)))) 
    19. 
  
  
  
  
  19.                 return first; 
    20. 
  
  
  
  
  20.             //当first节点不是所查找的节点时 
    21. 
  
  
  
  
  21.             if ((e = first.next) != null) { 
    22. 
  
  
  
  
  22.                 //判断是否当前是否用红黑树来存储 
    23. 
  
  
  
  
  23.                 if (first instanceof TreeNode) 
    24. 
  
  
  
  
  24.                     return ((TreeNode)first).getTreeNode(hash, key); 
    25. 
  
  
  
  
  25.                 //遍历链表 
    26. 
  
  
  
  
  26.                 do { 
    27. 
  
  
  
  
  27.                     if (e.hash == hash && 
    28. 
  
  
  
  
  28.                         ((k = e.key) == key || (key != null && key.equals(k)))) 
    29. 
  
  
  
  
  29.                         return e; 
    30. 
  
  
  
  
  30.                 } while ((e = e.next) != null); 
    31. 
  
  
  
  
  31.             } 
    32. 
  
  
  
  
  32.         } 
    33. 
  
  
  
  
  33.         return null; 
    34. 
  
  
  
  
  34.     } 
    35.

在调用get(key)方法时，会先获取可以的hash值，并计算得到此key在数组中的位置：first = tab[(n - 1) & hash]，如果first节点不是需要获取的key，则往下遍历，直到找到需要获取的键值，并返回对应的value即可。

HashMap的扩容机制

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.      * Initializes or doubles table size.  If null, allocates in 
    3. 
  
  
  
  
  3.      * accord with initial capacity target held in field threshold. 
    4. 
  
  
  
  
  4.      * Otherwise, because we are using power-of-two expansion, the 
    5. 
  
  
  
  
  5.      * elements from each bin must either stay at same index, or move 
    6. 
  
  
  
  
  6.      * with a power of two offset in the new table. 
    7. 
  
  
  
  
  7.      * 
    8. 
  
  
  
  
  8.      * @return the table 
    9. 
  
  
  
  
  9.      */ 
    10. 
  
  
  
  
  10.     final Node[] resize() { 
    11. 
  
  
  
  
  11.         Node[] oldTab = table; 
    12. 
  
  
  
  
  12.         int oldCap = (oldTab == null) ? 0 : oldTab.length; 
    13. 
  
  
  
  
  13.         int oldThr = threshold; 
    14. 
  
  
  
  
  14.         int newCap, newThr = 0; 
    15. 
  
  
  
  
  15.         if (oldCap > 0) { 
    16. 
  
  
  
  
  16.             if (oldCap >= MAXIMUM_CAPACITY) { 
    17. 
  
  
  
  
  17.                 threshold = Integer.MAX_VALUE; 
    18. 
  
  
  
  
  18.                 return oldTab; 
    19. 
  
  
  
  
  19.             } 
    20. 
  
  
  
  
  20.             //旧表的长度不为0，则把新表的容量设置为旧表容量的两倍 
    21. 
  
  
  
  
  21.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
    22. 
  
  
  
  
  22.                      oldCap >= DEFAULT_INITIAL_CAPACITY) 
    23. 
  
  
  
  
  23.                 newThr = oldThr << 1; // double threshold 
    24. 
  
  
  
  
  24.         } 
    25. 
  
  
  
  
  25.         else if (oldThr > 0) // initial capacity was placed in threshold 
    26. 
  
  
  
  
  26.             newCap = oldThr; 
    27. 
  
  
  
  
  27.         //如果旧表的长度为0，则说明是第一次初始化 
    28. 
  
  
  
  
  28.         else {               // zero initial threshold signifies using defaults 
    29. 
  
  
  
  
  29.             newCap = DEFAULT_INITIAL_CAPACITY; 
    30. 
  
  
  
  
  30.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
    31. 
  
  
  
  
  31.         } 
    32. 
  
  
  
  
  32.         if (newThr == 0) { 
    33. 
  
  
  
  
  33.             float ft = (float)newCap * loadFactor; 
    34. 
  
  
  
  
  34.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
    35. 
  
  
  
  
  35.                       (int)ft : Integer.MAX_VALUE); 
    36. 
  
  
  
  
  36.         } 
    37. 
  
  
  
  
  37.         threshold = newThr; 
    38. 
  
  
  
  
  38.         @SuppressWarnings({"rawtypes","unchecked"}) 
    39. 
  
  
  
  
  39.         Node[] newTab = (Node[])new Node[newCap]; 
    40. 
  
  
  
  
  40.         table = newTab; 
    41. 
  
  
  
  
  41.         if (oldTab != null) { 
    42. 
  
  
  
  
  42.             for (int j = 0; j < oldCap; ++j) { 
    43. 
  
  
  
  
  43.                 Node e; 
    44. 
  
  
  
  
  44.                 if ((e = oldTab[j]) != null) { 
    45. 
  
  
  
  
  45.                     oldTab[j] = null; 
    46. 
  
  
  
  
  46.                     //e.next为null说明此位置没有形成链表 
    47. 
  
  
  
  
  47.                     if (e.next == null) 
    48. 
  
  
  
  
  48.                         newTab[e.hash & (newCap - 1)] = e;  //重新计算该元素在新表中的位置并插入 
    49. 
  
  
  
  
  49.                     //判断是否为红黑树存储方式 
    50. 
  
  
  
  
  50.                     else if (e instanceof TreeNode) 
    51. 
  
  
  
  
  51.                         ((TreeNode)e).split(this, newTab, j, oldCap); 
    52. 
  
  
  
  
  52.                     else { // preserve order 
    53. 
  
  
  
  
  53.                         Node loHead = null, loTail = null; 
    54. 
  
  
  
  
  54.                         Node hiHead = null, hiTail = null; 
    55. 
  
  
  
  
  55.                         Node next; 
    56. 
  
  
  
  
  56.                         //遍历链表 
    57. 
  
  
  
  
  57.                         do { 
    58. 
  
  
  
  
  58.                             next = e.next; 
    59. 
  
  
  
  
  59.                             //将链表的节点拆分为两队，e.hash&oldCap结果为0的一队，结果为1的为另一队 
    60. 
  
  
  
  
  60.                             if ((e.hash & oldCap) == 0) { 
    61. 
  
  
  
  
  61.                                 if (loTail == null) 
    62. 
  
  
  
  
  62.                                     loHead = e; 
    63. 
  
  
  
  
  63.                                 else 
    64. 
  
  
  
  
  64.                                     loTail.next = e; 
    65. 
  
  
  
  
  65.                                 loTail = e; 
    66. 
  
  
  
  
  66.                             } 
    67. 
  
  
  
  
  67.                             else { 
    68. 
  
  
  
  
  68.                                 if (hiTail == null) 
    69. 
  
  
  
  
  69.                                     hiHead = e; 
    70. 
  
  
  
  
  70.                                 else 
    71. 
  
  
  
  
  71.                                     hiTail.next = e; 
    72. 
  
  
  
  
  72.                                 hiTail = e; 
    73. 
  
  
  
  
  73.                             } 
    74. 
  
  
  
  
  74.                         } while ((e = next) != null); 
    75. 
  
  
  
  
  75.                         if (loTail != null) { 
    76. 
  
  
  
  
  76.                             loTail.next = null; 
    77. 
  
  
  
  
  77.                             newTab[j] = loHead; 
    78. 
  
  
  
  
  78.                         } 
    79. 
  
  
  
  
  79.                         if (hiTail != null) { 
    80. 
  
  
  
  
  80.                             hiTail.next = null; 
    81. 
  
  
  
  
  81.                             newTab[j + oldCap] = hiHead; 
    82. 
  
  
  
  
  82.                         } 
    83. 
  
  
  
  
  83.                     } 
    84. 
  
  
  
  
  84.                 } 
    85. 
  
  
  
  
  85.             } 
    86. 
  
  
  
  
  86.         } 
    87. 
  
  
  
  
  87.         return newTab; 
    88. 
  
  
  
  
  88.     } 
    89.

当HashMap中的元素越来越多的时候，产生哈希冲突的几率也就越来越大，毕竟数组的长度是固定的。为了减小哈希冲突的几率，同时也是为了提高查询效率，我们需要对HashMap适当的进行扩容。而扩容也不是产生哈希冲突之后就开始执行，而是要满足一定条件之后才扩容：当HashMap中元素的个数已经达到阈值，则table.length * loadFactory，比如说采用无参数构造器去创建一个HashMap，那么table.length * loadFactory = 16 * 0.75 == 12，即当HashMap中的元素个数达到12时，HashMap才开始扩容。扩容之后的大小为之前的两倍。我们在源码中可以看到，扩容是一项很费时的操作，如果我们能够预知HashMap中元素的个数，那么在初始化时指定初始值以及加载因子来规避扩容，也是提高性能的一种方法。

Fail-Fast机制

原理

fail-fast 机制是 java 集合(Collection)中的一种错误机制。 当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。

比如说，在线程A通过 iterator去访问集合时，如果有其他线程修改了该集合，那么A线程这里就会抛出 ConcurrentModificationException 异常，产生 fail-fast 事件。

我们知道，java.util.HashMap不是线程安全的，在多线程的环境中，如果A线程正在通过iterator去访问这个map，而其他线程则修改了该map，那么A线程就会抛出一个ConcurrentModificationException异常。

这个策略在源码中的实现则是通过modCount，每一次修改map中的内容，modCount的值都会增加，在迭代器开始的过程中，会把modCount的值赋给迭代器的 expectedModCount：

 
 
 
 
    
  
  
  
  
  1. HashIterator() { 
    2. 
  
  
  
  
  2.             expectedModCount = modCount; 
    3. 
  
  
  
  
  3.             Node[] t = table; 
    4. 
  
  
  
  
  4.             current = next = null; 
    5. 
  
  
  
  
  5.             index = 0; 
    6. 
  
  
  
  
  6.             if (t != null && size > 0) { // advance to first entry 
    7. 
  
  
  
  
  7.                 do {} while (index < t.length && (next = t[index++]) == null); 
    8. 
  
  
  
  
  8.             } 
    9. 
  
  
  
  
  9.         } 
    10.

在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 map：

 
 
 
 
    
  
  
  
  
  1. final Node nextNode() { 
    2. 
  
  
  
  
  2.             Node[] t;            Node e = next;            if (modCount != expectedModCount) 
    3. 
  
  
  
  
  3.                 throw new ConcurrentModificationException(); 
    4. 
  
  
  
  
  4.             ...        } 
    5.

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

解决方案

fail-fast 机制，是一种错误检测机制。它只能被用来检测错误，因为 JDK 并不保证 fail-fast 机制一定会发生。若在多线程环境下使用 fail-fast 机制的集合，建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”。

与Hashtable的比较

相同点：

①都是基于哈希表实现的，并且里面存储的元素都是key-value对

②当产生哈希冲突时，内部都会通过单链表去解决冲突问题（当然JDK1.8中HashMap中加入了红黑树）

③内部容量不足时，都会自动进行扩容

④都实现了Map、Cloneable、Serializable接口，可以被克隆，支持序列化

区别：

①继承的父类不同

HashMap继承的是AbstractMap，而Hashtable继承的是Dictionary

②线程安全性不同

<

网站栏目：详解HashMap的使用及其实现
文章来源：http://www.shufengxianlan.com/qtweb/news10/309560.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站策划知识

分类信息网

小谭网创广告　　 　外贸营销网站建设　　 　温江服务器托管　　 　成都酒店服定制　　 　无边发光字　　 　力比特机械　　 　免备案虚拟主机　　 　自动门　　 　成都铁科精智测控　　 　泸县网站建设　　 　全网营销　　 　商城网站建设公司　　 　成都网站推广　　 　成都400电话办理　　 　成都集团网站建设　　 　产品包装设计　　 　自贡服务器托管　　 　云主机　　 　成都康明斯发电机　　 　微信小程序开发