所以我知道散列图使用桶和散列码等等。根据我的经验,Java 哈希码并不小,但通常很大,所以我假设它没有在内部建立索引。除非哈希码质量很差导致桶长度和桶数量大致相等,否则 HashMap 比名称-> 值对列表更快的原因是什么?
最佳答案
HashMap 通过使用哈希函数将元素映射到“桶”来工作。当有人试图插入一个元素时,会计算一个散列码,并对散列码进行取模运算,以获得应该插入元素的桶索引(这就是为什么哈希码有多大并不重要)。例如,如果你有 4 个桶,你的 hashcode 是 40,它会被插入桶 0,因为 40 mod 4 是 0。
当两个元素映射到同一个桶时,会发生“冲突”,通常该元素存储在同一个桶下的列表中。
如果您尝试获取一个元素,则使用哈希函数再次映射该键。如果桶包含一个元素列表,则使用 equals() 函数来识别哪个元素是正确的(这就是为什么必须实现 equals() 和 hashcode() 以将自定义对象插入 HashMap 的原因).
因此,如果您搜索一个元素,而您的 HashMap 在桶中没有任何列表,则您的成本为 O(1)。最坏的情况是当您只有 1 个桶和一个包含所有元素的列表时,在其中获取一个元素与在列表 O(N) 上搜索相同。
关于java - 是什么让 hashmap 更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41412011/