-10

我正在浏览 HashMap 并阅读以下分析..

  1. HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。

  2. 容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。

  3. 负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。

  4. 当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表的桶数大约增加一倍。

  5. 默认初始容量为 16，默认负载因子为 0.75。您可以在地图的构造函数中提供其他值。

现在假设我有一张地图..

HashMap map=new HashMap();//HashMap key random order.
         System.out.println("Amit".hashCode());
         map.put("Amit","Java");
         map.put("mAit","J2EE");
         map.put("Saral","J2rrrEE");

我想发生碰撞请告知碰撞将如何发生..!!

4

4 回答 4

2

我相信确切的哈希图行为取决于实现。只要看看你的类库正在做散列并构造一个冲突。这很简单。

如果你想在任意对象而不是字符串上发生冲突，那就容易多了。hashCode()只需使用always的自定义创建一个类returns 0。

于 2012-08-05T05:30:05.533 回答
1

如果您希望发生真正的冲突，那么最好编写自己的自定义哈希码。比如说，如果你想要和冲突Amit，mAit你可以做一件事，只需使用字符的 ascii 值作为哈希码。你会因为不同的键而发生冲突。

于 2012-08-05T05:42:01.097 回答
0

当 2 个 key 具有相同的 hash key 时会发生冲突。我没有计算你的键散列键，但我不认为它们具有相同的散列键，因此如果它们没有相同的散列键，则不会发生冲突。如果您将与键相同的字符串放在一起，则会发生冲突

于 2012-08-05T05:32:44.613 回答
0

这里的冲突绝对是可能的，并且与哈希表实现无关。 HashMap在内部使用Object.hashCode将对象映射到存储桶，然后使用Object.equals的冲突解决机制（OpenJDK 实现使用分离链） 。

为了回答您的问题，String.hashCode为兼容性而明确定义...

返回此字符串的哈希码。对象的哈希码String计算为 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用int算术运算，其中s[i]是字符串的第i个字符，是字符串n的长度，^表示取幂。（空字符串的哈希值为零。）

或者，在代码中（来自OpenJDK）

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

与任何散列函数一样，冲突是可能的。根据Wikipedia article，它指出，例如，"FB"和"Ea"导致相同的值。

如果你想要更多，在这里找到具有相同哈希值的冲突应该是一个微不足道的暴力问题。

作为旁注，我想我会指出这与The C Programming Language第二版中的函数非常相似：

#define HASHSIZE 100

unsigned hash(char *s)
{
    unsigned hashval;

     for(hashval = 0; *s != '\0'; s++)
         hashval = *s + 31 * hashval;

     return hashval % HASHSIZE;
}
于 2012-08-05T22:18:28.040 回答