Hash Table Problems

[Eric Mitchell]

Alright, so I have been trying to write a hash table class from scratch (as a programming exercise), but when it comes to testing, nothing is coming out right! For instance my "containsKey" method will return false no matter what, and my "get(key)" method can never find the keys. I assume it is all due to ONE central problem, but I can't find it. I have spent a lot of time looking at this, and I thank you in advance for your help.

/**A class that represents Hash Tables. Does not use
any of java's predefined classes to do so. Obviously,
for use only as study*/

public class HashTable
{
private final static int listSize=10;//max size of HashTable
private static ListNode[] list= new ListNode[listSize];//holds the values of the hashTable
private static int count;//count of items

	/**Defines the nodes which hold
	 * the values and keys*/
	private class ListNode
	{
	String key;
	String value;
	ListNode next;
		
		private ListNode(String thisKey, String thisValue)
		{
		key=thisKey;
		value=thisValue;
		}
	}
	
	/**adds an item to the list*/
	public void put(String key, String value)
	{
	int location=(Math.abs(key.hashCode()) % listSize);
	ListNode newNode=new ListNode(key, value);
		if(list[location]==null)
		{
		list[location]=newNode;
		return;
		}
		else
		{
		ListNode occupiedNode=list[location];
			while(occupiedNode.next!=null)
			{
			occupiedNode=occupiedNode.next;
			}
		newNode=occupiedNode.next;
		}
	count++;//add 1 to count of items
	}
	
	/**Returns the number of items in the array*/
	public int size()
	{
	return count;
	}
	
	/**returns true if the key is in the array*/
	public boolean containsKey(String key)
	{
	int location=(Math.abs( key.hashCode() ) % listSize);
	ListNode node=list[location];
		while(node!=null)
		{
			if(node.key.equals(key))
			return true;
			else
			node=node.next;
		}
	return false;//item not found
	}
	
	/**Returns the value associated with the key.
	If the key is not found, returns null*/
	public String get(String key)
	{
	int location=(Math.abs(key.hashCode()) % listSize);
	ListNode node=list[location];
		do{
			if(node.key.equals(key))
			return node.value;
			else
			node=node.next;
		}while(node!=null);
	return null;//nothing found, returns null
	}
	
	/**Removes the key and its associated value from the
	hash table*/
	public void remove(String key)
	{
	int location=Math.abs( key.hashCode()) % listSize;
	ListNode node=list[location];
		if(node==null)//Nothing is at the array index
		return;
		else if(node.key==key)
		{
		list[location]=node.next;
		count--;
		return;
		}
		else
		{
			while(node.next!=null)
			{
			ListNode lastNode=node;
			node=node.next;
			ListNode nextNode=node.next;
				if(node.key==key)
				{
				lastNode.next=nextNode;
				count--;
				return;
				}
			}
		}
	}
	
	public static void main(String[] args)
	{
	HashTable table=new HashTable();
	String key;//the keys to be operated on, specified by user
	table.put("George Boole", "Computers");
	table.put("Albert Einstein", "Physics");
	table.put("Beethoven" , "Music");
	System.out.println("Which key should be removed?");
	key=TextIO.getln();
	table.remove(key);
	System.out.println("Does the table contain beethoven?");
	System.out.println(table.containsKey("Beethoven"));
	System.out.println("Which key's value do you want?");
	key=TextIO.getln();
	System.out.println(table.get(key));
	
	}
}

[Paul Clapham]

That's not a bad first attempt, although there's a few glitches in there. However you haven't done enough testing -- yes, your code doesn't find Beethoven because of one of those glitches, but it should find those other two guys.

Let me just point out that when your put() method tries to add a new node to your linked list of nodes, there should be a line of code which looks something like "someNode.next = someOtherNode". You don't have any such line of code. Can you see what problem that would lead to?

By the way, the fields of your HashTable shouldn't be static. You won't notice any problem if you only have one HashTable, but as soon as you have two, all hell's going to break loose.

[Eric Mitchell]

alright, I got it! Yes, I attempted to write the statement someNode.next=someOtherNode, but had instead written newNode=occupiedNode.next (Line 43). I had also written in several places, "if (...key==otherKey)" like lines 92 & 105, when it should have been "key.equals(otherKey)". Also changed variables for list and count to be non-static, Not sure what I was thinking there...Anyways, thank you so much for your help!