基础知识-HashMap实现与原理

2017-12-25

面试

哈希表

又称为散列表（HashTable），应用场景诸如缓存技术（memcached），xxx 等

几种数据机构在新增，查找等基础操作的执行性能

数组，指定下标查找 O(1)，指定值查找 O(n)（有序的情况下二分，插值可以达到 O(logn)），新增 O(n)
线性链表，查找 O(n)，新增 O(1)
二叉树，对一棵相对平衡的有序二叉树，新增和查找操作平均 O(logn)
哈希表，不考虑哈希冲突的情况下，新增和查找平均为 O(1)

哈希表的实质：数组 A + 哈希函数 + 解决哈希冲突的方案

而对于数组的下表，即元素的存储位置是通过哈希函数计算出来的，这个哈希函数就是 f，有以下公式

存储位置 = f(关键字)，f 为哈希函数

哈希表的一切操作前提是通过这个哈希函数，找到元素的存储位置，继而进行操作，可在找存储位置的时候，一旦发现已经先有元素占用了，这就引发了哈希冲突问题

哈希冲突： f(i) = f(j)，i ≠ j

没有完美的哈希函数存在，好的哈希函数会尽可能地保证 计算简单 和 散列地址分布均匀，一旦冲突发生，有以下解决方案：

开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），
二次散列函数法
链地址法（HashMap）也就是数组+链表的方式

HashMap 实现原理：数组 + 链表

数组

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;
	
	Node(int hash, K key, V value, Node<K,V> 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);
	}

	public final V setValue(V newValue) {
		V oldValue = value;
		value = newValue;
		return oldValue;
	}

	public final boolean equals(Object o) {
		if (o == this)
			return true;
		if (o instanceof Map.Entry) {
			Map.Entry<?,?> e = (Map.Entry<?,?>)o;
			if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) 
				return true;
		}
		return false;
	}
   }

HashMap 其实就是一个以上 Entry 数组，Entry 对象中包含了键和值，其中 next 也是一个 Entry 对象，它就是用来处理 hash 冲突的，形成一个链表

几个重要的因素

//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

哈希函数

//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
	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);
}

注意：

重写 equals 方法需同时重写 hashCode 方法，因为 HashMap 是通过 hashCode 进行映射的，如果不重写则映射不到 value
putIfAbsent 是线程安全的，这个方法等价于在key不存在的时候加入一个值，如果key存在就不放入，记得判断返回值