해시 테이블에 정수 값을 삽입 할 때 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

OpenAddressHash의 크기가 2000 인 경우 insert에서 어떤 일이 발생하는지 고려하고 c2 변수를 1000으로 설정합니다 (d = 500 일 때 외부 루프에서와 마찬가지로).

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

c2 * i * i 
1000 * 1999 * 1999 

가 -298966296를 제공 서브 표현식, 그래서 기회는 당신이하지 않으면, 음의 지수를 얻을 수 있습니다

다음 i는 경우에 당신은 계산 1999까지 갈 수있다 start + (c1 *i)이 좋습니다. 그러나 내가 알 수있는 한 c1은 항상 1이고, start은 size보다 작은 것으로 표시되어 있습니다.

삽입 키가 음수이면 음수 인덱스가 표시됩니다.

Answer 2

내가 잘못 될 수도 있지만 방법을보고에서 당신은 인덱스 계산 : 시작의 ​​값이 0

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

경우, 인덱스의 크기가 같아야됩니다. 크기가 수량을 나타냅니다. 그래서, 당신이 그것을 1 씩 줄이지 않는다면, 당신은 당신이보고있는 예외로 끝날 수 있습니다. 첫 번째 반복을 위해, 어쨌든.

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

는 아마도 시작하거나, C1 또는 다음 예외 insertKwadratowe 방법에있어서 발생하고, 그 방법의 하나의 배열 액세스 거기로

Answer 3

보면 문제가이 라인 즉, 인덱스를 계산 있어야만 c2가 음수이거나, 곱셈과 함께 정수 오버플로가 발생하여 음수가 발생했을 수 있습니다.