HashMap 中相似的 String 会不会增加碰撞的几率？

Question

考虑以下因素：

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

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

鉴于每个条目的键都以相同的字符串开头，并且仅在附加的数字上有所不同，这可能会导致更多的冲突吗？我正在尝试确定这种创建唯一键的方式从性能角度来看是否是个好主意。

Answer 1

不，不会。这不是必然因为 String#hashcode；但是因为 HashMap 将通过将前 16 位与最后 16 位异或来重新哈希您的哈希码。

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

但即使会增加碰撞，您也可能永远感觉不到。对于条目一个接一个（以链接方式）放置的小型 buckets/bin，将调用 equals 以获取您关心的 actual 条目。

如果某个bin/bucket达到某个阈值，它将在perfectly balanced tree node中进行转换。在这样一棵树中的搜索时间是 0(logn).

即使如果相同的条目报告相同的散列码在重新散列之后，地图仍需决定哪个条目是在平局的情况下更大。

然后它会尝试调用 Comparable#compareTo 以防您的 Keys 实现 Comparable。如果他们不执行 Comparable，则将调用 System.identityHashcode 来决定平局。

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

HashMap 中相似的 String 会不会增加碰撞的几率？

Will similar Strings in HashMap lead to increased chance of collisions?

java

hashmap

hash-collision

string-hashing