首页   快速返回

HashMap和ConcurrentHashMap中的hash函数     所属分类 java
hashmap中的hash函数

java7

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);
    }

java8
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}




ConcurrentHashMap 中的hash函数 Java7 private int hash(Object k) { int h = hashSeed; if ((0 != h) && (k instanceof String)) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3); h ^= (h >>> 6); h += (h << 2) + (h << 14); return h ^ (h >>> 16); } java8 static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; } Spreads (XORs) higher bits of hash to lower and also forces top bit to 0. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds. 将(XORs)较高的哈希值扩展为较低的哈希值,并将最高位强制为0。 由于该表使用了2的幂掩码,因此仅在当前掩码之上以位为单位变化的散列集总是会发生冲突。 (已知的例子包括在小表中保存连续整数的浮点键集。) 因此,我们应用一个转换,将更高位的影响向下传播。 位扩展的速度、实用性和质量之间存在权衡。 因为许多常见的哈希集合已经得到了合理的分布(所以不要从传播中获益) 因为使用树来处理桶里的大量碰撞, 只是以最便宜的方式XOR移位一些位来减少系统损失,以及纳入最高位的影响 否则,由于表的边界,将永远不会在索引计算中使用它。 高低位异或 ,高低位同时参数计算,减少冲突概率 使用树处理桶里的大量碰撞 链表长度大于8转成红黑树

上一篇     下一篇
java8 hashmap 要点

hashmap在java7和8中的区别

java位运算

ConcurrentHashMap读不需要加锁的秘密

ConcurrentHashMap size 实现要点

37种融资模式