Home arrow static arrow Java Programming [Archive] - Searching a hash table
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Searching a hash table
This topic has 5 replies on 1 page.

Posts:3
Registered: 7/28/04
Searching a hash table  
Aug 6, 2004 2:31 AM



 
Any help on this would be greatly appreciated.

I've created a program that creates 500 ranom 3 letter strings and places these into a hash table.. I would like to be able to search the hash table for a particular given key, however I am having difficulty in working out how to do this. Would anyone be so kind as to help me work it out.

The code is supplied below:

import java.util.Random;

public class HashTable
{
public static final int charRange = 256;
public static final int tSize = 1001;

public static class Key {
String s;
int hashvalue=0;

public Key (String k) {
s = k;
for (int i = 0; i < k.length(); i++) {
hashvalue = (hashvalue*charRange + k.charAt(i)) % tSize;
}
}

public int hash() {
return hashvalue;
}

private static final String alphabet = "abcdefghijklmnopqrstuvwxyz";
private static final int kLength = 3;
private static final Random random = new Random();

public static Key random() {
char[] key = new char[kLength];
for (int i=0; i<kLength; i++)
key = alphabet.charAt(Math.abs(random.nextInt()) % alphabet.length());
String s = new String(key);
return new Key(s);
}
}

private Key[] table = new Key[tSize];

public void insert(Key k) {
int index = k.hash();
while (table[index] != null) {
index = (index+1) % tSize;
}
table[index] = k;
}

public void insert(String s) {
Key current = new Key(s);
insert(current);
}

public void showTable() {
int count = 0;
for (int i=0; i<tSize; i++) {
if (table != null) {
System.out.println(i + " key = " + table.s + " hash = " + table.hash());
count ++;
}
}
System.out.println("Number of lines ="+count);
}

public static void main(String[] args) {
HashTable rc = new HashTable();
for (int i=0; i<500; i++) {
rc.insert(Key.random());
}
rc.showTable();
}

}
 

Posts:5,965
Registered: 5/17/03
Re: Searching a hash table  
Aug 6, 2004 2:52 AM (reply 1 of 5)



 
It depends on how you handle owerflows. When you insert an object you get the table index from the hash function. If this hash table position is empty you insert the object. If not you add 1 to the index and try again. This is repeated until you find an empty spot.

To retrieve an object you must do the same. You follow the insert procedure until you find the object you're looking for or an empty position. Then you know the object's not in the table.
 

Posts:3
Registered: 7/28/04
Re: Searching a hash table  
Aug 6, 2004 3:02 AM (reply 2 of 5)



 
Thanks very much for your help. How would i go about getting the user to input the key that they wish to search for.. I've tried getting the user to input an integer but this is not what i want, it's a key that is required and im not sure how to go about this.
 

Posts:18,384
Registered: 21.03.00
Re: Searching a hash table  
Aug 6, 2004 3:32 AM (reply 3 of 5)



 
Hmm... I don't like the approach to look for an empty spot in the next index during insert. The hashtable should normally have an array of lists. And you always insert a value in the correct bucket, but last in the list found in that bucket.

/Kaj
 

Posts:5,965
Registered: 5/17/03
Re: Searching a hash table  
Aug 6, 2004 8:20 AM (reply 4 of 5)



 
Thanks very much for your help. How would i go about
getting the user to input the key that they wish to
search for.. I've tried getting the user to input an
integer but this is not what i want, it's a key that
is required and im not sure how to go about this.

The key doesn't have to be an integer. It can be anything. Normally a hash table is used to map keys to values. It's the job of the hash function to transform the key to an index position within the range of the hash table.

In Java this process has been standardized and happens in two steps. The first step is performed by the classes. To function as a key in a standard hash table based collection, like HashMap and HashSet, a class must provide a method called hashCode. This method returns an integer which should be based on the content of the object. This integer is then further mapped to the actual hash table held by the collection. All standard classes, like Integer and String, provide a hashCode method which can be used by a collection.

Anyway the general principle is that the key, whatever it is, is transformed to an index position by the hash function.
 

Posts:5,965
Registered: 5/17/03
Re: Searching a hash table  
Aug 6, 2004 8:31 AM (reply 5 of 5)



 
Hmm... I don't like the approach to look for an empty
spot in the next index during insert. The hashtable
should normally have an array of lists. And you always
insert a value in the correct bucket, but last in the
list found in that bucket.

I agree with that. The OP has chosen linear probing, the simplest form of so called open adderessing. If you want to be able to remove entries, overflows are better handled by direct chaining (objects that land at the same index position are stored in a linked list or array at that position in the hash table)
 
This topic has 5 replies on 1 page.