hashCode，实现以及与HashMap的关系
所以我在这里问了另一个相关的问题： 带有雪崩效应的java字符串哈希函数 ，但我现在有一个不同的相关问题。
我在那个问题中建立的是String的hashCode（）函数没有雪崩效应。 这意味着，例如，如果我有字符串“k1”，“k2”，“k3”，并且我在每个上调用hashCode（），则返回的值将是连续的。
现在，基于我对数据结构101的回忆，我的印象是这是一件坏事。 因为假设HashMap通过算法选择桶，例如：
class HashMap { private int capacity; private int chooseBucket(String key) { return key.hashCode() % capacity; } } 这意味着类似的密钥存储在连续的桶中，导致更高的冲突率，从O（1）降低大O查询时间到……谁知道有多糟糕……可能比O更差（log n ）。
我在第一个问题中得到的答案类型是“这里不需要雪崩效应”，“它仅用于加密哈希函数”，而且“字符串的hashCode实现很快，适用于小型哈希映射”。
这让我很困惑。 当它们很小时，所有数据结构都很快。 Sun是否会提供一个适用于大型数据集的默认hashCode函数？ 那时候HashMap的表现真的很重要，不是吗？
或者，我错过了什么？ 请赐教。
将密钥存储在连续的存储区中不会导致性能下降。 将密钥存储在同一个存储桶中（例如， 链接 ）可以。 使用链接解决哈希冲突时：
- 最坏情况：每个哈希值都相同，因此所有元素都在同一个桶中，在这种情况下，您获得O（n）性能（假设链是链接列表）
- 最佳情况：每个哈希值都不同，因此每个元素最终都在不同的存储桶中，因此您可以获得预期的O（1）性能。
用于散列表（等）的散列码不需要雪崩效应 。
你问“或者，我错过了什么？请赐教。”
是的，你错过了什么。
在HashMap类实现中，它可以防止糟糕的散列函数：
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // 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); }
因此，您的示例中生成的哈希码是：
k1 - Before: 3366 After: 3566 k2 - Before: 3367 After: 3567 k3 - Before: 3368 After: 3552
因此，即使你的3个元素的小样本量，其中一个被重新加入。 现在，这并不能防止恶意的hashCodes（ return randomInt();或return 4;根本无法保护）但它确实可以防止写得不好的哈希码。
我还应该指出，你可以通过使用非平凡的输入来改变很多东西。 例如考虑以下字符串。
k1longer - Before: 1237990607 After: 1304548342 k2longer - Before: 2125494288 After: 2040627866 k3longer - Before: -1281969327 After: -1178377711
注意低位有多少不同：对于哈希码来说，唯一重要的是低位。 支持映射的大小始终是2的幂。 它实际上在代码中记录了这种方式：
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;
重新散列相当不错，确保高位（通常在散列表中被忽略）仍然对低位有影响。 这是原始哈希码位置的映射及其影响的位：
00: 00000000000000000000000000000001 01: 00000000000000000000000000000010 02: 00000000000000000000000000000100 03: 00000000000000000000000000001000 04: 00000000000000000000000000010001 05: 00000000000000000000000000100010 06: 00000000000000000000000001000100 07: 00000000000000000000000010001001 08: 00000000000000000000000100010010 09: 00000000000000000000001000100100 10: 00000000000000000000010001001000 11: 00000000000000000000100010010000 12: 00000000000000000001000100100001 13: 00000000000000000010001001000010 14: 00000000000000000100010010000100 15: 00000000000000001000100100001000 16: 00000000000000010001001000010001 17: 00000000000000100010010000100010 18: 00000000000001000100100001000100 19: 00000000000010001001000010001001 20: 00000000000100010010000100010011 21: 00000000001000100100001000100110 22: 00000000010001001000010001001100 23: 00000000100010010000100010011000 # means a 1 in the 23rd bit position will 24: 00000001000100100001000100110001 # cause positions 4, 5, 8, 12, and 20 to 25: 00000010001001000010001001100010 # also be altered 26: 00000100010010000100010011000100 27: 00001000100100001000100110001001 28: 00010001001000010001001100010010 29: 00100010010000100010011000100100 30: 01000100100001000100110001001000 31: 10001001000010001001100010010000
所以，你担心“从O（1）降低大O查询时间到……谁知道有多糟糕……可能比O（log n）更差”和“Sun不会提供默认的hashCode函数适用于大型数据集吗？“ 可能会被搁置 – 他们有安全措施来防止这种情况发生。
如果它可以帮助你获得一些平静，这里是这个类的作者标签。 他们几乎都是Java世界的明星。 （评论＃是我的）
* @author Doug Lea # Formerly a Java Community Process Executive Committee member * @author Josh Bloch # Chief Java architect at Google, amongst other things * @author Arthur van Hoff # Done too many hardcore Java things to list... * @author Neal Gafter # Now a lead on the C# team at Microsoft, used to be team lead on javac
我前几天阅读了Eric Lippert的一篇博客文章，名为GetHashCode的指南和规则 。 虽然代码示例与C＃相关，但大多数一般原则同样适用于Java。 如果您想了解更多关于使用什么哈希码以及如何生成哈希码的信息，那么本文非常值得一读。
特别是，以下位似乎与您的问题特别相关：
指南：哈希码的分布必须是“随机的”
通过“随机分布”，我的意思是如果被散列的对象中存在共性，则在生成的散列码中不应存在类似的共性。
像HashMap这样的哈希函数的哈希函数需要对它的键集合理唯一，但键之间的关系（即两个键的相似程度）不需要是随机的。 我们真正想要避免的是在一个桶中的一堆对象会使搜索该桶变得昂贵。
在HashMaps和Strings的情况下，它必须将这些散列键映射到一个随机可访问容器的某个排序偏移量，例如有多个解决方案的数组，但如果两个键“关闭”，它仍将导致它们放在不同的水桶里，这是我们真正关心的。
对于非常大的Map容器（想想数十亿个键），我们可能希望更加聪明，但这似乎超出了Java的HashMap设计的范围。
最后要注意的是，您不必使用雪崩效果为字符串生成相当随机的键。 您希望选择一个足够随机且尽可能快的函数。
如果您查看HashMap的源代码，则会使用key.hashCode（）值调用哈希函数，这意味着它会通过自己的方式分配哈希值。 有一点需要确定的是不遵守equals和hashcode合同。 我建议，如果您正在寻找性能改进，请查看源代码并了解可用的桶数和最佳使用情况。