程序猿成长之路番外篇--hashmap介绍

最近在网上看hashmap的相关源码，发现基本的知识有所介绍，但有些地方还是讲的不够透彻，所以我打算再给大家分享一下我的理解。

HashMap大家都知道这是java中常见的数据结构，用途广泛，比如可以用作传参的容器，也可以用于spring中bean的管理。它继承了AbstractMap类，是map的后代，所以我们常常可以用向上造型进行创建实例。
如：

Map map = new HashMap<>();

此外，在括号内还可以传入参数，这个参数代表的含义就是hashmap的initCapacity（初始容量），一般取2的幂次方（为什么取这个值后文会讲到），默认为16。
如：

Map map = new HashMap<>(16);

ps: 这里的容量也可以填其他的数字，如10,14等，但是在初始化时会自动转换成不小于该数字的2的幂次方，这个又是怎么做到的后文也会讲。

之后要想往里面存放数据，只要这样写就还可以了:

map.put(key1,value1);
map.put(key2,value2);

要想取数据则这样写：

map.get(key1);   //value1
map.get(key2);	 //value2

此外，map中的entry元素支持循环遍历，代码如下：

for(Map.Entry entry: map.entrySet()) {
	String key = entry.getKey();
	String value = entry.getValue();
	// 后续操作
	...
}

也可以通过以下方式进行遍历，代码如下

for(Type1 key: map.keySet()) {
	String value = map.get(key);
	// 后续操作
	...
}

map还可以通过迭代器进行遍历，代码如下：

Iterator it = map.entrySet().iterator();
while(it.hasNext()) {
	Map.Entry entry = it.next();
	//对entry进行处理
	String key = entry.getKey();
	String value = entry.getValue();
	...
}

map可以删除元素：

map.remove(key1);

但是切记不能在上述两个循环中使用put或者remove方法进行节点的修改，否则会报java.util.ConcurrentModificationException错，因为在源码中，map中的entry的迭代器中有个expectedModCount 变量，而map中也有个变量叫做modCount，就拿remove方法举例，当调用map中的remove方法时，map中的modCount会进行累加，而迭代器中的expectedModCount没有发生变化，这在EntryIterator迭代器中在实现获取下一个节点的操作时会报错，代码如下：

//1.该函数出现在HashMap的HashIterator这个抽象类中
class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
	...
	transient int modCount;//HashMap结构改变的次数
	...
	abstract class HashIterator {
		Node next;
	    Node current;
	   	int expectedModCount //迭代器改变的次数
	    int index; 
		...
		final HashMap.Node nextNode() {
			HashNode node2 = this.next;
			//关键代码
			if(hashMap.this.modCount != this.expectedModCount) {
				throw new ConcurrentModificationException();
			}
			...
		}
		...
	}
	//2.而在map中则通过内部EntryIterator类实现了这个抽象类
	final class EntryIterator extends HashIterator
		implements Iterator> {
		public final Map.Entry next() { return nextNode(); }
	}
	//3.在Map.Entry中创建EntryIterator实例
	final class EntrySet extends AbstractSet> {
		public final int size() { 
			return size;
		}
		public final void clear() { 
			HashMap.this.clear();
		}
		public final Iterator> iterator() {
			return new EntryIterator();
		}
		...
	}
}	

但如果使用了迭代器中的remove方法，会自动将迭代器中的expectedModCount与map中的modCount同步更新，就避免了报错。

map还可以替换元素
map.replace(Type1 key, Type2 oldValue, Type2 newValue)

hashmap的基本结构如图所示

它最底层的数据结构为链表数组，也就是由链表组成的数组，也就是Node[] table。Node 为实现了Map.Entry接口的类（1.8之前叫Entry，1.8之后叫Node，改名字了），用于存储键值对。它的基本构成代码如下图：

