hashing

[xangel31x]

i am stuck on my program. i have to make a hash table and enter the data from the list of into the table. i have amount of data that i need and the loadfactor(the number of slots) i just don't know how to go about actually creating the initTable. it is suppose to initialize the hash table size. i am confused and hope that some one understands what i am trying to say. thanks in advance.

[Belisarius]

I'm not quite following what the problem is . . . you don't know how to create the underlying data structure for the hash table? Or is it something else?

[xangel31x]

yes i don't know how to create the actual table to then insert the data into it.

[Belisarius]

It's not actually a table, but rather an array. The hash() method returns a suitably random number (but will always return the same number for the same value). The position in the array is that hash value. As a result, in an infinitely large hash table, there is no searching for values, you just go to it's position and retrieve it. Of course, no hash table is of infinite size, so the question becomes "what if the hash value is outside the length of the array"? You use a modulus operator to loop back around and start from the beginning.

Say you have a hash table of size "10", but your Object has a hash value of "11" - where does it get inserted? At position "1", because 11 % 10 = 1.

Now, what if that spot is already occupied? That is known as a collision. There are a number of different ways of dealing with it, but the simplest is to merely move down the array until you find an empty spot. When someone wants to look up an object in the hash table, you look at what's contained at the spot that it hashes to. If it doesn't match the key of the object you're looking for, continue down the array until you either find it or loop. It's not terribly efficient in the case of collisions, but it's easy to code and I assume that's what you're looking for right now.

[xangel31x]

thanks for all the information but i already knew that. i have to create a initTable and that sets the table size and puts all the strings to empty and i am not really sure what to do for that. i really lost on this lab.

[Belisarius]

Are you talking about initializing the array?

[xangel31x]

yes

[Belisarius]

Object[] array = new Object[initSize];