HashMap原理

为什么要针对HashMap做一篇文章了，一方面是因为面试中经常被问到这个问题，另一方面主要是在工作中经常用到HashMap，既然经常用到，不能不懂它的原理啊。

• 定义

 * Hash table based implementation of the <tt>Map</tt> interface.  This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.

HashMap是基于哈希表对Map接口的一个实现。这个实现类提供类Map的所有可选的操作，同时允许储存null值和null键。和HashTable差不多，不同的是，HashMap是线程不安全的并且允许空的键值对。这个类不保证map的顺序。

• 基本原理

HashMap的主干是一个数组，每个元素可能是一个链表，也可能是一个红黑树，这要视这个元素所储存的键值对多少来决定。网上有说HashMap是一个链表的数组，这在jdk1.8以前是正确的理解，但是在jdk1.8以后，加入了红黑树的概念，所以注意以后不能这么理解了。把HashMap哈希碰撞以后的节点当作一个桶，这个桶可以是一个链表，也可以是一棵红黑树。那为什么要这样实现HashMap呢，当然是为了效率！HashMap寻找键值对时，第一步是对key进行一系列计算，算出键值对的储存位置后，再通过地址寻找，如果哈希算法设计的合理，几乎不会发生hash碰撞，这个时候，获取一次键值对的时间复杂度仅仅是O(1)（时间复杂度会在其他文章做出解释，做完后会附上连接）。如果发生了hash碰撞，当碰撞节点是个个链表时，说明这个链表的元素最多8个（源码中可以看出），通过循环遍历键值对，对比key.equals来确定地址；如果碰撞点是个红黑树，那就通过红黑树确定地址，红黑树的时间复杂度是O(logN)。这么看来，HashMap的时间复杂度最多也就是O(logN)，这就是为什么它会如此高效。这里对原理说个大概，接下来我们走一遍HashMap的生命周期。

• 创建HashMap

创建HashMap的时候并没有初始化table，而是在put操作的时候才会初始化table。

1 HashMap有四个构造方法：

1.1 public HashMap(int initialCapacity, float loadFactor);

参数中的initialCapacity和loadFactor分别是HashMap的初始容量和负载因子。

1.2 public HashMap(int initialCapacity)；

1.3 public HashMap()；

1.4 public HashMap(Map<? extends K, ? extends V> m)；

2 HashMap的几个变量：

2.1 transient int size;

map中的容纳的键值对总数。

2.2 transient int modCount;

map结构被修改的次数，这个变量在使用迭代器遍历元素的时候会用到。举个例子：

public static void main(String[] args) {
	Map<String,Object> map = new HashMap(1 << 2, 0.75f) {{
		put("a", 1);
		put("b", 1);
		put("c", 1);
		put("d", 1);
	}};
	Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator();
	int i = 0;
	while (iterator.hasNext()){
		Map.Entry<String,Object> next = iterator.next();
		do {
			map.remove("a");
		}while (i==1);
		i++;
	}
}

控制台：
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
	at HashMapPractice.main(HashMapPractice.java:17)

抛出异常的地方在这里：

     final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

当modCount与期望的expectedModCount不一致时，便会抛出ConcurrentModificationException。所以在使用map元素的迭代器时，一定要注意不能随意修改map的结构。

2.3 int threshold;

The next size value at which to resize (capacity * load factor).下一次重新扩充map容量的标志，这个值由capacity和load factor决定。当创建HashMap没有指定initialCapacity时，capacity默认为8（static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;），当没有指定loadFactor时，loadFactor默认为0.75f（static final float DEFAULT_LOAD_FACTOR = 0.75f;）。

2.4 final float loadFactor;

这个在2.3中已经提过，负载因子，代表map的容量达到某个值时，重新扩充容量。

2.5 transient Set<Map.Entry<K,V>> entrySet;

Map子类Entry的set集合，可用来获取所有的键值对。

2.6  transient Node<K,V>[] table;

HashMap子类Node的集合，可用来获取当前所有的节点。