HashMap源码剖析(五)

转载:http://blog.csdn.net/ns_code/article/details/36034955

HashMap简介

HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。

HashMap源码剖析

HashMap的源码如下(加入了比较详细的注释):

  1. package java.util;
  2. import java.io.*;
  3. public class HashMap<K,V>
  4.     extends AbstractMap<K,V>
  5.     implements Map<K,V>, Cloneable, Serializable
  6. {
  7.     // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂。  
  8.     static final int DEFAULT_INITIAL_CAPACITY = 16;
  9.     // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换)  
  10.     static final int MAXIMUM_CAPACITY = 1 << 30;
  11.     // 默认加载因子为0.75 
  12.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  13.     // 存储数据的Entry数组,长度是2的幂。  
  14.     // HashMap采用链表法解决冲突,每一个Entry本质上是一个单向链表  
  15.     transient Entry[] table;
  16.     // HashMap的底层数组中已用槽的数量  
  17.     transient int size;
  18.     // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)  
  19.     int threshold;
  20.     // 加载因子实际大小  
  21.     final float loadFactor;
  22.     // HashMap被改变的次数  
  23.     transient volatile int modCount;
  24.     // 指定“容量大小”和“加载因子”的构造函数  
  25.     public HashMap(int initialCapacity, float loadFactor) {
  26.         if (initialCapacity < 0)
  27.             throw new IllegalArgumentException("Illegal initial capacity: " +
  28.                                                initialCapacity);
  29.         // HashMap的最大容量只能是MAXIMUM_CAPACITY  
  30.         if (initialCapacity > MAXIMUM_CAPACITY)
  31.             initialCapacity = MAXIMUM_CAPACITY;
  32.         //加载因此不能小于0
  33.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  34.             throw new IllegalArgumentException("Illegal load factor: " +
  35.                                                loadFactor);
  36.         // 找出“大于initialCapacity”的最小的2的幂  
  37.         int capacity = 1;
  38.         while (capacity < initialCapacity)
  39.             capacity <<= 1;
  40.         // 设置“加载因子”  
  41.         this.loadFactor = loadFactor;
  42.         // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。  
  43.         threshold = (int)(capacity * loadFactor);
  44.         // 创建Entry数组,用来保存数据  
  45.         table = new Entry[capacity];
  46.         init();
  47.     }
  48.     // 指定“容量大小”的构造函数  
  49.     public HashMap(int initialCapacity) {
  50.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  51.     }
  52.     // 默认构造函数。  
  53.     public HashMap() {
  54.         // 设置“加载因子”为默认加载因子0.75  
  55.         this.loadFactor = DEFAULT_LOAD_FACTOR;
  56.         // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。  
  57.         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  58.         // 创建Entry数组,用来保存数据  
  59.         table = new Entry[DEFAULT_INITIAL_CAPACITY];
  60.         init();
  61.     }
  62.     // 包含“子Map”的构造函数  
  63.     public HashMap(Map<? extends K, ? extends V> m) {
  64.         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
  65.                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  66.         // 将m中的全部元素逐个添加到HashMap中  
  67.         putAllForCreate(m);
  68.     }
  69.     //求hash值的方法,重新计算hash值
  70.     static int hash(int h) {
  71.         h ^= (h >>> 20) ^ (h >>> 12);
  72.         return h ^ (h >>> 7) ^ (h >>> 4);
  73.     }
  74.     // 返回h在数组中的索引值,这里用&代替取模,旨在提升效率 
  75.     // h & (length-1)保证返回值的小于length  
  76.     static int indexFor(int h, int length) {
  77.         return h & (length-1);
  78.     }
  79.     public int size() {
  80.         return size;
  81.     }
  82.     public boolean isEmpty() {
  83.         return size == 0;
  84.     }
  85.     // 获取key对应的value  
  86.     public V get(Object key) {
  87.         if (key == null)
  88.             return getForNullKey();
  89.         // 获取key的hash值  
  90.         int hash = hash(key.hashCode());
  91.         // 在“该hash值对应的链表”上查找“键值等于key”的元素  
  92.         for (Entry<K,V> e = table[indexFor(hash, table.length)];
  93.              e != null;
  94.              e = e.next) {
  95.             Object k;
  96.             //判断key是否相同
  97.             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  98.                 return e.value;
  99.         }
  100.         //没找到则返回null
  101.         return null;
  102.     }
  103.     // 获取“key为null”的元素的值  
  104.     // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!  
  105.     private V getForNullKey() {
  106.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  107.             if (e.key == null)
  108.                 return e.value;
  109.         }
  110.         return null;
  111.     }
  112.     // HashMap是否包含key  
  113.     public boolean containsKey(Object key) {
  114.         return getEntry(key) != null;
  115.     }
  116.     // 返回“键为key”的键值对  
  117.     final Entry<K,V> getEntry(Object key) {
  118.         // 获取哈希值  
  119.         // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值  
  120.         int hash = (key == null) ? 0 : hash(key.hashCode());
  121.         // 在“该hash值对应的链表”上查找“键值等于key”的元素  
  122.         for (Entry<K,V> e = table[indexFor(hash, table.length)];
  123.              e != null;
  124.              e = e.next) {
  125.             Object k;
  126.             if (e.hash == hash &&
  127.                 ((k = e.key) == key || (key != null && key.equals(k))))
  128.                 return e;
  129.         }
  130.         return null;
  131.     }
  132.     // 将“key-value”添加到HashMap中  
  133.     public V put(K key, V value) {
  134.         // 若“key为null”,则将该键值对添加到table[0]中。  
  135.         if (key == null)
  136.             return putForNullKey(value);
  137.         // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。  
  138.         int hash = hash(key.hashCode());
  139.         int i = indexFor(hash, table.length);
  140.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  141.             Object k;
  142.             // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!  
  143.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  144.                 V oldValue = e.value;
  145.                 e.value = value;
  146.                 e.recordAccess(this);
  147.                 return oldValue;
  148.             }
  149.         }
  150.         // 若“该key”对应的键值对不存在,则将“key-value”添加到table中  
  151.         modCount++;
  152.         //将key-value添加到table[i]处
  153.         addEntry(hash, key, value, i);
  154.         return null;
  155.     }
  156.     // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置  
  157.     private V putForNullKey(V value) {
  158.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  159.             if (e.key == null) {
  160.                 V oldValue = e.value;
  161.                 e.value = value;
  162.                 e.recordAccess(this);
  163.                 return oldValue;
  164.             }
  165.         }
  166.         // 如果没有存在key为null的键值对,则直接题阿见到table[0]处!  
  167.         modCount++;
  168.         addEntry(0null, value, 0);
  169.         return null;
  170.     }
  171.     // 创建HashMap对应的“添加方法”,  
  172.     // 它和put()不同。putForCreate()是内部方法,它被构造函数等调用,用来创建HashMap  
  173.     // 而put()是对外提供的往HashMap中添加元素的方法。  
  174.     private void putForCreate(K key, V value) {
  175.         int hash = (key == null) ? 0 : hash(key.hashCode());
  176.         int i = indexFor(hash, table.length);
  177.         // 若该HashMap表中存在“键值等于key”的元素,则替换该元素的value值  
  178.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  179.             Object k;
  180.             if (e.hash == hash &&
  181.                 ((k = e.key) == key || (key != null && key.equals(k)))) {
  182.                 e.value = value;
  183.                 return;
  184.             }
  185.         }
  186.         // 若该HashMap表中不存在“键值等于key”的元素,则将该key-value添加到HashMap中  
  187.         createEntry(hash, key, value, i);
  188.     }
  189.     // 将“m”中的全部元素都添加到HashMap中。  
  190.     // 该方法被内部的构造HashMap的方法所调用。  
  191.     private void putAllForCreate(Map<? extends K, ? extends V> m) {
  192.         // 利用迭代器将元素逐个添加到HashMap中  
  193.         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
  194.             Map.Entry<? extends K, ? extends V> e = i.next();
  195.             putForCreate(e.getKey(), e.getValue());
  196.         }
  197.     }
  198.     // 重新调整HashMap的大小,newCapacity是调整后的容量  
  199.     void resize(int newCapacity) {
  200.         Entry[] oldTable = table;
  201.         int oldCapacity = oldTable.length;
  202.         //如果就容量已经达到了最大值,则不能再扩容,直接返回
  203.         if (oldCapacity == MAXIMUM_CAPACITY) {
  204.             threshold = Integer.MAX_VALUE;
  205.             return;
  206.         }
  207.         // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,  
  208.         // 然后,将“新HashMap”赋值给“旧HashMap”。  
  209.         Entry[] newTable = new Entry[newCapacity];
  210.         transfer(newTable);
  211.         table = newTable;
  212.         threshold = (int)(newCapacity * loadFactor);
  213.     }
  214.     // 将HashMap中的全部元素都添加到newTable中  
  215.     void transfer(Entry[] newTable) {
  216.         Entry[] src = table;
  217.         int newCapacity = newTable.length;
  218.         for (int j = 0; j < src.length; j++) {
  219.             Entry<K,V> e = src[j];
  220.             if (e != null) {
  221.                 src[j] = null;
  222.                 do {
  223.                     Entry<K,V> next = e.next;
  224.                     int i = indexFor(e.hash, newCapacity);
  225.                     e.next = newTable[i];
  226.                     newTable[i] = e;
  227.                     e = next;
  228.                 } while (e != null);
  229.             }
  230.         }
  231.     }
  232.     // 将"m"的全部元素都添加到HashMap中  
  233.     public void putAll(Map<? extends K, ? extends V> m) {
  234.         // 有效性判断  
  235.         int numKeysToBeAdded = m.size();
  236.         if (numKeysToBeAdded == 0)
  237.             return;
  238.         // 计算容量是否足够,  
  239.         // 若“当前阀值容量 < 需要的容量”,则将容量x2。  
  240.         if (numKeysToBeAdded > threshold) {
  241.             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
  242.             if (targetCapacity > MAXIMUM_CAPACITY)
  243.                 targetCapacity = MAXIMUM_CAPACITY;
  244.             int newCapacity = table.length;
  245.             while (newCapacity < targetCapacity)
  246.                 newCapacity <<= 1;
  247.             if (newCapacity > table.length)
  248.                 resize(newCapacity);
  249.         }
  250.         // 通过迭代器,将“m”中的元素逐个添加到HashMap中。  
  251.         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
  252.             Map.Entry<? extends K, ? extends V> e = i.next();
  253.             put(e.getKey(), e.getValue());
  254.         }
  255.     }
  256.     // 删除“键为key”元素  
  257.     public V remove(Object key) {
  258.         Entry<K,V> e = removeEntryForKey(key);
  259.         return (e == null ? null : e.value);
  260.     }
  261.     // 删除“键为key”的元素  
  262.     final Entry<K,V> removeEntryForKey(Object key) {
  263.         // 获取哈希值。若key为null,则哈希值为0;否则调用hash()进行计算  
  264.         int hash = (key == null) ? 0 : hash(key.hashCode());
  265.         int i = indexFor(hash, table.length);
  266.         Entry<K,V> prev = table[i];
  267.         Entry<K,V> e = prev;
  268.         // 删除链表中“键为key”的元素  
  269.         // 本质是“删除单向链表中的节点”  
  270.         while (e != null) {
  271.             Entry<K,V> next = e.next;
  272.             Object k;
  273.             if (e.hash == hash &&
  274.                 ((k = e.key) == key || (key != null && key.equals(k)))) {
  275.                 modCount++;
  276.                 size--;
  277.                 if (prev == e)
  278.                     table[i] = next;
  279.                 else
  280.                     prev.next = next;
  281.                 e.recordRemoval(this);
  282.                 return e;
  283.             }
  284.             prev = e;
  285.             e = next;
  286.         }
  287.         return e;
  288.     }
  289.     // 删除“键值对”  
  290.     final Entry<K,V> removeMapping(Object o) {
  291.         if (!(o instanceof Map.Entry))
  292.             return null;
  293.         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
  294.         Object key = entry.getKey();
  295.         int hash = (key == null) ? 0 : hash(key.hashCode());
  296.         int i = indexFor(hash, table.length);
  297.         Entry<K,V> prev = table[i];
  298.         Entry<K,V> e = prev;
  299.         // 删除链表中的“键值对e”  
  300.         // 本质是“删除单向链表中的节点”  
  301.         while (e != null) {
  302.             Entry<K,V> next = e.next;
  303.             if (e.hash == hash && e.equals(entry)) {
  304.                 modCount++;
  305.                 size--;
  306.                 if (prev == e)
  307.                     table[i] = next;
  308.                 else
  309.                     prev.next = next;
  310.                 e.recordRemoval(this);
  311.                 return e;
  312.             }
  313.             prev = e;
  314.             e = next;
  315.         }
  316.         return e;
  317.     }
  318.     // 清空HashMap,将所有的元素设为null  
  319.     public void clear() {
  320.         modCount++;
  321.         Entry[] tab = table;
  322.         for (int i = 0; i < tab.length; i++)
  323.             tab[i] = null;
  324.         size = 0;
  325.     }
  326.     // 是否包含“值为value”的元素  
  327.     public boolean containsValue(Object value) {
  328.     // 若“value为null”,则调用containsNullValue()查找  
  329.     if (value == null)
  330.             return containsNullValue();
  331.     // 若“value不为null”,则查找HashMap中是否有值为value的节点。  
  332.     Entry[] tab = table;
  333.         for (int i = 0; i < tab.length ; i++)
  334.             for (Entry e = tab[i] ; e != null ; e = e.next)
  335.                 if (value.equals(e.value))
  336.                     return true;
  337.     return false;
  338.     }
  339.     // 是否包含null值  
  340.     private boolean containsNullValue() {
  341.     Entry[] tab = table;
  342.         for (int i = 0; i < tab.length ; i++)
  343.             for (Entry e = tab[i] ; e != null ; e = e.next)
  344.                 if (e.value == null)
  345.                     return true;
  346.     return false;
  347.     }
  348.     // 克隆一个HashMap,并返回Object对象  
  349.     public Object clone() {
  350.         HashMap<K,V> result = null;
  351.         try {
  352.             result = (HashMap<K,V>)super.clone();
  353.         } catch (CloneNotSupportedException e) {
  354.             // assert false;  
  355.         }
  356.         result.table = new Entry[table.length];
  357.         result.entrySet = null;
  358.         result.modCount = 0;
  359.         result.size = 0;
  360.         result.init();
  361.         // 调用putAllForCreate()将全部元素添加到HashMap中  
  362.         result.putAllForCreate(this);
  363.         return result;
  364.     }
  365.     // Entry是单向链表。  
  366.     // 它是 “HashMap链式存储法”对应的链表。  
  367.     // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
  368.     static class Entry<K,V> implements Map.Entry<K,V> {
  369.         final K key;
  370.         V value;
  371.         // 指向下一个节点  
  372.         Entry<K,V> next;
  373.         final int hash;
  374.         // 构造函数。  
  375.         // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"  
  376.         Entry(int h, K k, V v, Entry<K,V> n) {
  377.             value = v;
  378.             next = n;
  379.             key = k;
  380.             hash = h;
  381.         }
  382.         public final K getKey() {
  383.             return key;
  384.         }
  385.         public final V getValue() {
  386.             return value;
  387.         }
  388.         public final V setValue(V newValue) {
  389.             V oldValue = value;
  390.             value = newValue;
  391.             return oldValue;
  392.         }
  393.         // 判断两个Entry是否相等  
  394.         // 若两个Entry的“key”和“value”都相等,则返回true。  
  395.         // 否则,返回false  
  396.         public final boolean equals(Object o) {
  397.             if (!(o instanceof Map.Entry))
  398.                 return false;
  399.             Map.Entry e = (Map.Entry)o;
  400.             Object k1 = getKey();
  401.             Object k2 = e.getKey();
  402.             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  403.                 Object v1 = getValue();
  404.                 Object v2 = e.getValue();
  405.                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
  406.                     return true;
  407.             }
  408.             return false;
  409.         }
  410.         // 实现hashCode()  
  411.         public final int hashCode() {
  412.             return (key==null   ? 0 : key.hashCode()) ^
  413.                    (value==null ? 0 : value.hashCode());
  414.         }
  415.         public final String toString() {
  416.             return getKey() + "=" + getValue();
  417.         }
  418.         // 当向HashMap中添加元素时,绘调用recordAccess()。  
  419.         // 这里不做任何处理  
  420.         void recordAccess(HashMap<K,V> m) {
  421.         }
  422.         // 当从HashMap中删除元素时,绘调用recordRemoval()。  
  423.         // 这里不做任何处理  
  424.         void recordRemoval(HashMap<K,V> m) {
  425.         }
  426.     }
  427.     // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。  
  428.     void addEntry(int hash, K key, V value, int bucketIndex) {
  429.         // 保存“bucketIndex”位置的值到“e”中  
  430.         Entry<K,V> e = table[bucketIndex];
  431.         // 设置“bucketIndex”位置的元素为“新Entry”,  
  432.         // 设置“e”为“新Entry的下一个节点”  
  433.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  434.         // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小  
  435.         if (size++ >= threshold)
  436.             resize(2 * table.length);
  437.     }
  438.     // 创建Entry。将“key-value”插入指定位置。  
  439.     void createEntry(int hash, K key, V value, int bucketIndex) {
  440.         // 保存“bucketIndex”位置的值到“e”中  
  441.         Entry<K,V> e = table[bucketIndex];
  442.         // 设置“bucketIndex”位置的元素为“新Entry”,  
  443.         // 设置“e”为“新Entry的下一个节点”  
  444.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  445.         size++;
  446.     }
  447.     // HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。  
  448.     // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。  
  449.     private abstract class HashIterator<E> implements Iterator<E> {
  450.         // 下一个元素  
  451.         Entry<K,V> next;
  452.         // expectedModCount用于实现fast-fail机制。  
  453.         int expectedModCount;
  454.         // 当前索引  
  455.         int index;
  456.         // 当前元素  
  457.         Entry<K,V> current;
  458.         HashIterator() {
  459.             expectedModCount = modCount;
  460.             if (size > 0) { // advance to first entry  
  461.                 Entry[] t = table;
  462.                 // 将next指向table中第一个不为null的元素。  
  463.                 // 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。  
  464.                 while (index < t.length && (next = t[index++]) == null)
  465.                     ;
  466.             }
  467.         }
  468.         public final boolean hasNext() {
  469.             return next != null;
  470.         }
  471.         // 获取下一个元素  
  472.         final Entry<K,V> nextEntry() {
  473.             if (modCount != expectedModCount)
  474.                 throw new ConcurrentModificationException();
  475.             Entry<K,V> e = next;
  476.             if (e == null)
  477.                 throw new NoSuchElementException();
  478.             // 注意!!!  
  479.             // 一个Entry就是一个单向链表  
  480.             // 若该Entry的下一个节点不为空,就将next指向下一个节点;  
  481.             // 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。  
  482.             if ((next = e.next) == null) {
  483.                 Entry[] t = table;
  484.                 while (index < t.length && (next = t[index++]) == null)
  485.                     ;
  486.             }
  487.             current = e;
  488.             return e;
  489.         }
  490.         // 删除当前元素  
  491.         public void remove() {
  492.             if (current == null)
  493.                 throw new IllegalStateException();
  494.             if (modCount != expectedModCount)
  495.                 throw new ConcurrentModificationException();
  496.             Object k = current.key;
  497.             current = null;
  498.             HashMap.this.removeEntryForKey(k);
  499.             expectedModCount = modCount;
  500.         }
  501.     }
  502.     // value的迭代器  
  503.     private final class ValueIterator extends HashIterator<V> {
  504.         public V next() {
  505.             return nextEntry().value;
  506.         }
  507.     }
  508.     // key的迭代器  
  509.     private final class KeyIterator extends HashIterator<K> {
  510.         public K next() {
  511.             return nextEntry().getKey();
  512.         }
  513.     }
  514.     // Entry的迭代器  
  515.     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
  516.         public Map.Entry<K,V> next() {
  517.             return nextEntry();
  518.         }
  519.     }
  520.     // 返回一个“key迭代器”  
  521.     Iterator<K> newKeyIterator()   {
  522.         return new KeyIterator();
  523.     }
  524.     // 返回一个“value迭代器”  
  525.     Iterator<V> newValueIterator()   {
  526.         return new ValueIterator();
  527.     }
  528.     // 返回一个“entry迭代器”  
  529.     Iterator<Map.Entry<K,V>> newEntryIterator()   {
  530.         return new EntryIterator();
  531.     }
  532.     // HashMap的Entry对应的集合  
  533.     private transient Set<Map.Entry<K,V>> entrySet = null;
  534.     // 返回“key的集合”,实际上返回一个“KeySet对象”  
  535.     public Set<K> keySet() {
  536.         Set<K> ks = keySet;
  537.         return (ks != null ? ks : (keySet = new KeySet()));
  538.     }
  539.     // Key对应的集合  
  540.     // KeySet继承于AbstractSet,说明该集合中没有重复的Key。  
  541.     private final class KeySet extends AbstractSet<K> {
  542.         public Iterator<K> iterator() {
  543.             return newKeyIterator();
  544.         }
  545.         public int size() {
  546.             return size;
  547.         }
  548.         public boolean contains(Object o) {
  549.             return containsKey(o);
  550.         }
  551.         public boolean remove(Object o) {
  552.             return HashMap.this.removeEntryForKey(o) != null;
  553.         }
  554.         public void clear() {
  555.             HashMap.this.clear();
  556.         }
  557.     }
  558.     // 返回“value集合”,实际上返回的是一个Values对象  
  559.     public Collection<V> values() {
  560.         Collection<V> vs = values;
  561.         return (vs != null ? vs : (values = new Values()));
  562.     }
  563.     // “value集合”  
  564.     // Values继承于AbstractCollection,不同于“KeySet继承于AbstractSet”,  
  565.     // Values中的元素能够重复。因为不同的key可以指向相同的value。  
  566.     private final class Values extends AbstractCollection<V> {
  567.         public Iterator<V> iterator() {
  568.             return newValueIterator();
  569.         }
  570.         public int size() {
  571.             return size;
  572.         }
  573.         public boolean contains(Object o) {
  574.             return containsValue(o);
  575.         }
  576.         public void clear() {
  577.             HashMap.this.clear();
  578.         }
  579.     }
  580.     // 返回“HashMap的Entry集合”  
  581.     public Set<Map.Entry<K,V>> entrySet() {
  582.         return entrySet0();
  583.     }
  584.     // 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象  
  585.     private Set<Map.Entry<K,V>> entrySet0() {
  586.         Set<Map.Entry<K,V>> es = entrySet;
  587.         return es != null ? es : (entrySet = new EntrySet());
  588.     }
  589.     // EntrySet对应的集合  
  590.     // EntrySet继承于AbstractSet,说明该集合中没有重复的EntrySet。  
  591.     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
  592.         public Iterator<Map.Entry<K,V>> iterator() {
  593.             return newEntryIterator();
  594.         }
  595.         public boolean contains(Object o) {
  596.             if (!(o instanceof Map.Entry))
  597.                 return false;
  598.             Map.Entry<K,V> e = (Map.Entry<K,V>) o;
  599.             Entry<K,V> candidate = getEntry(e.getKey());
  600.             return candidate != null && candidate.equals(e);
  601.         }
  602.         public boolean remove(Object o) {
  603.             return removeMapping(o) != null;
  604.         }
  605.         public int size() {
  606.             return size;
  607.         }
  608.         public void clear() {
  609.             HashMap.this.clear();
  610.         }
  611.     }
  612.     // java.io.Serializable的写入函数  
  613.     // 将HashMap的“总的容量,实际容量,所有的Entry”都写入到输出流中  
  614.     private void writeObject(java.io.ObjectOutputStream s)
  615.         throws IOException
  616.     {
  617.         Iterator<Map.Entry<K,V>> i =
  618.             (size > 0) ? entrySet0().iterator() : null;
  619.         // Write out the threshold, loadfactor, and any hidden stuff  
  620.         s.defaultWriteObject();
  621.         // Write out number of buckets  
  622.         s.writeInt(table.length);
  623.         // Write out size (number of Mappings)  
  624.         s.writeInt(size);
  625.         // Write out keys and values (alternating)  
  626.         if (i != null) {
  627.             while (i.hasNext()) {
  628.             Map.Entry<K,V> e = i.next();
  629.             s.writeObject(e.getKey());
  630.             s.writeObject(e.getValue());
  631.             }
  632.         }
  633.     }
  634.     private static final long serialVersionUID = 362498820763181265L;
  635.     // java.io.Serializable的读取函数:根据写入方式读出  
  636.     // 将HashMap的“总的容量,实际容量,所有的Entry”依次读出  
  637.     private void readObject(java.io.ObjectInputStream s)
  638.          throws IOException, ClassNotFoundException
  639.     {
  640.         // Read in the threshold, loadfactor, and any hidden stuff  
  641.         s.defaultReadObject();
  642.         // Read in number of buckets and allocate the bucket array;  
  643.         int numBuckets = s.readInt();
  644.         table = new Entry[numBuckets];
  645.         init();  // Give subclass a chance to do its thing.  
  646.         // Read in size (number of Mappings)  
  647.         int size = s.readInt();
  648.         // Read the keys and values, and put the mappings in the HashMap  
  649.         for (int i=0; i<size; i++) {
  650.             K key = (K) s.readObject();
  651.             V value = (V) s.readObject();
  652.             putForCreate(key, value);
  653.         }
  654.     }
  655.     // 返回“HashMap总的容量”  
  656.     int   capacity()     { return table.length; }
  657.     // 返回“HashMap的加载因子”  
  658.     float loadFactor()   { return loadFactor;   }
  659. }

 

