答：“当然用过，HashMap是一种<key,value>的存储构造，能够快速将key的数据put办法存储起来，然后很快的通过get取出来”，然后说“HashMap不是线程安全的， HashTable是线程安全的，通过synchronized实现的。HashMap取值非常快”等等。这个时候解释他已经很闇练利用HashMap的工具了。
问：“你知道HashMap 在put和get的时候是怎么事情的吗？”
答：“HashMap是通过key打算出Hash值，然后将这个Hash值映射到工具的引用上，get的时候先打算key的hash值，然后找到工具”。这个时候已经显得不自傲了。
问：“HashMap的key为什么一样平常用字符串比较多，能用其他工具，或者自定义的工具吗？为什么？”
答：“这个没研究过，一样平常习惯用String。”
问：“你刚才提到HashMap不是线程安全的，你怎么理解线程安全。事理是什么？几种办法避免线程安全的问题。”
答：“线程安全便是多个线程去访问的时候，会对工具造成不是预期的结果，一样平常要加锁才能线程安全。”
实在，问了以上那些问题，我基本能剖断这个程序员的基本功了，一样平常技能中等，接下来的问题没必要问了。
从我的个人角度来看，HashMap的口试问题能够稽核口试者的线程问题、Java内存模型问题、线程可见与不可变问题、Hash打算问题、链表构造问题、二进制的&、|、<<、>>等问题。以是一个HashMap就能磨练一个人的技能功底了。
二、观点剖析1、HashMap的类图构造
此处的类图是根据JDK1.6版本画出来的。如下图1:
2、HashMap存储构造
HashMap的利用那么大略，那么问题来了，它是怎么存储的，它的存储构造是若何的，很多程序员都不知道，实在当你put和get的时候，稍稍往前一步，你看到便是它的真面孔。实在大略的说HashMap的存储构造是由数组和链表共同完成的。如图：
从上图可以看出HashMap是Y轴方向是数组，X轴方向便是链表的存储办法。大家都知道数组的存储办法在内存的地址是连续的，大小固定，一旦分配不能被其他引用占用。它的特点是查询快，韶光繁芜度是O(1)，插入和删除的操作比较慢，韶光繁芜度是O(n)，链表的存储办法是非连续的，大小不固定，特点与数组相反，插入和删除快，查询速率慢。HashMap可以说是一种折中的方案吧。
3、HashMap基本事理
1、首先判断Key是否为Null，如果为null，直接查找Enrty[0]，如果不是Null，先打算Key的HashCode，然后经由二次Hash。得到Hash值，这里的Hash特色值是一个int值。
2、根据Hash值，要找到对应的数组啊，以是对Entry[]的长度length求余，得到的便是Entry数组的index。
3、找到对应的数组，便是找到了所在的链表，然后按照链表的操为难刁难Value进行插入、删除和查询操作。
4、HashMap观点先容
5、HashMap初始化
默认情形下，大多数人都调用new HashMap()来初始化的，我在这里剖析new HashMap(int initialCapacity, float loadFactor)的布局函数，代码如下：
由上面的代码可以看出，初始化的时候须要知道初始化的容量大小，由于在后面要通过按位与的Hash算法打算Entry数组的索引，那么哀求Entry的数组长度是2的N次方。
6、HashMap中的Hash打算和碰撞问题
HashMap的hash打算时先打算hashCode(),然后进行二次hash。代码如下：
// 打算二次Hash int hash = hash(key.hashCode());// 通过Hash找数组索引int i = indexFor(hash, table.length);
先不忙着学习HashMap的Hash算法，先来看看JDK的String的Hash算法。代码如下：
从JDK的API可以看出，它的算法等式便是s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]，个中s[i]便是索引为i的字符，n为字符串的长度。这里为什么有一个固定常量31呢，关于这个31的谈论很多，基本便是优化的数字，紧张参考Joshua Bloch's Effective Java的引用如下：
The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 i == (i << 5) - i. Modern VMs do this sort of optimization automatically.
大体意思是说选择31是由于它是一个奇素数，如果它做乘法溢出的时候，信息会丢失，而且当和2做乘法的时候相称于移位，在利用它的时候优点还是不清楚，但是它已经成为了传统的选择，31的一个很好的特性便是做乘法的时候可以被移位和减法代替的时候有更好的性能表示。例如31i相称于是i左移5位减去i，即31i == (i<<5)-i。当代的虚拟内存系统都利用这种自动优化。
现在进入正题，HashMap为什么还要做二次hash呢? 代码如下：
回答这个问题之前，我们先来看看HashMap是怎么通过Hash查找数组的索引的。
/ Returns index for hash code h. / static int indexFor(int h, int length) { return h & (length-1); }
个中h是hash值，length是数组的长度，这个按位与的算法实在便是h%length求余，一样平常什么情形下利用该算法，范例的分组。例如怎么将100个数分组16组中，便是这个意思。运用非常广泛。
既然知道了分组的事理了，那我们看看几个例子，代码如下：
运行结果都是15，为什么呢?我们换算成二进制来看看。
这里你就创造了，在做按位与操作的时候，后面的始终是低位在做打算，高位不参与打算，由于高位都是0。这样导致的结果便是只假如低位是一样的，高位无论是什么，末了结果是一样的，如果这样一来，hash碰撞始终在一个数组上，导致这个数组开始的链表无限长，那么在查询的时候就速率很慢，又怎么算得上高性能的啊。以是hashmap必须办理这样的问题，只管即便让key尽可能均匀的分配到数组上去。避免造成Hash堆积。
回到正题，HashMap怎么处理这个问题，怎么做第二次Hash。
这里便是办理Hash的的冲突的函数，办理Hash的冲突有以下几种方法： 1. 开放定址法 线性探测再散列，二次探测再散列，伪随机探测再散列） 2. 再哈希法 3. 链地址法 4. 建立一 公共溢出区
而HashMap采取的是链地址法，这几种方法在往后的博客会有单独先容，这里就不做先容了。
7、HashMap的put()解析
以上说了一些基本观点，下面该进入主题了，HashMap怎么存储一个工具的，代码如下：
/ Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. @param key key with which the specified value is to be associated @param value value to be associated with the specified key @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return can also indicate that the map previously associated <tt>null</tt> with <tt>key</tt>.) / public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }
从代码可以看出，步骤如下：
(1) 首先判断key是否为null，如果是null，就单独调用putForNullKey(value)处理。代码如下：
从代码可以看出，如果key为null的值，默认就存储到table[0]开头的链表了。然后遍历table[0]的链表的每个节点Entry，如果创造个中存在节点Entry的key为null，就更换新的value，然后返回旧的value，如果没创造key即是null的节点Entry，就增加新的节点。
(2) 打算key的hashcode，再用打算的结果二次hash，通过indexFor(hash, table.length);找到Entry数组的索引i。
(3) 然后遍历以table[i]为头节点的链表，如果创造有节点的hash，key都相同的节点时，就更换为新的value，然后返回旧的value。
(4) modCount是干嘛的啊? 让我来为你解答。众所周知，HashMap不是线程安全的，但在某些容错能力较好的运用中，如果你不想仅仅由于1%的可能性而去承受hashTable的同步开销，HashMap利用了Fail-Fast机制来处理这个问题，你会创造modCount在源码中是这样声明的。
volatile关键字声明了modCount，代表了多线程环境下访问modCount，根据JVM规范，只要modCount改变了，其他线程将读到最新的值。其实在Hashmap中modCount只是在迭代的时候起到关键浸染。
private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { // 这里便是关键 if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } }
利用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修正，如果modCount和expectedModCount值不一样，证明有其他线程在修正HashMap的构造，会抛出非常。
以是HashMap的put、remove等操作都有modCount++的打算。
(5) 如果没有找到key的hash相同的节点，就增加新的节点addEntry(),代码如下：
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 table.length); }
这里增加节点的时候取消了，每个新添加的节点都增加到头节点，然后新的头节点的next指向旧的老节点。
(6) 如果HashMap大小超过临界值，就要重新设置大小，扩容，见第9节内容。
8、HashMap的get()解析
理解上面的put，get就很好理解了。代码如下：
别看这段代码，它带来的问题是巨大的，千万记住,HashMap是非线程安全的，以是这里的循环会导致去世循环的。为什么呢?当你查找一个key的hash存在的时候，进入了循环，正好这个时候，其余一个线程将这个Entry删除了，那么你就一贯由于找不到Entry而涌现去世循环，末了导致的结果便是代码效率很低，CPU特殊高。一定记住。
9、HashMap的size()解析
HashMap的大小很大略，不是实时打算的，而是每次新增加Entry的时候，size就递增。删除的时候就递减。空间换韶光的做法。由于它不是线程安全的。完备可以这么做。效力高。
9、HashMap的reSize()解析
当HashMap的大小超过临界值的时候，就须要扩充HashMap的容量了。代码如下：
从代码可以看出，如果大小超过最大容量就返回。否则就new 一个新的Entry数组，长度为旧的Entry数组长度的两倍。然后将旧的Entry[]复制到新的Entry[].代码如下：
在复制的时候数组的索引int i = indexFor(e.hash, newCapacity);重新参与打算。
至此，HashMap还有一些迭代器的代码，这里不一一做先容了，在JDK1.7版本中HashMap也做了一些升级，详细有Hash因子的参与。
本日差不多完成了HashMap的源码解析，下一步将会剖析ConcurrencyHashMap的源码。ConcurrencyHashMap填补了HashMap线程不屈安、HashTable性能低的缺失落。是目前高性能的线程安全的HashMap类。
