在秋招面试准备中博主找过很多关于HashMap的博客，但是秋招结束后回过头来看，感觉没有一篇全面、通俗易懂的讲解HashMap文章（可能是博主没有找到），所以在秋招结束后，写下了这篇文章，尽最大的努力把HashMap源码讲解的通俗易懂，并且尽量涵盖面试中HashMap的考察点。
就博主的经历来看，HashMap是求职面试中名副其实的“明星”，基本上博主面试的每一家公司多多少少都有问到HashMap的底层实现原理等一些相关问题。
这篇文章将会按以下顺序来组织：
HashMap源码分析（JDK8，通俗易懂）
HashMap面试“明星”问题汇总，以及明星问题答案
下面是JDK8中HashMap的源码分析：
注：下文源码分析中，
注释多少与重要性成正比
注释多少与重要性成正比
注释多少与重要性成正比
HashMap的成员属性源码分析
1public 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 * The default initial capacity - MUST be a power of two. 7 */ 8 9 //HashMap的初始容量为16，HashMap的容量指的是存储元素的数组大小，即桶的数量 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 18 //HashMap的最大的容量 19 static final int MAXIMUM_CAPACITY = 1 << 30; 20 21 /** 22 * The load factor used when none specified in constructor. 23 */ 24 25 /** 26 * DEFAULT_LOAD_FACTOR:HashMap的负载因子，影响HashMap性能的参数之一，是时间和空间之间的权 27 * 衡，后面会看到HashMap的元素存储在Node数组中，这个数组的大小这里称为“桶”的大小. 28 * 另外还有一个参数size指的是我们往HashMap中put了多少个元素。 29 * 当size==桶的数量*DEFAULT_LOAD_FACTOR的时候，这时HashMap要进行扩容操作，也就是桶不能装 30 * 满。DEFAULT_LOAD_FACTOR是衡量桶的利用率:DEFAULT_LOAD_FACTOR较小时（桶的利用率较小）, 31 * 这时浪费的空间较多（因为只能存储桶的数量*DEFAULT_LOAD_FACTOR个元素，超过了就要进行扩容）, 32 * 这种情况下往HashMap中put元素时发生冲突的概率也很小，所谓冲突指的是：多个元素被put到了同一个桶 中; 33 * 冲突小时（可以认为一个桶中只有一个元素）put、get等HashMap的操作代价就很低，可以认为是O(1); 34 * 桶的利用率较大的时候(DEFAULT_LOAD_FACTOR很大，注意可以大于1，因为冲突的元素是使用链表或者 红黑树连接起来的) 35 * 空间利用率较高， 36 * 这也意味着一个桶中存储了很多元素，这时HashMap的put、get等操作代价就相对较大，因为每一个put或get操作都变成了 37 * 对链表或者红黑树的操作，代价肯定大于O(1),所以说DEFAULT_LOAD_FACTOR是空间和时间的一个平衡点; 38 * DEFAULT_LOAD_FACTOR较小时，需要的空间较大，但是put和get的代价较小; 39 * DEFAULT_LOAD_FACTOR较大时，需要的空间较小，但是put和get的代价较大）。 40 * 41 * 扩容操作就是把桶的数量*2，即把Node数组的大小调整为扩容前的2倍，至于为什么是两倍，分析扩容函 数时会讲解， 42 * 这其实是一个trick。Node数组中每一个桶中存储的是Node链表，当链表长度>=8的时候， 43 * 链表会变为红黑树结构（因为红黑树的增删改查复杂度是logn，链表是n，红黑树结构比链表代价更小）。 44 */ 45 static final float DEFAULT_LOAD_FACTOR = 0.75f; 46 47 /** 48 * The bin count threshold for using a tree rather than list for a 49 * bin. Bins are converted to trees when adding an element to a 50 * bin with at least this many nodes. The value must be greater 51 * than 2 and should be at least 8 to mesh with assumptions in 52 * tree removal about conversion back to plain bins upon 53 * shrinkage. 54 */ 55 //当某一个桶中链表的长度>=8时，链表结构会转换成红黑树结构（其实还要求桶的中数量>=64,后面会提到） 56 static final int TREEIFY_THRESHOLD = 8; 57 58 /** 59 * The bin count threshold for untreeifying a (split) bin during a 60 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 61 * most 6 to mesh with shrinkage detection under removal. 62 */ 63 //当红黑树中的节点数量<=6时，红黑树结构会转变为链表结构 64 static final int UNTREEIFY_THRESHOLD = 6; 65 66 /** 67 * The smallest table capacity for which bins may be treeified. 68 * (Otherwise the table is resized if too many nodes in a bin.) 69 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts 70 * between resizing and treeification thresholds. 71 */ 72 //上面提到的：当Node数组容量>=64的前提下，如果某一个桶中链表长度>=8，则会将链表结构转换成 73 //红黑树结构 74 static final int MIN_TREEIFY_CAPACITY = 64; 75 76}
HashMap内部类——Node源码分析
下面介绍HashMap的内部类Node，HashMap的所有数据都保存在Node数组中那么这个Node到底是个什么东西呢？
1//Node是HashMap的内部类 2static class Node<K,V> implements Map.Entry<K,V> { 3 //保存key的hashcode=key的hashcode ^ (key的hashcode>>>16)这样做主要是为了减少hash冲突 4 //当我们往map中put(k,v)时，这个k,v键值对会被封装为Node，那么这个Node放在Node数组的哪个 5 //位置呢：index=hash&(n-1),n为Node数组的长度。那为什么这样计算hash可以减少冲突呢？如果直接 6 //使用hashCode&(n-1)来计算index，此时hashCode的高位随机特性完全没有用到，因为n相对于 7 //hashcode的值很小。基于这一点，把hashcode 高16位的值通过异或混合到hashCode的低16位，由此 8 //来增强hashCode低16位的随机性 9 final int hash; 10 final K key;//保存map中的key 11 V value;//保存map中的value 12 Node<K,V> next;//单向链表 13 14 Node(int hash, K key, V value, Node<K,V> next) {//构造器 15 this.hash = hash; 16 this.key = key; 17 this.value = value; 18 this.next = next; 19 }
HashMap hash函数和tableSizeFor函数源码分析（这两个函数后面会用到）
1 /** 2 * HashMap允许key为null，null的hash为0（也意味着HashMap允许key为null的键值对）， 3 * 非null的key的hash高16位和低16位分别由由：key的hashCode 4 * 高16位和hashCode的高16位异或hashCode的低16位组成。主要是为了增强hash的随机性减少hash&(n-1)的 5 * 随机性，即减小hash冲突，提高HashMap的性能。所以作为HashMap的key的hashCode函数的实现对HashMap 6 * 的性能影响较大，极端情况下：所有key的hashCode都相同，这是HashMap的性能很糟糕！ 7 */ 8static final int hash(Object key) { 9 int h; 10 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 11 } 12 13 14 /** 15 * 在new HashMap的时候，如果我们传入了大小参数，这是HashMap会对我们传入的HashMap容量进行传到 16 * tableSizeFor函数处理：这个函数主要功能是：返回一个数：这个数是大于等于cap并且是2的整数次幂 17 * 的所有数中最小的那个，即返回一个最接近cap(>=cap)，并且是2的整数次幂的那个数。 18 * 具体逻辑如下:一个数是2的整数次幂，那么这个数减1的二进制就是一串掩码，即二进制从某位开始是一 串连续的1。 19 */ 20 static final int tableSizeFor(int cap) { 21 //举例而言：n的第三位是1(从高位开始数)， 22 int n = cap - 1; 23 24 n |= n >>> 1; 25 n |= n >>> 2; 26 n |= n >>> 4; 27 n |= n >>> 8; 28 n |= n >>> 16; 29 //举例而言：如果n为: 00010000 00000000 00000000 000 30 /* 31 n |= n >>> 1;->n：00011000 00000000 00000000 0000 32 n |= n >>> 2;->n: 00011110 00000000 00000000 0000 33 n |= n >>> 4;->n: 00011111 11100000 00000000 0000 34 n |= n >>> 8;->n: 00011111 11111111 11100000 0000 35 n |= n >>> 16;->n:00011111 11111111 11111111 1111 36 37 返回n+1：00010000 00000000 00000000 000(>=cap并且为2的整数次幂，与cap差值最小的那个) 38 最后的n+1一定是2的整数次幂，并且一定是>=cap 39 整体的思路就是：如果n二进制的第k为1，那么经过上面四个‘|’运算后[0,k]位都变成了1, 40 即：一连串连续的二进制‘1’(掩码)，最后n+1一定是2的整数次幂（如果不溢出） 41 */ 42 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 43 }
HashMap成员属性源码分析
1/** 2 * The table, initialized on first use, and resized as 3 * necessary. When allocated, length is always a power of two. 4 * (We also tolerate length zero in some operations to allow 5 * bootstrapping mechanics that are currently not needed.) 6 */ 7 //我们往map中put的(k,v)都被封装在Node中，所有的Node都存放在table数组中 8 transient Node<K,V>[] table; 9 10 /** 11 * Holds cached entrySet(). Note that AbstractMap fields are used 12 * for keySet() and values(). 13 */ 14 //用于返回keySet和values 15 transient Set<Map.Entry<K,V>> entrySet; 16 17 /** 18 * The number of key-value mappings contained in this map. 19 */ 20 //保存map当前有多少个元素 21 transient int size; 22 23 /** 24 * The number of times this HashMap has been structurally modified 25 * Structural modifications are those that change the number of mappings in 26 * the HashMap or otherwise modify its internal structure (e.g., 27 * rehash). This field is used to make iterators on Collection-views of 28 * the HashMap fail-fast. (See ConcurrentModificationException). 29 */ 30 //failFast机制，在讲解ArrayList和LinkedList一文中已经讲过了 31 transient int modCount; 32 33 /** 34 * The next size value at which to resize (capacity * load factor). 35 * 36 * @serial 37 */ 38 // (The javadoc description is true upon serialization. 39 // Additionally, if the table array has not been allocated, this 40 // field holds the initial array capacity, or zero signifying 41 // DEFAULT_INITIAL_CAPACITY.) 42 43 //这也是比较重要的一个属性： 44 //创建HashMap时，改变量的值是：初始容量（2的整数次幂） 45 //之后threshold的值是HashMap扩容的门限值：即当前Node/table数组的长度*loadfactor 46 47 //举个例子而言，如果我们传给HashMap构造器的容量大小为9，那么threshold初始值为16，在向HashMap中 48 //put第一个元素后，内部会创建长度为16的Node数组，并且threshold的值更新为16*0.75=12。 49 //具体而言，当我们一直往HashMap put元素的时候，，如果put某个元素后，Node数组中元素个数为13了 50 //，此时会触发扩容（因为数组中元素个数>threshold了，即13>threshold=12），具体扩容操作之后会 51 //详细分析，简单理解就是，扩容操作将Node数组长度*2；并且将原来的所有元素迁移到新的Node数组中。 52 int threshold; 53 54 /** 55 * The load factor for the hash table. 56 * 57 * @serial 58 */ 59 //负载因子，见上面对DEFAULT_LOAD_FACTOR 参数的讲解，默认值是0.75 60 final float loadFactor;
HashMap构造器源码分析：
1//构造器：指定map的大小，和loadfactor 2public HashMap(int initialCapacity, float loadFactor) { 3 if (initialCapacity < 0) 4 throw new IllegalArgumentException("Illegal initial capacity: " + 5 initialCapacity); 6 if (initialCapacity > MAXIMUM_CAPACITY) 7 initialCapacity = MAXIMUM_CAPACITY; 8 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9 throw new IllegalArgumentException("Illegal load factor: " + 10 loadFactor); 11 this.loadFactor = loadFactor;//保存loadfactor 12 13 //注意，前面有讲tableSizeFor函数，该函数返回值：>=initialCapacity、返回值是2的整数次幂 14 //并且得是满足上面两个条件的所有数值中最小的那个数 15 this.threshold = tableSizeFor(initialCapacity); 16 } 17 18 //只指定HashMap容量的构造器，loadfactor使用的是默认的值:0.75 19 public HashMap(int initialCapacity) { 20 this(initialCapacity, DEFAULT_LOAD_FACTOR); 21 } 22 23 //无参构造器，默认loadfactor：0.75 24 public HashMap() { 25 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 26 } 27 28//其他不常用的构造器就不分析了
从构造器中我们可以看到：HashMap是“懒加载”，在构造器中值保留了相关保留的值，并没有初始化table<Node>数组，当我们向map中put第一个元素的时候，map才会进行初始化！
HashMap的get函数源码分析
1//入口,返回对应的value 2public V get(Object key) { 3 Node<K,V> e; 4 5 //hash：这个函数上面分析过了。返回key混淆后的hashCode 6 //注意getNode返回的类型是Node：当返回值为null时表示map中没有对应的key，注意区分value为 7 //null：如果key对应的value为null的话，体现在getNode的返回值e.value为null，此时返回值也是 8 //null，也就是HashMap的get函数不能判断map中是否有对应的key：get返回值为null时，可能不包 9 //含该key，也可能该key的value为null！那么如何判断map中是否包含某个key呢？见下面contains 10 //函数分析 11 return (e = getNode(hash(key), key)) == null ? null : e.value; 12 } 13 14 public boolean containsKey(Object key) { 15 //注意与get函数区分，我们往map中put的所有的<key,value>都被封装在Node中，如果Node都不存在 16 //显然一定不包含对应的key 17 return getNode(hash(key), key) != null; 18 } 19 20 21 22 //下面分析getNode函数 23 /** 24 * Implements Map.get and related methods 25 * 26 * @param hash hash for key //下面简称：key的hash值 27 * @param key the key 28 * @return the node, or null if none 29 */ 30 final Node<K,V> getNode(int hash, Object key) { 31 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 32 //(n-1)&hash：当前key可能在的桶索引，put操作时也是将Node存放在index=(n-1)&hash位置 33 //主要逻辑：如果table[index]处节点的key就是要找的key则直接返回该节点； 34 //否则：如果在table[index]位置进行搜索，搜索是否存在目标key的Node：这里的搜索又分两种： 35 //链表搜索和红黑树搜索，具体红黑树的查找就不展开了，红黑树是一种弱平衡(相对于AVL)BST， 36 //红黑树查找、删除、插入等操作都能够保证在O(lon(n))时间复杂度内完成，红黑树原理不在本文 37 //范围内，但是大家要知道红黑树的各种操作是可以实现的，简单点可以把红黑树理解为BST， 38 //BST的查找、插入、删除等操作的实现在之前的博客中有java实现代码，实际上红黑树就是一种平 39 //衡的BST 40 if ((tab = table) != null && (n = tab.length) > 0 && 41 (first = tab[(n - 1) & hash]) != null) { 42 if (first.hash == hash && // always check first node 43 ((k = first.key) == key || (key != null && key.equals(k)))) 44 return first;//一次就匹配到了，直接返回，否则进行搜索 45 if ((e = first.next) != null) { 46 if (first instanceof TreeNode) 47 //红黑树搜索/查找 48 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 49 do { 50 //链表搜索(查找) 51 if (e.hash == hash && 52 ((k = e.key) == key || (key != null && key.equals(k)))) 53 return e;//找到了就返回 54 } while ((e = e.next) != null); 55 } 56 } 57 return null;//没找到，返回null 58 }
get函数实质就是进行链表或者红黑树遍历搜索指定key的节点的过程；另外需要注意到HashMap的get函数的返回值不能判断一个key是否包含在map中，get返回null有可能是不包含该key；也有可能该key对应的value为null。HashMap中允许key为null，允许value为null。
HashMap的put函数源码分析
1//put函数入口,两个参数：key和value 2public V put(K key, V value) { 3 //下面分析这个函数，注意前3个参数，后面2个参数这里不太重要，因为所有的put后面2个参数都一样 4 return putVal(hash(key), key, value, false, true); 5 } 6 7 8 9//下面是put函数的核心处理函数 10/** 11 * Implements Map.put and related methods 12 * 13 * @param hash hash for key 14 * @param key the key 15 * @param value the value to put 16 * @param onlyIfAbsent if true, don't change existing value 17 * @param evict if false, the table is in creation mode. 18 * @return previous value, or null if none 19 */ 20 21 //hash：key的hashCode 22 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 23 boolean evict) { 24 Node<K,V>[] tab; Node<K,V> p; int n, i; 25 //上面提到过HashMap是懒加载，所有put的时候要先检查table数组是否已经初始化了， 26 //没有初始化得先初始化table数组，保证table数组一定初始化了 27 if ((tab = table) == null || (n = tab.length) == 0) 28 n = (tab = resize()).length;//这个函数后面有resize函数分析 29 30 //到这里表示table数组一定初始化了 31 //与上面get函数相同，指定key的Node，put在table数组的i=(n-1)&hash下标位置，get的时候 32 //也是从table数组的该位置搜索 33 if ((p = tab[i = (n - 1) & hash]) == null) 34 //如果i位置还没有存储元素，则把当前的key，value封装为Node，存储在table[i]位置 35 tab[i] = newNode(hash, key, value, null); 36 else { 37 //如果table[i]位置已经有元素了，则接下来执行的是： 38 //首先判断链表或者二叉树中时候已经存在key的键值对，存在的话就更新它的value 39 //不存在的话把当前的key，value插入到链表的末尾或者插入到红黑树中 40 //如果链表或者红黑树中已经存在Node.key等于key，则e指向该Node，即 41 //e指向一个Node：该Node的key属性与put时传入的key参数相等的那个Node，后面会更新e.value 42 Node<K,V> e; K k; 43 44 //为什么get和put先判断p.hash==hash,下面的if条件中去掉hash的比较也可以逻辑也正确？ 45 //因为hash的比较是两个整数的比较，比较的代价相对较小，key是泛型，对象的比较比整数比较 46 //代价大，所以先比较hash，hash相等在比较key 47 if (p.hash == hash &&// 48 ((k = p.key) == key || (key != null && key.equals(k)))) 49 e = p;//e指向一个Node：该Node的key属性与put时传入的key参数相等的那个Node 50 else if (p instanceof TreeNode) 51 //红黑树的插入操作，如果已经存在该key的TreeNode，则返回该TreeNode，否则返回null 52 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 53 else { 54 //table[i]处存放的是链表，接下来和TreeNode类似 55 //在遍历链表过程中先判断是key先前是否存在，如果存在则e指向该Node 56 //否则将该Node插入到链表末尾，插入后判断链表长度是否>=8，是的话要进行额外操作 57 58 //binCountt最后的值是链表的长度 59 for (int binCount = 0; ; ++binCount) { 60 61 if ((e = p.next) == null) { 62 //遍历到了链表最后一个元素,接下来执行链表的插入操作，先封装为Node再插入 63 //p指向的是链表最后一个节点，将待插入的Node置为p.next，就完成了单链表的插入 64 p.next = newNode(hash, key, value, null); 65 66 67 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 68 //TREEIFY_THRESHOLD值是8， binCount>=7,然后又插入了一个新节点， 69 //链表长度>=8，这时要么进行扩容操作，要么把链表结构转为红黑树结构 70 //我们接下会分析treeifyBin的源码实现 71 treeifyBin(tab, hash); 72 break; 73 } 74 75 //当p不是指向链表末尾的时候：先判断p.key是否等于key，等于的话表示当前key 76 //已经存在了，令e指向p，停止遍历，最后会更新e的value； 77 //不等的话准备下次遍历，令p=p.next，即p=e 78 if (e.hash == hash && 79 ((k = e.key) == key || (key != null && key.equals(k)))) 80 break; 81 p = e; 82 } 83 } 84 85 86 if (e != null) { // existing mapping for key 87 //表示当前的key之前已经存在了，并且上面的逻辑保证:e.key一定等于key 88 //这是更新e.value就好 89 V oldValue = e.value;//保存oldvalue 90 91 //onlyIfAbsent默是false，evict为true 92 //onlyIfAbsent为true表示如果之前已经存在key这个键值对了，那么后面在put这个key 93 //时，忽略这个操作，不更新先前的value，这里连接就好 94 if (!onlyIfAbsent || oldValue == null) 95 e.value = value;//更新e.value 96 97 //这个函数的默认实现是“空”，即这个函数默认什么操作都不执行，那为什么要有它呢？ 98 //这是个hook/钩子函数，主要要在LinkedHashMap中，LinkedHashMap重写了这个函数 99 //后面讲解LinkedHashMap时会详细讲解 100 afterNodeAccess(e); 101 return oldValue;//返回旧的value 102 } 103 } 104 105 //如果是第一次插入key这个键，就会执行到这里 106 ++modCount;//failFast机制 107 108 //size保存的是当前HashMap中保存了多少个键值对，HashMap的size方法就是直接返回size 109 //之前说过，threshold保存的是当前table数组长度*loadfactor，如果table数组中存储的 110 //Node数量大于threshold，这时候会进行扩容，即将table数组的容量翻倍。后面会详细讲解 111 //resize方法 112 if (++size > threshold) 113 resize(); 114 115 //这也是一个hook函数，作用和afterNodeAccess一样 116 afterNodeInsertion(evict); 117 return null; 118 } 119 120 121 //将链表转换为红黑树结构，在链表的插入操作后调用 122/** 123 * Replaces all linked nodes in bin at index for given hash unless 124 * table is too small, in which case resizes instead. 125 */ 126 final void treeifyBin(Node<K,V>[] tab, int hash) { 127 int n, index; Node<K,V> e; 128 129 //MIN_TREEIFY_CAPACITY值是64,也就是当链表长度>8的时候，有两种情况： 130 //如果table数组的长度<64,此时进行扩容操作 131 //如果table数组的长度>64，此时进行链表转红黑树结构的操作 132 //具体转细节在面试中几乎没有问的，这里不细讲了， 133 //大部同学认为链表长度>8一定会转换成红黑树，这是不对的！！！ 134 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 135 resize(); 136 else if ((e = tab[index = (n - 1) & hash]) != null) { 137 TreeNode<K,V> hd = null, tl = null; 138 do { 139 TreeNode<K,V> p = replacementTreeNode(e, null); 140 if (tl == null) 141 hd = p; 142 else { 143 p.prev = tl; 144 tl.next = p; 145 } 146 tl = p; 147 } while ((e = e.next) != null); 148 if ((tab[index] = hd) != null) 149 hd.treeify(tab); 150 } 151 }
HashMap的resize函数源码分析
重点中的重点，面试谈到HashMap必考resize相关知识
1/** 2 * 有两种情况会调用当前函数： 3 * 1.之前说过HashMap是懒加载，第一次hHashMap的put方法的时候table还没初始化， 4 * 这个时候会执行resize，进行table数组的初始化，table数组的初始容量保存在threshold中（如果从构造器 5 * 中传入的一个初始容量的话），如果创建HashMap的时候没有指定容量，那么table数组的初始容 6 * 量是默认值：16。即，初始化table数组的时候会执行resize函数 7 * 2.扩容的时候会执行resize函数，当size的值>threshold的时候会触发扩容，即执行resize方法， 8 * 这时table数组的大小会翻倍。 9 * 10 * 注意我们每次扩容之后容量都是翻倍（*2），所以HashMap的容量一定是2的整数次幂，那么HashMap的 11 * 容量为什么一定得是2的整数次幂呢？（面试重点） 要知道原因，首先回顾我们put 12 * key的时候，每一个key会对应到一个桶里面，桶的索引是这样计算的： index = hash & (n-1)， 13 * index的计算最为直观的想法是：hash%n，即通过取余的方式把当前的key、value键值对散列到各个桶中； 14 * 那么这里为什么不用取余(%)的方式呢？原因是CPU对位运算支持较好，即位运算速度很快。 15 * 另外,当n是2的整数次幂时：hash&(n-1)与hash%(n-1)是等价的，但是两者效率来讲是不同的，位运算的效率 16 * 远高于%运算。基于这一点，HashMap中使用的是hash&(n-1)。这还带来了一个好处，就是将旧数组中的Node迁移到扩容后 17 * 的新数组中的时候有一个很方便的特性：HashMap使用table数组保存Node节点，所以table数组扩容的时候（数组扩容）一 18 * 定得是先重新开辟一个数组，然后把就数组中的元素重新散列到新数组中去。这里举一个例子来来说明这个特性：下面以Hash初始容量 19 * n=16，默认loadfactor=0.75举例（其他2的整数次幂的容量也是类似的）：默认容量：n=16，二进制：10000；n-1：15, 20 * n-1二进制：01111，即一连串1。某个时刻，map中元素大于16*0.75=12，即size>12，此时我们新建了一个数组， 21 * 容量为扩容前的两倍，newtab，len=32;接下来我们需要把table中的Node搬移(rehash)到newtab。从table的i=0 22 * 位置开始处理,假设我们当前要处理table数组i索引位置的node，那这个node应该放在newtab的那个位置呢？下面的hash表 23 * 示node.key对应的hash值，也就等于node.hash属性值,另外为了简单，下面的hash只写出了8位（省略的高位的0），实际上 24 * hash是32位：node在newtab中的索引：index=hash%len=hash&(len-1)=hash&(32-1)=hash&31 25 * =hash&(0x0001_1111)；再看node在table数组中的索引计算：i=hash&(16-1)=hash&15 26 * =hash&(0x0000_1111)。注意观察两者的异同：i=hash&(0x0000_1111);index=hash&(0x0001_1111) 27 * 这个表达式有个特点：index=hash&(0x0001_1111)=hash&(0x0000_1111) | 28 * hash&(0x0001_0000) =hash&(0x0000_1111) | hash&n)=i+( hash&n)。什么意思呢： 29 * hash&n要么等于n要么等于0;也就是：inde要么等于i，要么等于i+n;再具体一点：当hash&n==0的时候，index=i; 30 * 当hash&n==n的时候，index=i+n;这有什么用呢？当我们把table[i]位置的所有Node迁移到newtab中去的时候： 31 * 这里面的node要么在newtab的i位置（不变），要么在newtab的i+n位置；也就是我们可以这样处理：把table[i]这个桶中的 32 * node拆分为两个链表l1和类：如果hash&n==0，那么当前这个node被连接到l1链表；否则连接到l2链表。这样下来， 33 * 当遍历完table[i]处的所有node的时候，我们得到两个链表l1和l2，这时我们令newtab[i]=l1,newtab[i+n]=l2, 34 * 这就完成了table[i]位置所有node的迁移/rehash，这也是HashMap中容量一定的是2的整数次幂带来的方便之处。 35 * 下面的resize的逻辑就是上面讲的那样。将table[i]处的Node拆分为两个链表，这两个链表再放到newtab[i] 36 * 和newtab[i+n]位置 37 38 * Initializes or doubles table size. If null, allocates in 39 * accord with initial capacity target held in field threshold. 40 * Otherwise, because we are using power-of-two expansion, the 41 * elements from each bin must either stay at same index, or move 42 * with a power of two offset in the new table. 43 * 44 * @return the table 45 */ 46 final Node<K,V>[] resize() { 47 Node<K,V>[] oldTab = table;//保留扩容前数组引用 48 int oldCap = (oldTab == null) ? 0 : oldTab.length; 49 int oldThr = threshold; 50 int newCap, newThr = 0; 51 if (oldCap > 0) { 52 if (oldCap >= MAXIMUM_CAPACITY) { 53 threshold = Integer.MAX_VALUE; 54 return oldTab; 55 } 56 //正常扩容：newCap = oldCap << 1 57 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 58 oldCap >= DEFAULT_INITIAL_CAPACITY) 59 //容量翻倍，扩容后的threshold自然也是*2 60 newThr = oldThr << 1; // double threshold 61 } 62 else if (oldThr > 0) // initial capacity was placed in threshold 63 newCap = oldThr; 64 else { // zero initial threshold signifies using defaults 65 //table数组初始化的时候会进入到这里 66 newCap = DEFAULT_INITIAL_CAPACITY;//默认容量 67 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//threshold 68 } 69 if (newThr == 0) { 70 float ft = (float)newCap * loadFactor; 71 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 72 (int)ft : Integer.MAX_VALUE); 73 } 74 threshold = newThr;//更新threshold 75 @SuppressWarnings({"rawtypes","unchecked"}) 76 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//扩容后的新数组 77 table = newTab;//执行容量翻倍的新数组 78 if (oldTab != null) { 79 for (int j = 0; j < oldCap; ++j) {//之后完成oldTab中Node迁移到table中去 80 Node<K,V> e; 81 if ((e = oldTab[j]) != null) { 82 oldTab[j] = null; 83 if (e.next == null)//j这个桶位置只有一个元素，直接rehash到table数组 84 newTab[e.hash & (newCap - 1)] = e; 85 else if (e instanceof TreeNode) 86 //如果是红黑树：也是将红黑树拆分为两个链表，这里主要看链表的拆分，两者逻辑一样 87 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 88 else { // preserve order 89 //链表的拆分 90 Node<K,V> loHead = null, loTail = null;//第一个链表l1 91 Node<K,V> hiHead = null, hiTail = null;//第二个链表l2 92 Node<K,V> next; 93 do { 94 next = e.next; 95 if ((e.hash & oldCap) == 0) {//rehash到table[j]位置 96 //将当前node连接到l1上 97 if (loTail == null) 98 loHead = e; 99 else 100 loTail.next = e; 101 loTail = e; 102 } 103 else { 104 //将当前node连接到l2上 105 if (hiTail == null) 106 hiHead = e; 107 else 108 hiTail.next = e; 109 hiTail = e; 110 } 111 } while ((e = next) != null); 112 113 if (loTail != null) { 114 //l1放到table[j]位置 115 loTail.next = null; 116 newTab[j] = loHead; 117 } 118 if (hiTail != null) { 119 //l1放到table[j+oldCap]位置 120 hiTail.next = null; 121 newTab[j + oldCap] = hiHead; 122 } 123 } 124 } 125 } 126 } 127 return newTab; 128 }
HashMap面试“明星”问题汇总，及答案 ：
你知道HashMap吗，请你讲讲HashMap？
这个问题不单单考察你对HashMap的掌握程度，也考察你的表达、组织问题的能力。个人认为应该从以下几个角度入手（所有常见HashMap的考点问题总结）：
size必须是2的整数次方原因
get和put方法流程
resize方法
影响HashMap的性能因素（key的hashCode函数实现、loadFactor、初始容量）
HashMap key的hash值计算方法以及原因（见上面hash函数的分析）
HashMap内部存储结构：Node数组+链表或红黑树
table[i]位置的链表什么时候会转变成红黑树（上面源码中有讲）
HashMap主要成员属性：threshold、loadFactor、HashMap的懒加载
HashMap的get方法能否判断某个元素是否在map中
HashMap线程安全吗，哪些环节最有可能出问题，为什么？
HashMap的value允许为null，但是HashTable和ConcurrentHashMap的valued都不允许为null，试分析原因？
HashMap中的hook函数（后面讲解LinkedHashMap时会讲解，这可作为HashMap的延伸知识，增加面试官对你的印象）
上面问题的答案都可以在上面的源码分析中找到，下面在给三点补充：
HashMap的初试容量设计怎样影响HashMap的性能的？
假如你估计你最多往HashMap中存储64个元素，那么你在创建HashMap的时候：如果选用无参构造器：默认容量16，在存储16_loadFactor个元素之后就要进行扩容（数组扩容涉及到连续空间的分配，Node节点的rehash，代价很高，所以要尽量避免扩容操作）；如果给构造器传入的参数是64，这时HashMap中在存储64_loadFactor个元素之后就要进行扩容；但是如果你给构造器传的参数为：(int)(64/0.75)+1，此时就可以保证HashMap不用进行扩容，避免了扩容时的代价。
HashMap线程安全吗，哪些环节最有可能出问题，为什么？
我们都知道HashMap线程不安全，那么哪些环节最优可能出问题呢，及其原因：没有参照这个问题有点不好直接回答，但是我们可以找参照啊，参照：ConcurrentHashMap，因为大家都知道HashMap不是线程安全的，ConcurrentHashMap是线程安全的，对照ConcurrentHashMap，看看ConcurrentHashMap在HashMap的基础之上增加了哪些安全措施，这个问题就迎刃而解了。后面会有分析ConcurrentHashMap的文章，这里先简要回答这个问题：HashMap的put操作是不安全的，因为没有使用任何锁；HashMap在多线程下最大的安全隐患发生在扩容的时候，想想一个场合：HashMap使用默认容量16，这时100个线程同时往HashMap中put元素，会发生什么？扩容混乱，因为扩容也没有任何锁来保证并发安全，另外,后面的博文会讲到ConcurrentHashMap的并发扩容操作是ConcurrentHashMap的一个核心方法。
HashMap的value允许为null，但是HashTable和ConcurrentHashMap的valued都不允许为null，试分析原因？
首先要明确ConcurrentHashMap和Hashtable从技术从技术层面讲是可以允许value为null；但是它是实际是不允许的，这肯定是为了解决一些问题，为了说明这个问题，我们看下面这个例子（这里以ConcurrentHashMap为例，HashTable也是类似）
HashMap由于允value为null，get方法返回null时有可能是map中没有对应的key；也有可能是该key对应的value为null。所以get不能判断map中是否包含某个key，只能使用contains判断是否包含某个key。
看下面的代码段，要求完成这个一个功能：如果map中包含了某个key则返回对应的value，否则抛出异常：
1if (map.containsKey(k)) { 2 return map.get(k); 3} else { 4 throw new KeyNotPresentException(); 5}
如果上面的map为HashMap，那么没什么问题，因为HashMap本来就是线程不安全的，如果有并发问题应该用ConcurrentHashMap，所以在单线程下面可以返回正确的结果
如果上面的map为ConcurrentHashMap，此时存在并发问题：在map.containsKey(k)和map.get之间有可能其他线程把这个key删除了，这时候map.get就会返回null，而ConcurrentHashMap中不允许value为null，也就是这时候返回了null，一个根本不允许出现的值？
但是因为ConcurrentHashMap不允许value为null，所以可以通过map.get(key)是否为null来判断该map中是否包含该key，这时就没有上面的并发问题了。