几点总结

1、首先要清楚HashMap的存储结构,如下图所示:

图中,紫色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。

2、首先看链表中节点的数据结构:

  1. // Entry是单向链表。  
  2. // 它是 “HashMap链式存储法”对应的链表。  
  3. // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
  4. static class Entry<K,V> implements Map.Entry<K,V> {
  5.     final K key;
  6.     V value;
  7.     // 指向下一个节点  
  8.     Entry<K,V> next;
  9.     final int hash;
  10.     // 构造函数。  
  11.     // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"  
  12.     Entry(int h, K k, V v, Entry<K,V> n) {
  13.         value = v;
  14.         next = n;
  15.         key = k;
  16.         hash = h;
  17.     }
  18.     public final K getKey() {
  19.         return key;
  20.     }
  21.     public final V getValue() {
  22.         return value;
  23.     }
  24.     public final V setValue(V newValue) {
  25.         V oldValue = value;
  26.         value = newValue;
  27.         return oldValue;
  28.     }
  29.     // 判断两个Entry是否相等  
  30.     // 若两个Entry的“key”和“value”都相等,则返回true。  
  31.     // 否则,返回false  
  32.     public final boolean equals(Object o) {
  33.         if (!(o instanceof Map.Entry))
  34.             return false;
  35.         Map.Entry e = (Map.Entry)o;
  36.         Object k1 = getKey();
  37.         Object k2 = e.getKey();
  38.         if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  39.             Object v1 = getValue();
  40.             Object v2 = e.getValue();
  41.             if (v1 == v2 || (v1 != null && v1.equals(v2)))
  42.                 return true;
  43.         }
  44.         return false;
  45.     }
  46.     // 实现hashCode()  
  47.     public final int hashCode() {
  48.         return (key==null   ? 0 : key.hashCode()) ^
  49.                (value==null ? 0 : value.hashCode());
  50.     }
  51.     public final String toString() {
  52.         return getKey() + "=" + getValue();
  53.     }
  54.     // 当向HashMap中添加元素时,绘调用recordAccess()。  
  55.     // 这里不做任何处理  
  56.     void recordAccess(HashMap<K,V> m) {
  57.     }
  58.     // 当从HashMap中删除元素时,绘调用recordRemoval()。  
  59.     // 这里不做任何处理  
  60.     void recordRemoval(HashMap<K,V> m) {
  61.     }
  62. }

