Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / December 2007

Tip: Looking for answers? Try searching our database.

hash table quadratic probing help please

Thread view: 
Totti - 22 Dec 2007 18:06 GMT
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 cell
       hashVal %= size;    // wraparound if necessary
       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, 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.
would you please help?
it is wrapping arround but the problem is the x++ i think, i dont know
how to fix it, i am pretty new to java,
i ll appreciate any help and thanks in advance
jkohen@gmail.com - 22 Dec 2007 18:39 GMT
> 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
[quoted text clipped - 8 lines]
>       {
>         hashVal = hashVal + (int) Math.pow(x,2); // go to next cell

I am somewhat guessing, but according to your description below, I
think you always want to use the original hashVal on the right side
expression.

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)
Eric Sosman - 22 Dec 2007 19:33 GMT
> 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
[quoted text clipped - 6 lines]
>       int x = 0;
>       while(arr[hashVal] != null )

    This line assumes that 0 <= hashVal < arr.length, which
may in fact be true but suggests an "unhealthy" coupling
between arr and hashFunc.

>       {
>         hashVal = hashVal + (int) Math.pow(x,2); // go to next cell

    Three points about this line: First, `x * x' would be a
good deal simpler.  Second, x is zero on the first trip through
the loop, so hashVal is unchanged and the first two probes will
go to the same spot in the array.  Third, if you make so many
probes that x grows to 46341 you'll find that x*x becomes negative
and messes up the hashVal calculation (probably not a problem
unless the hash table gets completely overstuffed).

>         hashVal %= size;    // wraparound if necessary

    I guess size is equal to arr.length, or at any rate is no
larger than arr.length?  It would be better to use arr.length
directly.

    How certain are you that this probe sequence will eventually
visit every array index?  For example, if the array size is eleven
and the first hashVal is zero, locations [2], [4], [7], and [9]
are untouched in the first hundred probes (unless I botched my
quick-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 in
which the code fails.  You tell us it's "working ok" in some
conditions, and you tell us the condition where it doesn't
work, but you don't tell us what goes wrong or why you think
it is wrong.

Signature

Eric Sosman
esosman@ieee-dot-org.invalid

Roedy Green - 22 Dec 2007 19:57 GMT
On Sat, 22 Dec 2007 10:06:33 -0800 (PST), Totti
<saliba.toufic.george@gmail.com> wrote, quoted or indirectly quoted
someone who said :

>    hashVal = hashVal + (int) Math.pow(x,2); // go to next cell

x*x will work much faster than (int)Math.pow(x,2);
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Roedy Green - 22 Dec 2007 19:59 GMT
On Sat, 22 Dec 2007 10:06:33 -0800 (PST), Totti
<saliba.toufic.george@gmail.com> wrote, quoted or indirectly quoted
someone 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
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Totti - 22 Dec 2007 21:17 GMT
Many Thanks to everybody.
you were all helpful


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.