java - 将整数值插入哈希表时出现 ArrayIndexOutOfBoundsException

Question

我不知道错误在哪里(插入表)。这是我的代码片段(插入开放寻址哈希表)。线性和双寻址都很好，但是这个(二次函数寻址)就出了问题

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -848
    at openaddresshash.OpenAddressHash.insertKwadratowe(OpenAddressHash.java:101)
    at openaddresshash.OpenAddressHash.main(OpenAddressHash.java:261)
Java Result: 1

我知道这行有问题:

int index = ((start + (c1 * i) + (c2 * i * i))) % size;

但在我看来，一切都很好，因为我的函数(索引)应该如下所示:

h(k,i) = (h'(k) + c1*i + c2*i^2) mod m
where h'(k) = k mod m

我的代码:

for( int d = 25; d<=2500; d+=25)
{
    int liczba=4*d;
    OpenAddressHash hstb = new OpenAddressHash(liczba);
    int jj=2*d;
    hstb.AdresowanieKwadratoweDane(1, jj);

    Losowania los = new Losowania(); // random values
    los.Losowe(liczba); 

    for(int yy=0; yy<liczba; yy++)
    {
        hstb.insertKwadratowe(los.trzy[yy]);//trzy is a table with random values 
        if((yy%(Math.ceil(liczba/50)))==0)
        {
            AdresowanieKwadratowe.println( liczba+" "+yy+" "+hstb.s );
        } 
        hstb.s=0;
    }

}

static public class SLOT
{
    public int key;
    public STATUS stat;

    public SLOT()
    {
        stat = STATUS.INVALID;
    }
}

public void AdresowanieKwadratoweDane(int c1, int c2)
{
    this.c1 = c1;
    this.c2 = c2;
}

public OpenAddressHash(int n)
{
    table = new SLOT[n];
    for (int i = 0; i < table.length; i++)
    {
        table[i] = new SLOT();
    }
}

public int insertKwadratowe(int key)
{
    int size = table.length;
    int start = key%size;
    for (int i = 0; i < size; i++)
    {
        s++;
        int index = ((start + (c1 * i) + (c2 * i * i))) % size;
        if (table[index].stat == STATUS.INVALID ||
                table[index].stat == STATUS.DELETED)
        {
            table[index] = new SLOT();
            table[index].key = key;
            table[index].stat = STATUS.OCCUPIED;

            return index;
        }
    }
    return -1;
}

public void AdresowanieKwadratoweDane(int c1, int c2)
{
    this.c1 = c1;
    this.c2 = c2;
}

Answer 1

我可能是不正确的，但从你计算指数的方式来看:

int index = ((start + (c1 * i) + (c2 * i * i))) % size;

如果start的值为0，那么索引将等于size。虽然，尺寸代表数量。因此，除非将其减少 1，否则最终可能会出现您所看到的异常。无论如何，对于第一次迭代。