Hi all, i am trying to do a quadratic hashing but i am having somedifficulties probably because i am not in the right logic.using thiscode:public void insert(DataItem item)       {      int key = item.getKey();      int hashVal = hashFunc(key);      int x = 0;      while(arr[hashVal] != null )      {        hashVal = hashVal + (int) Math.pow(x,2); // go to next cell        hashVal %= size;    // wraparound if necessary        x++;}      	arr[hashVal] = item;     }thi seems working ok untill something has taken the slot meant to bethe item's i am inserting at this moment, so it has to go as x + (1^2)if empty, if not x+(2^2)  *** ^ means to the power ofso on and so forth, the x++ shall occur only if the previous x couldnot been committed.would you please help?it is wrapping arround but the problem is the x++ i think, i dont knowhow to fix it, i am pretty new to java,i ll appreciate any help and thanks in advance

On Dec 22, 7:06 pm, Totti <saliba.toufic.geo...@gmail.com> wrote:> Hi all, i am trying to do a quadratic hashing but i am having some> difficulties probably because i am not in the right logic.using this> code:>> public void insert(DataItem item)>        {>       int key = item.getKey();>       int hashVal = hashFunc(key);>       int x = 0;>       while(arr[hashVal] != null )>       {>         hashVal = hashVal + (int) Math.pow(x,2); // go to next cellI am somewhat guessing, but according to your description below, Ithink you always want to use the original hashVal on the right sideexpression.Also, what's wrong with the old x*x?> so it has to go as x + (1^2) if empty, if not x+(2^2)

Totti wrote:> Hi all, i am trying to do a quadratic hashing but i am having some> difficulties probably because i am not in the right logic.using this> code:> > public void insert(DataItem item)>        {>       int key = item.getKey();>       int hashVal = hashFunc(key);>       int x = 0;>       while(arr[hashVal] != null )     This line assumes that 0 <= hashVal < arr.length, whichmay in fact be true but suggests an "unhealthy" couplingbetween arr and hashFunc.>       {>         hashVal = hashVal + (int) Math.pow(x,2); // go to next cell     Three points about this line: First, `x * x' would be agood deal simpler.  Second, x is zero on the first trip throughthe loop, so hashVal is unchanged and the first two probes willgo to the same spot in the array.  Third, if you make so manyprobes that x grows to 46341 you'll find that x*x becomes negativeand messes up the hashVal calculation (probably not a problemunless the hash table gets completely overstuffed).>         hashVal %= size;    // wraparound if necessary     I guess size is equal to arr.length, or at any rate is nolarger than arr.length?  It would be better to use arr.lengthdirectly.     How certain are you that this probe sequence will eventuallyvisit every array index?  For example, if the array size is elevenand the first hashVal is zero, locations [2], [4], [7], and [9]are untouched in the first hundred probes (unless I botched myquick-and-dirty spreadsheet).>         x++;> }>       	arr[hashVal] = item;>      }> thi seems working ok untill something has taken the slot meant to be> the item's i am inserting at this moment, [...]     It's unfortunate that you didn't reveal the manner inwhich the code fails.  You tell us it's "working ok" in someconditions, and you tell us the condition where it doesn'twork, but you don't tell us what goes wrong or why you thinkit is wrong.-- Eric Sosmanesosman@ieee-dot-org.invalid

On Sat, 22 Dec 2007 10:06:33 -0800 (PST), Totti<saliba.toufic.george@gmail.com> wrote, quoted or indirectly quotedsomeone who said :>    hashVal = hashVal + (int) Math.pow(x,2); // go to next cellx*x will work much faster than (int)Math.pow(x,2);-- Roedy Green Canadian Mind ProductsThe Java Glossaryhttp://mindprod.com

On Sat, 22 Dec 2007 10:06:33 -0800 (PST), Totti<saliba.toufic.george@gmail.com> wrote, quoted or indirectly quotedsomeone who said :>thi seems working ok untill something has taken the slot meant to be>the item's i am inserting at this moment, so it has to go as x + (1^2)>if empty, if not x+(2^2)  *** ^ means to the power of>so on and so forth, the x++ shall occur only if the previous x could>not been committed.You could just use a HashMap which handles this for you. Or you could test the cell for not-null, and if it is, increment,wrapping around till you find a free slot to put it in.see http://mindprod.com/jgloss/hashmap.html-- Roedy Green Canadian Mind ProductsThe Java Glossaryhttp://mindprod.com

Many Thanks to everybody.you were all helpful