java集合框架小结(进阶版)之HashMap篇
基本概念:
Hash(哈希):hash一般也译作“散列”。事实上,就是一个函数,用于直接定址。将数据元素的关键字key作为变量,通过哈希函数,计算生成该元素的存储地址。
冲突:函数是可以多对一的。即:多个自变量可以映射到同一函数值。一般而言,不同的key的hash值是不同的。在往hash表中映射的时候,不同的hash值可能映射到同一存储地址,这种情况被称为冲突。
解决冲突的方法:
1. 链表法:将冲突的各个元素用一个一维数组来维护。(java源码实现)
2. 开发寻址法:具体的有线性探测法、二次探测法、随机探测法等。
3. 桶定址法。
装载因子:哈希表的实际元素数(n)/哈希表的槽数(m)。
装载因子是对哈希表装载程度的一个有效衡量。越大则表示哈希表填装程度越高,反之越小。java中默认的装载因子为0.75。
装载因子越大,哈希表的空置槽位,对空间利用率越高,然而会降低查找效率。(本文均假设装载因子= 0.75,哈希表槽数为16。试想,当填装了12个元素之后,继续往里面添加,势必增加冲突的可能)
装载因子越小,冲突概率越小,但是哈希表过于稀疏,空间过于浪费。
因此装载因子是个需要权衡的常量。当超过阈值时,哈希表要进行扩容。因此还需要再哈希。
-------------------------------------------------------------------------↑基本概念↑,↓正文↓---------------------------------------------------------------------------------
初识HashMap
如java集合框架小结(初级版)中所示,HashMap是Map接口的一个非线程安全的基于hash表的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
数据结构:
下面结合源代码来看下HashMap:
1 transient Entry<K,V>[] table; 2 3 static class Entry<K,V> implements Map.Entry<K,V> { 4 final K key; 5 V value; 6 Entry<K,V> next; 7 int hash; 8 .......... 9 }
代码中可以看出,HashMap的内部结构实际上是一个Entry<k,v>数组,而Entry<k,v>同时是一个单链表节点。因此可以看出HashMap实际上就是由链表组成的数组结构。
常用操作:
put操作:
/** 在map中为特定的键值对分配空间,如果该key之前已经被赋值,则将其覆盖 * 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);//得到hash值 int i = indexFor(hash, table.length);//根据hash值找到相应槽位 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))) {//如果找到了原key所映射的旧key-value对,覆盖掉 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }
modCount++;//fail-fast机制,后面讲
//没有找到冲突,则将entry加载到该链表头部
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n;//头插法 key = k; hash = h; }
简单概括一下:根据key计算hash值,根据hash值找到映射槽位,槽位不空,看是否需要覆盖。不需要覆盖,则将该k-v对插在链表头(思考:为什么要用头插法?)
再对插入操作小结一下:
1.算hash值 -> 找槽位 -> 槽位不空,看是否需要覆盖 -> 不需要则头插法。
当插入元素过多的时候,势必会超过阈值(装载因子 * 表容量),这是就需要对hash表进行扩容,这是就要进行再哈希rehash。
resize(rehash):
阈值 = 装载因子 * 表容量。
超过阈值就需要对表进行扩容,与ArrayList道理差不多。区别是,ArrayList每次扩充一半,Hash表每次扩容一倍。然后再做一次hash算法。重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
get操作:
get操作相对比较简单。结合代码来看:
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
与插入操作差不多:算hash值 -> 找槽位 -> 槽位不空,遍历查找。
Hash与哈希函数:
hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。
final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
得到了hash值,需要通过哈希函数得到数组地址。这个过程称之为Hash。试想,如果12个元素一个都木有冲突,每个槽位占一个,那该才是真正的O(1)效率。多美好啊。因此我们希望冲突尽量少的发生,让每个槽位都有相同的机会得到元素。通过hash值,如何将元素映射到相应槽位呢,最常规的思路应该是取余。
java源代码也是这样做的:
static int indexFor(int h, int length) { return h & (length-1); }
熟悉2进制操作的同学对n&(n - 1)应该不会陌生。那个是求n的2进制的1的个数滴。这个h&(length - 1)与n&(n-1)是否有联系呢?事实上,的确如此。
public HashMap(int initialCapacity, float loadFactor) { .... // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;//表容量是成倍增加的 .... init(); }
由代码可以看出,表容量实际并不是完全人为指定的,而是不大于initialCapacity的最大的2的指数倍。有点拗口,看代码比较明白。
这样做有什么好处呢?例如length = 16(10000)length - 1之后即为01111,而下标的范围为(0000~1111)因此,每个下标都是可以被访问到的。如果length不是2的指数倍的话,就存在不能被访问到的槽位了,例如length = 0x10100,length - 1为0x10011,下标范围为(00000~10011)那么第2,3位为1的槽位例如01100(12),01101(13),011010(14),01111(15)等都将无妨访问到(思考一下);这样毫无疑问,浪费了空间利用率,增大了碰撞率。
Fail-Fast机制:
java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。
这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。
HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } }
这个expectedModCount名字起的是在是太好了~\(≧▽≦)/~
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; }
在迭代过程中的每一个操作之前,都会对ModCount进行判断,如果不相等就表示已经有其他线程修改了Map:
注意到modCount声明为volatile,保证线程之间修改的可见性。
在HashMap的API中指出:
由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。
注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
参考资料:http://zhangshixi.iteye.com/blog/672697
Jdk源码
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。