JDK1.8源码hashMap

一、概念

允许key为null，value为null；线程不安全；不保证映射的顺序；迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例；HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数；加载因子默认是0.75；存储过多的相同的key，降低hash table性能；

线程不安全的，想要线程安全，最好的方法是在创建的时候使用下面方法：

1  Map m = Collections.synchronizedMap(new HashMap(...));

关于迭代器和LinkedList一样！

JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题！

二、属性和构造方法：

  1 public class HashMap<K,V> extends AbstractMap<K,V>
  2     implements Map<K,V>, Cloneable, Serializable {
  3 
  4     private static final long serialVersionUID = 362498820763181265L;
  5 
  6     /**
  7      * The default initial capacity - MUST be a power of two.
  8      */
  9     //默认初始容量-必须是2的指数。2的4次方=16次方
 10     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 11 
 12     /**
 13      * The maximum capacity, used if a higher value is implicitly specified
 14      * by either of the constructors with arguments.
 15      * MUST be a power of two <= 1<<30.
 16      */
 17     //最大容量，2的30次方=1073741824
 18     static final int MAXIMUM_CAPACITY = 1 << 30;
 19 
 20     /**
 21      * The load factor used when none specified in constructor.
 22      */
 23     //负载系数=0.75
 24     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 25 
 26     /**
 27      * The bin count threshold for using a tree rather than list for a
 28      * bin.  Bins are converted to trees when adding an element to a
 29      * bin with at least this many nodes. The value must be greater
 30      * than 2 and should be at least 8 to mesh with assumptions in
 31      * tree removal about conversion back to plain bins upon
 32      * shrinkage.
 33      */
 34     //一个桶的树化阈值：8，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
 35     static final int TREEIFY_THRESHOLD = 8;
 36 
 37     /**
 38      * The bin count threshold for untreeifying a (split) bin during a
 39      * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 40      * most 6 to mesh with shrinkage detection under removal.
 41      */
 42     //一个树的链表还原阈值：6，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
 43     static final int UNTREEIFY_THRESHOLD = 6;
 44 
 45     /**
 46      * The smallest table capacity for which bins may be treeified.
 47      * (Otherwise the table is resized if too many nodes in a bin.)
 48      * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 49      * between resizing and treeification thresholds.
 50      */
 51     //hash表的最小树形化容量：64，1，当哈希表中的容量大于这个值时，表中的桶才能进行树形化；否则桶内元素太多时会扩容，而不是树形化，
        //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
 52     static final int MIN_TREEIFY_CAPACITY = 64;
 53 
 54     static class Node<K,V> implements Map.Entry<K,V> {
 55         final int hash; //对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
 56         final K key;
 57         V value;
 58         Node<K,V> next; //存储指向下一个Entry的引用，单链表结构
 59 
 60         Node(int hash, K key, V value, Node<K,V> next) {
 61             this.hash = hash;
 62             this.key = key;
 63             this.value = value;
 64             this.next = next;
 65         }
 66 
 67         public final K getKey()        { return key; }
 68         public final V getValue()      { return value; }
 69         public final String toString() { return key + "=" + value; }
 70 
 71         public final int hashCode() {
 72             return Objects.hashCode(key) ^ Objects.hashCode(value);
 73         }
 74 
 75         public final V setValue(V newValue) {
 76             V oldValue = value;
 77             value = newValue;
 78             return oldValue;
 79         }
 80 
 81         public final boolean equals(Object o) {
 82             if (o == this)
 83                 return true;
 84             if (o instanceof Map.Entry) {
 85                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 86                 if (Objects.equals(key, e.getKey()) &&
 87                     Objects.equals(value, e.getValue()))
 88                     return true;
 89             }
 90             return false;
 91         }
 92     }
 93 
 94     //key的hash值
 95     static final int hash(Object key) {
 96         int h;
 97         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 98     }
 99 
100     /**
101      * Returns x's Class if it is of the form "class C implements
102      * Comparable<C>", else null.
103      */
104     static Class<?> comparableClassFor(Object x) {
105         if (x instanceof Comparable) {
106             Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
107             if ((c = x.getClass()) == String.class) // bypass checks
108                 return c;
109             if ((ts = c.getGenericInterfaces()) != null) {
110                 for (int i = 0; i < ts.length; ++i) {
111                     if (((t = ts[i]) instanceof ParameterizedType) &&
112                         ((p = (ParameterizedType)t).getRawType() ==
113                          Comparable.class) &&
114                         (as = p.getActualTypeArguments()) != null &&
115                         as.length == 1 && as[0] == c) // type arg is c
116                         return c;
117                 }
118             }
119         }
120         return null;
121     }
122 
123     /**
124      * Returns k.compareTo(x) if x matches kc (k's screened comparable
125      * class), else 0.
126      */
127     @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
128     static int compareComparables(Class<?> kc, Object k, Object x) {
129         return (x == null || x.getClass() != kc ? 0 :
130                 ((Comparable)k).compareTo(x));
131     }
132 
133     /**
134      * Returns a power of two size for the given target capacity.
135      */
136     //返回给定的容量的2的指数
137     static final int tableSizeFor(int cap) {
138         int n = cap - 1;
139         n |= n >>> 1;
140         n |= n >>> 2;
141         n |= n >>> 4;
142         n |= n >>> 8;
143         n |= n >>> 16;
144         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
145     }
146 
147     /* ---------------- Fields -------------- */
148 
149     /**
150      * The table, initialized on first use, and resized as
151      * necessary. When allocated, length is always a power of two.
152      * (We also tolerate length zero in some operations to allow
153      * bootstrapping mechanics that are currently not needed.)
154      */
155     //初始化数组 
156     transient Node<K,V>[] table;
157 
158     /**
159      * Holds cached entrySet(). Note that AbstractMap fields are used
160      * for keySet() and values().
161      */
162     transient Set<Map.Entry<K,V>> entrySet;
163 
164     /**
165      * The number of key-value mappings contained in this map.
166      */
167     //实际存储的key-value键值对的个数 
168     transient int size;
169 
170     /**
171      * The number of times this HashMap has been structurally modified
172      * Structural modifications are those that change the number of mappings in
173      * the HashMap or otherwise modify its internal structure (e.g.,
174      * rehash).  This field is used to make iterators on Collection-views of
175      * the HashMap fail-fast.  (See ConcurrentModificationException).
176      */
177     transient int modCount;
178 
179     /**
180      * The next size value at which to resize (capacity * load factor).
181      *
182      * @serial
183      */
184     // (The javadoc description is true upon serialization.
185     // Additionally, if the table array has not been allocated, this
186     // field holds the initial array capacity, or zero signifying
187     // DEFAULT_INITIAL_CAPACITY.)
188     //阈值，当table == {}时，该值为初始容量（初始容量默认为16）；
189     //当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。
190     int threshold;
191 
192     //负载系数,代表了table的填充度有多少，默认是0.75
193     final float loadFactor;
194 
195     //创建一个空的HashMap用指定的容量和负载系数
196     public HashMap(int initialCapacity, float loadFactor) {
197         if (initialCapacity < 0)
198             throw new IllegalArgumentException("Illegal initial capacity: " +
199                                                initialCapacity);
200         if (initialCapacity > MAXIMUM_CAPACITY)//不能大于最大值
201             initialCapacity = MAXIMUM_CAPACITY;
202         if (loadFactor <= 0 || Float.isNaN(loadFactor))
203             throw new IllegalArgumentException("Illegal load factor: " +
204                                                loadFactor);
205         this.loadFactor = loadFactor;
206         this.threshold = tableSizeFor(initialCapacity);
207     }
208 
209     //创建一个空的HashMap用指定的容量和默认的负载系数（0.75） 
210     public HashMap(int initialCapacity) {
211         this(initialCapacity, DEFAULT_LOAD_FACTOR);
212     }
213 
214     //创建一个空的HashMap用默认的容量（16）和默认的负载系数（0.75）  
215     public HashMap() {
216         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
217     }
218 
219     /**
220      * Constructs a new <tt>HashMap</tt> with the same mappings as the
221      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
222      * default load factor (0.75) and an initial capacity sufficient to
223      * hold the mappings in the specified <tt>Map</tt>.
224      *
225      * @param   m the map whose mappings are to be placed in this map
226      * @throws  NullPointerException if the specified map is null
227      */
228     public HashMap(Map<? extends K, ? extends V> m) {
229         this.loadFactor = DEFAULT_LOAD_FACTOR;
230         putMapEntries(m, false);
231     }

三、扩容机制

put方法和resize()方法：

关于扩容的理解可以参考博文：https://blog.csdn.net/qq_27093465/article/details/52270519

https://blog.csdn.net/u013494765/article/details/77837338

https://www.cnblogs.com/chengxiao/p/6059914.html

我理解为什么HashMap的数组长度一定是2的次幂？很大一部分原因是：为了均匀分布table数据和充分利用空间，减少hash冲突，快速查询

  1    /**
  2      * Implements Map.putAll and Map constructor
  3      *
  4      * @param m the map
  5      * @param evict false when initially constructing this map, else
  6      * true (relayed to method afterNodeInsertion).
  7      */
  8     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  9         int s = m.size();
 10         if (s > 0) {
 11             if (table == null) { // pre-size 数组是空
 12                 float ft = ((float)s / loadFactor) + 1.0F;
 13                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 14                          (int)ft : MAXIMUM_CAPACITY);
 15                 if (t > threshold)//大于map的实际可容量就扩大
 16                     threshold = tableSizeFor(t);
 17             }
 18             else if (s > threshold)
 19                 resize(); //扩容
 20             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 21                 K key = e.getKey();
 22                 V value = e.getValue();
 23                 putVal(hash(key), key, value, false, evict);
 24             }
 25         }
 26     }
 27     
 28       /**
 29      * Associates the specified value with the specified key in this map.
 30      * If the map previously contained a mapping for the key, the old
 31      * value is replaced.
 32      *
 33      * @param key key with which the specified value is to be associated
 34      * @param value value to be associated with the specified key
 35      * @return the previous value associated with <tt>key</tt>, or
 36      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 37      *         (A <tt>null</tt> return can also indicate that the map
 38      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 39      */
 40     public V put(K key, V value) {
 41         return putVal(hash(key), key, value, false, true);
 42     }
 43     
 44       /**
 45      * Implements Map.put and related methods
 46      *
 47      * @param hash hash for key
 48      * @param key the key
 49      * @param value the value to put
 50      * @param onlyIfAbsent if true, don't change existing value
 51      * @param evict if false, the table is in creation mode.
 52      * @return previous value, or null if none
 53      */
 54      
 55     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 56                    boolean evict) {
 57         Node<K,V>[] tab; Node<K,V> p; int n, i;
 58         if ((tab = table) == null || (n = tab.length) == 0) //数组未初始化
 59             n = (tab = resize()).length;  //数组设置初始值
 60         if ((p = tab[i = (n - 1) & hash]) == null) //计算脚标i，数组[i]是否是null，(n - 1) & hash计量把数组分布均匀的填满
 61             tab[i] = newNode(hash, key, value, null); //将key，value放到数组[i]
 62         else { //hash冲突时
 63             Node<K,V> e; K k;
 64             if (p.hash == hash &&
 65                 ((k = p.key) == key || (key != null && key.equals(k)))) //判断key是否是同一个key
 66                 e = p;
 67             else if (p instanceof TreeNode) //如果是tree节点 
 68                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 69             else {
 70                 for (int binCount = 0; ; ++binCount) {
 71                     if ((e = p.next) == null) {
 72                         //在链表头部插入key，value
 73                         p.next = newNode(hash, key, value, null);
 74                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 75                             treeifyBin(tab, hash);
 76                         break;
 77                     }
 78                     if (e.hash == hash &&
 79                         ((k = e.key) == key || (key != null && key.equals(k))))
 80                         break;
 81                     p = e;
 82                 }
 83             }
 84             if (e != null) { // existing mapping for key
 85                 V oldValue = e.value;
 86                 if (!onlyIfAbsent || oldValue == null)
 87                     e.value = value;
 88                 afterNodeAccess(e);
 89                 return oldValue;
 90             }
 91         }
 92         ++modCount;
 93         if (++size > threshold)
 94             resize();
 95         afterNodeInsertion(evict);
 96         return null;
 97     }
 98     
 99       /**
100      * Initializes or doubles table size.  If null, allocates in
101      * accord with initial capacity target held in field threshold.
102      * Otherwise, because we are using power-of-two expansion, the
103      * elements from each bin must either stay at same index, or move
104      * with a power of two offset in the new table.
105      *
106      * @return the table
107      */
108     //以默认容量大小16，默认负载系数0.75为例
109     final Node<K,V>[] resize() {
110         Node<K,V>[] oldTab = table;//原数组
111         int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组长度 16
112         int oldThr = threshold;//原临界值 12
113         int newCap, newThr = 0;
114         if (oldCap > 0) {
115             if (oldCap >= MAXIMUM_CAPACITY) {//原数组长度大于最大容量(1073741824) 
116                 //则将threshold设为Integer.MAX_VALUE=2147483647，接近MAXIMUM_CAPACITY的两倍
117                 threshold = Integer.MAX_VALUE;
118                 return oldTab;
119             }            
120             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  //newCap=32
121                      oldCap >= DEFAULT_INITIAL_CAPACITY)
122                      // 新数组长度 是原数组长度的2倍，
123                 newThr = oldThr << 1; // double threshold 临界值也扩大为原来2倍 24
124         }
125         else if (oldThr > 0) // initial capacity was placed in threshold
126             newCap = oldThr;
127         else {               // zero initial threshold signifies using defaults
128             newCap = DEFAULT_INITIAL_CAPACITY;
129             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
130         }
131         if (newThr == 0) {
132             float ft = (float)newCap * loadFactor;
133             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
134                       (int)ft : Integer.MAX_VALUE);
135         }
136         threshold = newThr; //新临界值 24
137         @SuppressWarnings({"rawtypes","unchecked"})
138             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建以长度32的新数组
139         table = newTab;
140         //如果原来数组有数据，则将原数据复制到新数组中
141         if (oldTab != null) {
142             // 根据容量进行循环整个数组，将非空元素进行复制
143             for (int j = 0; j < oldCap; ++j) {
144                 Node<K,V> e;
145                 // 获取数组的第j个元素
146                 if ((e = oldTab[j]) != null) {
147                     oldTab[j] = null; //原数组j位置置为null，交给GC
148                     // 如果链表只有一个，则进行直接赋值
149                     if (e.next == null)
150                         // e.hash & (newCap - 1) 确定元素存放位置
151                         newTab[e.hash & (newCap - 1)] = e;
152                     else if (e instanceof TreeNode)
153                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
154                     else { // preserve order
155                         Node<K,V> loHead = null, loTail = null;
156                         Node<K,V> hiHead = null, hiTail = null;
157                         Node<K,V> next;
158                         do {
159                             next = e.next;
160                             if ((e.hash & oldCap) == 0) {
161                                 if (loTail == null)
162                                     loHead = e;
163                                 else
164                                     loTail.next = e;
165                                 loTail = e;
166                             }
167                             else {
168                                 if (hiTail == null)
169                                     hiHead = e;
170                                 else
171                                     hiTail.next = e;
172                                 hiTail = e;
173                             }
174                         } while ((e = next) != null);
175                         if (loTail != null) {
176                             loTail.next = null;
177                             newTab[j] = loHead;
178                         }
179                         if (hiTail != null) {
180                             hiTail.next = null;
181                             newTab[j + oldCap] = hiHead;
182                         }
183                     }
184                 }
185             }
186         }
187         return newTab;
188     }

剩下的一些方法：

putIfAbsent：value不为空并且不改变现存的值

computeIfAbsent：如果key已存在，返回oldVlaue；不存在创建，返回新创建value

computeIfPresent：如果key不存在，返回null；如果已存在，value为null则删除此节点，不为null替换节点value并返回此value。

compute：如果key不存在，新建key进行存储；如果key存在，value为null则删除此节点，不为null替换节点value并返回此value。