重视网站阵地建设,wordpress怎么做网站,东莞整站排名,怎么做企业功能网站总览 用于哈希键的策略可以直接影响哈希集合#xff08;例如HashMap或HashSet#xff09;的性能。 内置的哈希函数被设计为通用的#xff0c;并且可以在各种用例中很好地工作。 我们可以做得更好#xff0c;特别是如果您对用例有一个很好的了解吗#xff1f; 测试哈希策… 总览 用于哈希键的策略可以直接影响哈希集合例如HashMap或HashSet的性能。 内置的哈希函数被设计为通用的并且可以在各种用例中很好地工作。 我们可以做得更好特别是如果您对用例有一个很好的了解吗 测试哈希策略 在上一篇文章中我介绍了多种测试哈希策略的方法特别是针对“正交位”进行了优化的哈希策略该方法旨在确保每个哈希结果仅基于一个比特就尽可能地不同变化。 但是如果您有一组已知的要散列的元素/键则可以针对该特定用例进行优化而不是尝试查找通用解决方案。 减少碰撞 您希望避免在哈希集合中发生的主要事情之一是冲突。 这是两个或更多键映射到同一存储桶时。 这些冲突意味着您必须做更多的工作来检查密钥是否与您期望的一致因为同一存储桶中现在有多个密钥。 理想情况下每个存储桶中最多有一个密钥。 我只需要唯一的哈希码不是吗 一个常见的误解是为了避免冲突您需要拥有唯一的哈希码。 尽管非常需要唯一的哈希码但这还不够。 假设您有一组密钥并且所有密钥都有唯一的32位哈希码。 如果您有一个包含40亿个存储桶的数组则每个键都有其自己的存储桶并且不会发生冲突。 对于所有散列集合通常不希望具有如此大的数组。 实际上对于2 ^ 30或刚刚超过10亿的数组HashMap和HashSet受2大小的最大幂限制。 当您拥有更切合实际的散列集合时会发生什么 存储桶的数量需要更小并且哈希码被模块化为存储桶的数量。 如果存储桶数是2的幂则可以使用最低位的掩码。 让我们来看一个示例ftse350.csv。如果将第一列作为键或元素则将获得352个字符串。 这些字符串具有唯一的String.hashCode但是说我们采用这些哈希码的低位。 我们看到碰撞了吗 面具 屏蔽了String.hashCode HashMap.hash 屏蔽了String.hashCode 32位 没有碰撞 没有碰撞 16位 1次碰撞 3次碰撞 15位 2次碰撞 4次碰撞 14位 6次碰撞 6次碰撞 13位 11次碰撞 9次碰撞 12位 17次碰撞 15次碰撞 11位 29次碰撞 25次碰撞 10位 57次碰撞 50次碰撞 9位 103次碰撞 92次碰撞 HashMap的大小负载因子为0.7默认值是512它使用低9位的掩码。 如您所见即使我们从唯一的哈希码开始仍有大约30的键发生冲突。 HashTesterMain的代码在这里。 为了减少不良哈希策略的影响HashMap使用了一种搅拌函数。 在Java 8中这非常简单。 从HashMap.hash的源代码中您可以阅读Javadoc以获得更多详细信息 static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 这将哈希码的高位与低位混合以改善低位的随机性。 对于上述高碰撞率的情况存在改进。 请参阅第三列。 看一下String的哈希函数 String.hashCode的代码 public int hashCode() {int h hash;if (h 0 value.length 0) {char val[] value;for (int i 0; i value.length; i) {h 31 * h val[i];}hash h;}return h;
} 注意 String的实现是在Javadoc中定义的因此几乎没有机会更改它但是可以定义新的哈希策略。 哈希策略的组成部分。 在散列策略中我要看两部分。 魔术数字。 您可以尝试不同的数字以找到最佳结果。 代码的结构。 您需要一种结构对于任何理智的幻数选择都能获得良好的结果。 尽管幻数很重要但您不希望它们太重要的原因是对于给定的用例您总是有可能选择不正确的幻数。 这就是为什么您还想要一种即使在选择不正确的幻数的情况下也具有最低的最坏情况结果的代码结构的原因。 让我们尝试一些不同的乘数而不是31。 乘数 碰撞 1个 230 2 167 3 113 4 99 5 105 6 102 7 93 8 90 9 100 10 91 11 91 您会看到魔术数字的选择很重要但是也有很多数字可供尝试。 我们需要编写一个测试来尝试一个好的随机选择。 HashSearchMain的来源 哈希函数 最佳乘数 最低的碰撞 最差的乘数 最高碰撞 hash 130795 81次碰撞 126975 250次碰撞 xorShift16哈希 2104137237 68次碰撞 -1207975937 237次碰撞 addShift16hash 805603055 68次碰撞 -1040130049 243次碰撞 xorShift16n9hash 841248317 69次碰撞 467648511 177次碰撞 要看的关键代码是 public static int hash(String s, int multiplier) {int h 0;for (int i 0; i s.length(); i) {h multiplier * h s.charAt(i);}return h;
}private static int xorShift16(int hash) {return hash ^ (hash 16);
}private static int addShift16(int hash) {return hash (hash 16);
}private static int xorShift16n9(int hash) {hash ^ (hash 16);hash ^ (hash 9);return hash;
} 如您所见如果您提供一个良好的乘数或者一个乘数恰好与您的键集配合使用则每个哈希加下一个字符的重复乘数是合理的。 如果将130795作为乘数而不是31作为乘数则对于测试的密钥集您只会得到81次碰撞而不是103次碰撞。 如果同时使用搅拌功能则可能发生68次碰撞。 这接近两倍于数组大小的相同冲突率。 也就是说无需使用更多内存即可提高碰撞率。 但是当我们向哈希集合添加新密钥时会发生什么我们的幻数仍然对我们有利吗 在这里我着眼于最差的碰撞率以确定在更大范围的可能输入下哪种结构可能产生良好的结果。 hash的最坏情况是250次碰撞即70的键碰撞这非常糟糕。 搅动功能对此有所改善但是仍然不是很好。 注意如果添加移位后的值而不是对其进行异或运算则在这种情况下会得到较差的结果。 但是如果我们进行两次移位不仅要混合最高位和最低位还要混合生成的哈希码的四个不同部分的位我们发现最坏情况下的冲突率要低得多。 这向我表明如果更改键的选择则由于结构更好且魔术数字的选择或输入的选择的重要性降低我们不太可能收到不好的结果。 如果我们在哈希函数中添加而不是xor怎么办 在搅拌功能中使用xor可能比使用add更好。 如果我们改变这个会发生什么 h multiplier * h s.charAt(i); 与 h multiplier * h ^ s.charAt(i); 哈希函数 最佳乘数 最低的碰撞 最差分数 最高碰撞 hash 1724087 78次碰撞 247297 285次碰撞 xorShift16哈希 701377257 68次碰撞 -369082367 271次碰撞 addShift16hash -1537823509 67次碰撞 -1409310719 290次碰撞 xorShift16n9hash 1638982843 68次碰撞 1210040321 206次碰撞 最佳情况下的数字稍好一些但是最坏情况下的碰撞率则更高。 这向我表明幻数的选择更重要但这也意味着键的选择更重要。 这似乎是一个冒险的选择因为您必须考虑密钥可能会随着时间而变化。 为什么我们选择奇数乘数 当您乘以奇数时结果的低位机会等于0或1。这是因为0 * 1 0和1 * 1 1。但是如果您将其乘以偶数则低位总是为0。即不再是随机的。 假设我们重复了先前的测试但仅使用偶数这看起来如何 哈希函数 最佳乘数 最低的碰撞 最差分数 最高碰撞 hash 82598 81次碰撞 290816 325次碰撞 xorShift16哈希 1294373564 68次碰撞 1912651776 301次碰撞 addShift16hash 448521724 69次碰撞 872472576 306次碰撞 xorShift16n9hash 1159351160 66次碰撞 721551872 212次碰撞 如果您很幸运并且为您的魔术数字输入了正确的结果则结果与奇数一样好但是如果您很不幸结果可能会很糟糕。 325次碰撞意味着仅使用了512个铲斗中的27个。 更多高级哈希策略有何不同 对于基于CityMurmurXXHash和Vanilla Hash我们自己的的哈希策略 散列策略一次读取64位数据的速度比逐字节读取数据的速度快。 计算的工作值是两个64位值。 工作值减少到64位长。 结果使用了更多的乘法常数。 搅拌功能更为复杂。 我们在实现中使用长哈希码为 我们针对64位处理器进行了优化 Java中最长的原始数据类型是64位并且 如果您有大量的哈希集合即数百万个则32位哈希不太可能是唯一的。 综上所述 通过探索我们如何生成哈希码我们找到了将352个键的冲突次数从103个冲突减少到68个冲突的方法但是与更改键集相比有一定的信心我们已经减少了可能产生的影响。 这无需使用更多的内存甚至不需要更多的处理能力。 我们仍然可以选择使用更多的内存。 为了进行比较您可以看到将数组的大小加倍可以改善最佳情况但是仍然存在一个问题即键集和幻数之间的未命中匹配仍然会具有较高的冲突率。 哈希函数 最佳乘数 最低的碰撞 最差分数 最高碰撞 hash 2924091 37次碰撞 117759 250次碰撞 xorShift16哈希 543157075 25次碰撞 – 469729279 237次碰撞 addShift16hash -1843751569 25次碰撞 – 1501097607 205次碰撞 xorShift16n9hash -2109862879 27次碰撞 -2082455553 172次碰撞 结论 在具有稳定密钥集的情况下可以通过调整所使用的哈希策略来显着提高冲突率。 您还需要进行测试这些测试表明如果密钥集在不重新优化的情况下发生更改可能会变得很糟糕。 结合使用这两种方法您可以开发新的哈希策略来提高性能而不必使用更多的内存或更多的CPU。 翻译自: https://www.javacodegeeks.com/2015/09/an-introduction-to-optimising-a-hashing-strategy.html
