ArrayIndexOutOfBoundsException將整數值插入散列表時

我不知道錯誤在哪裏（插入表）。它是我的代碼片段（插入到開放尋址哈希表中）。線性和雙尋址都不錯，但與此（二次函數處理）的一些錯誤ArrayIndexOutOfBoundsException將整數值插入散列表時

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;

但在我看來，它的一切都很好becouse我的函數（指數）應該是這樣的：

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

來源

2013-11-26 user2898122

哪條線拋出異常？ – Taylor

我知道錯誤在哪裏：它位於OpenAddressHash.java的第101行。某處可能有一個負整數，或整數溢出。使用你的調試器。 –

計算'index'的公式可能有些問題。很難弄清楚，不知道代碼中究竟發生了什麼。 –

考慮一下當我們有一個大小爲2000的OpenAddressHash，並將c2變量設置爲1000時（如d = 500時在外部循環中做的那樣），插入時會發生什麼。

然後i可以上升至1999年，在這種情況下，你計算：

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

子表達式

c2 * i * i 
1000 * 1999 * 1999

給人-298966296，等有機會，你會得到一個負數索引，除非start + (c1 *i)將會很好。但沒有跡象表明它會這樣做，因爲c1總是1，據我所知，start比size小。

除此之外，當您插入的密鑰爲負值時，您也會得到負指數。

來源

2013-11-26 16:34:45 Ingo

我可能是不正確的，但看你的方式計算指數：

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

如果開始的值是0，那麼指數將等於大小。儘管尺寸代表數量。所以，除非你減少1，否則你可能會看到異常。反正第一次迭代。

來源

2013-11-26 16:18:32 Joe

「如果start的值爲0，那麼索引將等於大小」 - 您如何計算？我看不出任何數字的模數大小可能與大小相等。 – davmac

眼看作爲insertKwadratowe方法時發生的異常，並有在該方法中只有一個數組訪問，這個問題必須位於計算指數，即，這條線：

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

也許啓動，或C1或c2是否定的，或者你的整數溢出會導致負數。

來源

2013-11-26 16:20:13 davmac

start可以很容易地變爲負數，例如當參數'key'爲負時。另外，假設c2 = 5000，我必須小於* 655以避免溢出。 – Ingo

ArrayIndexOutOfBoundsException將整數值插入散列表時

回答

相關問題