它的结构元素除了key、value、hash外,还有next,next指向下一个节点。另外,这里覆写了equals和hashCode方法来保证键值对的独一无二。

3、HashMap共有四个构造方法。构造方法中提到了两个很重要的参数:初始容量和加载因子。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中槽的数量(即哈希数组的长度),初始容量是创建哈希表时的容量(从构造函数中可以看出,如果不指明,则默认为16),加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。

下面说下加载因子,如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。

另外,无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方

4、HashMap中key和value都允许为null。

5、要重点分析下HashMap中用的最多的两个方法put和get。先从比较简单的get方法着手,源码如下:

  1. // 获取key对应的value  
  2. public V get(Object key) {
  3.     if (key == null)
  4.         return getForNullKey();
  5.     // 获取key的hash值  
  6.     int hash = hash(key.hashCode());
  7.     // 在“该hash值对应的链表”上查找“键值等于key”的元素  
  8.     for (Entry<K,V> e = table[indexFor(hash, table.length)];
  9.          e != null;
  10.          e = e.next) {
  11.         Object k;
  12. /判断key是否相同
  13.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  14.             return e.value;
  15.     }
  16. 没找到则返回null
  17.     return null;
  18. }
  19. // 获取“key为null”的元素的值  
  20. // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!  
  21. private V getForNullKey() {
  22.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  23.         if (e.key == null)
  24.             return e.value;
  25.     }
  26.     return null;
  27. }

