ArrayIndexOutOfBoundsException when inserting integer values into hash table

Question

I don't know where is the error (Insert into table). It's fragment of my code (inserting into open addressing hash table). Linear and double addressing are good, but with this (quadratic function addressing) its something wrong

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

I know that is something wrong with this line:

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

But in my opinion its everything good becouse my function (index) should be looks like:

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

My code:

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

I know where the error is: it's at line 101 of OpenAddressHash.java. You probably have a negative integer somewhere, or an integer overflow. Use your debugger. — JB Nizet
– JB Nizet, Commented Nov 26, 2013 at 16:11
Something's probably wrong with the formula to calculate index. Hard to figure out, not knowing what's really going on in your code. — Paul Samsotha
– Paul Samsotha, Commented Nov 26, 2013 at 16:13

Joe · Accepted Answer · 2013-11-26 16:18:32Z

1

I might be incorrect, but from looking at the way you calculate the index:

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

If the value of start is 0, then the index will be equal to size. Although, size represents the quantity. So, unless you reduce it by 1, you could end up with the exception you are seeing. For the first iteration, anyways.

answered Nov 26, 2013 at 16:18

Joe

6912 gold badges8 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

davmac Over a year ago

"If the value of start is 0, then the index will be equal to size" - how do you figure? I don't see how any number modulo size could be equal to size.

davmac · Accepted Answer · 2013-11-26 16:20:13Z

1

Seeing as the exception occurs in the insertKwadratowe method, and there's only one array access in that method, the problem must lie in calculating the index, i.e. this line:

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

Perhaps start, or c1 or c2 are negative, or perhaps you are getting an integer overflow with your multiplication resulting in a negative number.

answered Nov 26, 2013 at 16:20

davmac

20.9k1 gold badge45 silver badges72 bronze badges

1 Comment

Ingo Over a year ago

start can easily go negative, for example when the argument key is negative. Also, assuming c2=5000, i must be less than 655 to avoid overflow.

Ingo · Accepted Answer · 2013-11-26 16:39:58Z

0

Consider what happens in insert when we have an OpenAddressHash with size 2000, and set the c2 variable to 1000 (as you do in your outer loop when d=500).

Then i can go up to 1999, in which case you compute:

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

The subexpression

 c2   * i    * i
 1000 * 1999 * 1999

gives -298966296, and so chances are that you get a negative index, unless start + (c1 *i) will make it good. But there is no indication it would do that, as c1 is always 1 as far as I can see, and start is something smaller than size.

Apart from that, you get also negative index when your key to insert is negative.

edited Nov 26, 2013 at 16:39

answered Nov 26, 2013 at 16:34

Ingo

36.4k6 gold badges57 silver badges102 bronze badges

Collectives™ on Stack Overflow

ArrayIndexOutOfBoundsException when inserting integer values into hash table

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related