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;
        }
View Code

 

 

简单概括一下:根据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);
    }
View Code

 

 

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;
    }
View Code

 

与插入操作差不多:算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);
    }
View Code

 

得到了hash值,需要通过哈希函数得到数组地址。这个过程称之为Hash。试想,如果12个元素一个都木有冲突,每个槽位占一个,那该才是真正的O(1)效率。多美好啊。因此我们希望冲突尽量少的发生,让每个槽位都有相同的机会得到元素。通过hash值,如何将元素映射到相应槽位呢,最常规的思路应该是取余

java源代码也是这样做的:

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

 

熟悉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();
    }
View Code

 

由代码可以看出,表容量实际并不是完全人为指定的,而是不大于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)
                    ;
            }
        }
View Code

 这个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;
        }
View Code

 

在迭代过程中的每一个操作之前,都会对ModCount进行判断,如果不相等就表示已经有其他线程修改了Map:

注意到modCount声明为volatile,保证线程之间修改的可见性。

  在HashMap的API中指出:

   由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。

   注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误 

 

参考资料:http://zhangshixi.iteye.com/blog/672697

Jdk源码

java集合框架小结(进阶版)之HashMap篇,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。