HashMap中类似的Strings是否会导致发生碰撞的机会增加？

小编典典

HashMap中类似的Strings是否会导致发生碰撞的机会增加？

java

考虑以下：

HashMap<String, Object> hm = new HashMap<>();
final String prefix = "My objects ";
int counter = 0;

void put(Object value) {
    hm.put(prefix+(counter++), value);
}

假设每个条目的键都以相同的字符串开头，并且仅相差一个附加的数字，这是否可能导致更多的冲突？从性能的角度来看，我试图确定这种创建唯一密钥的方法是否是一个好主意。

阅读 192

2020-12-03

共1个答案

小编典典

不，不会。那 不一定 是因为String#hashcode; 但是因为a
HashMap会通过对最后16个16位进行XOR运算来重新哈希您的哈希码。

// this is re-hashing that is done internally
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

但是，即使那会增加碰撞，您也可能永远不会感觉到。对于将条目逐个放置（以链接的方式）的小桶/箱，equals将被调用以获取您关心的实际
条目。

如果某个仓位/存储桶达到某个阈值，它将被转换为perfectly balanced tree node。这样的树中的搜索时间为0(logn)。

即使相同的条目在重新哈希后报告了相同的哈希码，如果出现平局，地图也必须决定哪个条目较大。

然后Comparable#compareTo，如果您的键实现了Comparable
，它将尝试调用。如果他们不执行Comparable，System.identityHashcode将在平局的情况下决定。

从性能角度来说，由于所有这些内部因素，您的平均搜索时间将O(1)在地图中。

2020-12-03