首先,如果key为null,则直接从哈希表的第一个位置table[0]对应的链表上查找。记住,key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。

如果key不为null,则先求的key的hash值,根据hash值找到在table中的索引,在该索引对应的单链表中查找是否有键值对的key与目标key相等,有就返回对应的value,没有则返回null。

put方法稍微复杂些,代码如下:

  1.   // 将“key-value”添加到HashMap中  
  2.   public V put(K key, V value) {
  3.       // 若“key为null”,则将该键值对添加到table[0]中。  
  4.       if (key == null)
  5.           return putForNullKey(value);
  6.       // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。  
  7.       int hash = hash(key.hashCode());
  8.       int i = indexFor(hash, table.length);
  9.       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  10.           Object k;
  11.           // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!  
  12.           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  13.               V oldValue = e.value;
  14.               e.value = value;
  15.               e.recordAccess(this);
  16.               return oldValue;
  17.           }
  18.       }
  19.       // 若“该key”对应的键值对不存在,则将“key-value”添加到table中  
  20.       modCount++;
  21. //将key-value添加到table[i]处
  22.       addEntry(hash, key, value, i);
  23.       return null;
  24.   }

如果key为null,则将其添加到table[0]对应的链表中,putForNullKey的源码如下:

  1. // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置  
  2. private V putForNullKey(V value) {
  3.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  4.         if (e.key == null) {
  5.             V oldValue = e.value;
  6.             e.value = value;
  7.             e.recordAccess(this);
  8.             return oldValue;
  9.         }
  10.     }
  11.     // 如果没有存在key为null的键值对,则直接题阿见到table[0]处!  
  12.     modCount++;
  13.     addEntry(0null, value, 0);
  14.     return null;
  15. }

