Quick question about java hashtables....

[SnoopCat]

ok heres my problem....

im reading in this file

{
[start]
Java is [X] fancy! ;
This [Y] ! ;
}

{
[X]
very ;
[X] very ;
}

{
[Y]
[Z] cool ;
rocks ;
}

{
[Z]
is really ;
could be ;
}




as you can see, there are 4 possible states ( [start], [X], [Y], [Z] )
i made a hash function where it adds up all the ascii values so..

[start] = 742
[X] = 272
[Y] = 273
[Z] = 274

mod each of those number by 4, because i am planning to put each in a different cell in an array....so now it looks like this after the mod....

[start] = 2
[X] = 0
[Y] = 1
[Z] = 2


as u can see, [start] and [Z] has the same number, so both will try and go into the same array cell... i think this is called a "collision". I cant figure out a way to resolve it... ive been looking at my book for a while and its unclear to me.... anyone know how to fix this problem? i will need to look up this values later in the program too.

 

[br0wn]

I'm not certain about the problem that you are stating.

Let me guess:
1.
PROBLEM:
The four states the only one you need to hash and store
into the array (or for indexing)?
SOLUTION:
Then, you don't need to hash........just create something
like alias......
START = 0
X = 1
Y = 2
Z = 3
That will solve your problem.

2.
PROBLEM:
You have more than four states, and you have more than 4 cells
in your array.
SOLUTION:
Need to find hashing function that will not introduce collision.
Basically, you are looking for a perfect hash. The function will
depend on the charasteristic of the inputs. I can't give you
any suggestion since I don't know what are the inputs.


Other solution for no 2:
You might want to use an array of linked list.
Each cell in the array is a linked list, so when a collision
occurs, you can still store both datas (or even more than two).

BTW, creating a hash function with mod by 4 is not very effective...
you should try mod by a prime number.