在java中，如果不检查数组中的索引是否等于0或null，如何检查数组中的索引是否未初始化？

Question

我在做线性探测。它散列了表大小mod上的值，并为此编写了一些代码。

public class LinearProbing
{
    private int table[];
    private int size;
    LinearProbing(int size)
    {
        this.size=size;
        table=new int[size];
    }
    public void hash(int value)
    {
        int key=value%size;
        while(table[key]!=0)
        {
            key++;
            if(key==size)
            {
                key=0;
            }
        }
        table[key]=value;
    }
    public void display()
    {
        for(int i=0;i<size;i++)
        {
            System.out.println(i+"->"+table[i]);
        }
    }
}

它适用于除零（0）之外的每个值。当零在要散列的值中时，就像在java数组中一样，每个索引最初都是以零启动的。用零检查索引是否空闲，如果零要散列并且可以被覆盖，是否会引起麻烦。我还检查了null的相等性，但它会引发错误类型不匹配。

有人有什么建议吗？

Answer 1

计算机不是这样工作的，至少要付出相当大的代价。

具体来说，一个新的int[10]实际上只是创建了一个连续的内存块，该内存块精确地足以容纳10个int变量，并且不会超过这个值。具体来说，每个int将覆盖32位，这些位可以用来精确地表示2^32个不同的事物。想想看：如果我给你一个由3个电灯开关组成的面板，你所要做的就是走进来，拨动一些开关，然后再走出去，然后我走进来，看看你一直在拨动什么，这就是我们所获得的所有通信通道，我们可以预先安排8个不同的信号。为什么是8？因为这是2^3。有点像那个电灯开关。打开或关闭。没有其他选项，也没有“未设置”。除非我们在这个信号上“花费”8种不同安排中的一种，只剩下7种，否则无法表示“哦，你还没到房间”。

因此，如果您希望每个“int”也知道“是否已设置”，并且“尚未设置”与任何有效值不同，则需要一个全新的位，并且鉴于现代CPU不喜欢对子字单位进行工作，该位过于昂贵。在任何一种情况下，您都必须对其进行编程。

例如：

private int table[];
private int set[];

LinearProbing(int size) {
  this.size = size;
  this.table = new int[size];
  this.set = new int[(size + 31) / 32];
}

boolean isSet(int idx) {
  int setIdx = idx / 32;
  int bit = idx % 32;
  return this.set[setIdx] >>> bit != 0;
}

private void markAsSet(int idx) {
  int setIdx = idx / 32;
  int bit = idx % 32;
  this.set[setIdx] |= (1 << bit);
}

这台相当复杂的机器“打包”了额外的“是否已设置？”位放入一个名为set的单独数组中，我们可以将其设置为整个数组的1/32，因为每个int包含32位，我们只需要1位将索引槽标记为“unset”。不幸的是，这意味着我们需要进行各种“位争用”，因此我们使用了位OR运算符（|=）和位移位（

这就是为什么，通常情况下，这不是办法，有点争吵并不便宜。

最好的办法是去掉散列中2^32个不同值中的一个。您可以选择0，但也可以选择一些任意选择的值；选择一个大素数有一个很小的好处。比如说7549。

现在，您需要做的就是指定一个特定的算法：值的实际哈希值来自以下公式：

• 如果实际的散列值是7549，我们说实际的散列值是6961。是的，这意味着6961将更频繁地出现

多田：这个算法意味着“7549”是免费的。没有实际的散列可以是7549。这意味着我们现在可以使用7549作为标记，因为它表示“unset”。

6961现在加倍的事实在技术上并不相关：任何散列桶系统都不能仅仅声明相等的散列意味着相等的对象——毕竟，只有2^32个散列，因此从数学上讲，冲突是无法避免的。这就是为什么java自己的HashMap不只是比较哈希-它还调用.equals。如果在同一个映射中推送两个不同的（如，而不是.equals）对象，使其恰好散列到相同的值，则HashMap可以使用它。因此，在6961附近有更多冲突并不特别相关。

与6961上的额外碰撞机会相关的额外成本远远低于与跟踪已设置或未设置哪些桶相关的额外成本。毕竟，假设哈希分布良好，我们的转换算法释放了7549个条目，这意味着每40亿个条目中就有1个发生碰撞的可能性增加了两倍。这是一个无穷小的事件，在另一个无穷小的事件之上，这无关紧要。

注意：6961和7549是随机选择的质数。质数只是稍微不太可能碰撞，你在这里选择质数并不重要。