如果key不为null,则同样先求出key的hash值,根据hash值得出在table中的索引,而后遍历对应的单链表,如果单链表中存在与目标key相等的键值对,则将新的value覆盖旧的value,比将旧的value返回,如果找不到与目标key相等的键值对,或者该单链表为空,则将该键值对插入到改单链表的头结点位置(每次新插入的节点都是放在头结点的位置),该操作是有addEntry方法实现的,它的源码如下:

  1. // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。  
  2. void addEntry(int hash, K key, V value, int bucketIndex) {
  3.     // 保存“bucketIndex”位置的值到“e”中  
  4.     Entry<K,V> e = table[bucketIndex];
  5.     // 设置“bucketIndex”位置的元素为“新Entry”,  
  6.     // 设置“e”为“新Entry的下一个节点”  
  7.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  8.     // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小  
  9.     if (size++ >= threshold)
  10.         resize(2 * table.length);
  11. }

注意这里倒数第三行的构造方法,将key-value键值对赋给table[bucketIndex],并将其next指向元素e,这便将key-value放到了头结点中,并将之前的头结点接在了它的后面。该方法也说明,每次put键值对的时候,总是将新的该键值对放在table[bucketIndex]处(即头结点处)。

两外注意最后两行代码,每次加入键值对时,都要判断当前已用的槽的数目是否大于等于阀值(容量*加载因子),如果大于等于,则进行扩容,将容量扩为原来容量的2倍。