static class Node implements Map.Entry {
	final int hash; //hash值用于确定下标位置
	final K key;
	final V value;
	final Node next; //链表下一个元素
	// 注意这里是package的访问修饰符，也就是说外部无法通过
	//Map.Node的形式获取该元素，而是要通过自带的static函数
	// map.entrySet()来获取
	Node(int hash, K key, V value, Node next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
	public final K getKey() {
		return key;
	}
	public final V getValue() {
		return value;
	}
	public final String toString() {
		return key + "=" + value;
	}
	public final int hashCode(){
		return Objects.hashCode(key) ^ Objects.hashCode(value);
	}
}

细心的小伙伴一定发现了这里的构造方法是package的，只能在同一个包里面访问，所以外部无法通过Map.Node的形式获取该元素，而是要通过自带的方法map.entrySet()来获取。

那么问题来了，既然知道hashmap的底层为链表数组，那么它是怎么进行数据存储的呢？node中的hash值如何计算，它又有什么用途呢？

饭总得一口一口的吃，问题也要一个一个的解决。先看一下数据存储的过程：现在我们想往里面存放一些数据：{“name”: “zhangsan”,“age”:“16”,“sex”,“男”}, 很明显这是一条个人信息数据，我们也可以将其以键值对形式存放进hashmap中。

• 步骤一: 调用put(key,value)方法
• 步骤二: 在put(key,value)方法中我们会计算这个键值对的hash值，计算方式如下：

//JDK1.7
static int hash(Object key){
	int h = hashSeed;
	if (0 != h && k instanceof String) {
		return sun.misc.Hashing.stringHash32((String) k);
	}
	h ^= k.hashCode();
	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}
//JDK1.8
static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

以JDK1.8为例，这里用了无符号右移的运算（高位补0，低位右移），将高16位和key本身的hash值进行异或运算（不用&或|运算是因为这两个运算概率偏向0或1，分布不够均匀）。这样做的好处就是低位保留了高位的特征, 减低了低位重复的可能，使得hash值尽量分布均匀，减少之后在确定主键位置时发生重复冲突的可能。这里用到的hash函数是散列函数，它可以使得不同长度的输入得到相同长度的结果。但具体hashCode函数怎么实现的可能需要小伙伴的帮助了。

• 步骤三：根据hash值确定该键值对在hashmap中保存的位置。即index。关于这一点，JDK1.7
  中有个函数叫indexFor(int h, int length)，（JDK1.8有所调整但原理一致），下面为源代码

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

这里我来解释一下，h – 表示hash函数计算后的结果，length表示hashmap数组长度，但为什么要让length减1呢？
在解说这点前我先把前面的坑补了，先说说为何数组的默认长度为2的幂次方（默认为16）:
数组长度为2的幂次方有个特征就是它减一后的值最高位后面的每个位上都为1，它与任何数字进行与运算（&）后获取的hash低几位的数据即为结果。

这样做有什么好处呢？好处就是使用了位运算运算快，并且拿hash的值与每位都为1的二进制数进行与运算（不是或、异或运算），减少了冲突的可能，增加了分布的均匀性。
举个例子 做与运算： 拿 1101（hash）与 0111（length-1 即8-1） 做与运算得0101（5） 拿 1111
（hash）与 0111（length-1 即8-1） 做与运算得0111（7） 但是 如果做或运算： 拿 1101（hash）与
0111（length-1 即8-1） 做或运算得0111（7） 拿 1111 （hash）与 0111（length-1 即8-1）
做与运算得0111（7） 这样就冲突啦。

总之，hash存储的过程如下： put(key,value) -> hash(key) -> indexFor(hash）-> index

那么问题又来了，这个均匀分布也不可能避免出现重复冲突的可能，在这种情况下hashmap该怎么处理? 答案很简单，那就是它会先以链表的形式存储，如果长度超过8，就会以红黑树的形式存储。

为什么之后要以红黑树形式存储？为何要选择临界值为8？
我们学过数据结构应该知道红黑树的查找长度为O(logn) 而链表则是为O(n/2)
当长度< 8 时 logn 和 n/2 的差值不大并且生成红黑树需要额外的开销因此选择链表形式进行存储，但是当长度大于8时（16,32, 64… 因为hashmap扩容是以2倍为倍率进行扩容的）logn 与 n/2 的差值就会变大，这时候红黑树无疑是更好的。

【未完待续】