美文网首页
JAVA非并发容器--HashMap-hash规则

JAVA非并发容器--HashMap-hash规则

作者: 小犇手K线研究员 | 来源:发表于2017-03-14 20:58 被阅读160次

    概述

    我相信只要写过JAVA的程序要拿99%的都用过HashMap, 其是我们最常用,也是最基础的一个Map.本篇文章将从存储结构、hash规则、扩容策略、迭代器四方面来分析其源代码。

    hash规则

    当调用get,put后,首先需要计算key的hash值--hash(key),然后计算在数组中的index--indexFor(hash, table.length).
    hash(key):

      final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            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(key)为什么这么写?遵循一个原则:减少hash冲突,说实话,我也没有深入研究why.
    indexFor(hash, table.length):

    static int indexFor(int h, int length) {
            // assert Integer.bitCount(length) == 1 : "length must be a non-    zero power of 2";
            return h & (length-1);
        }
    

    这句代码很有意思,它隐含了一个条件: table.length一个的2的n次方,
    从而用&代替%,提高效率。
    hashSeed, 在计算hash的时候,用到了一个hash种子:hashSeed,其是怎么得来的呢?

    final boolean initHashSeedAsNeeded(int capacity) {
            boolean currentAltHashing = hashSeed != 0;
            boolean useAltHashing = sun.misc.VM.isBooted() &&
                    (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
            boolean switching = currentAltHashing ^ useAltHashing;
            if (switching) {
                hashSeed = useAltHashing
                    ? sun.misc.Hashing.randomHashSeed(this)
                    : 0;
            }
            return switching;
        }
    

    Holder:

        private static class Holder {
    
            /**
             * Table capacity above which to switch to use alternative hashing.
             */
            static final int ALTERNATIVE_HASHING_THRESHOLD;
    
            static {
                String altThreshold = java.security.AccessController.doPrivileged(
                    new sun.security.action.GetPropertyAction(
                        "jdk.map.althashing.threshold"));
    
                int threshold;
                try {
                    threshold = (null != altThreshold)
                            ? Integer.parseInt(altThreshold)
                            : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
    
                    // disable alternative hashing if -1
                    if (threshold == -1) {
                        threshold = Integer.MAX_VALUE;
                    }
    
                    if (threshold < 0) {
                        throw new IllegalArgumentException("value must be positive integer.");
                    }
                } catch(IllegalArgumentException failed) {
                    throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
                }
                ALTERNATIVE_HASHING_THRESHOLD = threshold;
            }
        }
    

    这个地发,没理解透.

    相关文章

      网友评论

          本文标题:JAVA非并发容器--HashMap-hash规则

          本文链接:https://www.haomeiwen.com/subject/dgqknttx.html