6、关于扩容。上面我们看到了扩容的方法,resize方法,它的源码如下:

  1. // 重新调整HashMap的大小,newCapacity是调整后的单位  
  2. void resize(int newCapacity) {
  3.     Entry[] oldTable = table;
  4.     int oldCapacity = oldTable.length;
  5.     if (oldCapacity == MAXIMUM_CAPACITY) {
  6.         threshold = Integer.MAX_VALUE;
  7.         return;
  8.     }
  9.     // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,  
  10.     // 然后,将“新HashMap”赋值给“旧HashMap”。  
  11.     Entry[] newTable = new Entry[newCapacity];
  12.     transfer(newTable);
  13.     table = newTable;
  14.     threshold = (int)(newCapacity * loadFactor);
  15. }

很明显,是新建了一个HashMap的底层数组,而后调用transfer方法,将就HashMap的全部元素添加到新的HashMap中(要重新计算元素在新的数组中的索引位置)。transfer方法的源码如下:

  1. // 将HashMap中的全部元素都添加到newTable中  
  2. void transfer(Entry[] newTable) {
  3.     Entry[] src = table;
  4.     int newCapacity = newTable.length;
  5.     for (int j = 0; j < src.length; j++) {
  6.         Entry<K,V> e = src[j];
  7.         if (e != null) {
  8.             src[j] = null;
  9.             do {
  10.                 Entry<K,V> next = e.next;
  11.                 int i = indexFor(e.hash, newCapacity);
  12.                 e.next = newTable[i];
  13.                 newTable[i] = e;
  14.                 e = next;
  15.             } while (e != null);
  16.         }
  17.     }
  18. }

很明显,扩容是一个相当耗时的操作,因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此,我们在用HashMap的时,最好能提前预估下HashMap中元素的个数,这样有助于提高HashMap的性能。

7、注意containsKey方法和containsValue方法。前者直接可以通过key的哈希值将搜索范围定位到指定索引对应的链表,而后者要对哈希数组的每个链表进行搜索。

8、我们重点来分析下求hash值和索引值的方法,这两个方法便是HashMap设计的最为核心的部分,二者结合能保证哈希表中的元素尽可能均匀地散列。

计算哈希值的方法如下:

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

它只是一个数学公式,IDK这样设计对hash值的计算,自然有它的好处,至于为什么这样设计,我们这里不去追究,只要明白一点,用的位的操作使hash值的计算效率很高。

由hash值找到对应索引的方法如下:

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

这个我们要重点说下,我们一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法),Hashtable中也是这样实现的,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低,HashMap中则通过h&(length-1)的方法来代替取模,同样实现了均匀的散列,但效率要高很多,这也是HashMap对Hashtable的一个改进。

接下来,我们分析下为什么哈希表的容量一定要是2的整数次幂。首先,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率;其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。

发表评论

电子邮件地址不会被公开。 必填项已用*标注