Skip to content

Instantly share code, notes, and snippets.

@xpcoffee
Last active August 29, 2015 14:09
Show Gist options
  • Save xpcoffee/4dfbeee7b95625985cb9 to your computer and use it in GitHub Desktop.
Save xpcoffee/4dfbeee7b95625985cb9 to your computer and use it in GitHub Desktop.
hashtable tutorial
import java.lang.NullPointerException;
import java.util.NoSuchElementException;
import java.lang.StringBuilder;
import java.util.LinkedList;
/**
* Hashtable tutorial class.
*
* Adapted from <a href="http://www.danielacton.com/Data-Structures/Hashtable/Java/>">Daniel Action</a>.
* November 2014.
*/
@SuppressWarnings({"unchecked"})
public class Hashtable {
/*
* MEMBER VARIABLES
*/
private final int tableSize = 20;
private int numElements;
/*
* ugly cast is needed to create a linkedlist array:
* http://stackoverflow.com/questions/217065/cannot-create-an-array-of-linkedlists-in-java
*/
private LinkedList<HashtableNode>[] table = (LinkedList<HashtableNode>[]) new LinkedList<?>[20];
/*
* PUBLIC METHODS
*/
/* tester class*/
public static void main(String[] args)
{
Hashtable hashtable = new Hashtable();
hashtable.add("XPC", "123 456 7890");
hashtable.add("XPC DEV", "987 6543");
System.out.println("Hashtable:");
System.out.println(hashtable);
System.out.println("get(\"Bosch family\"): " + hashtable.get("Bosch family"));
}
/* adding */
public void add(Object key, Object data)
{
/* no null keys or elements allowed */
if ((data == null) || (key == null))
throw new NullPointerException("Cannot insert null key or data into Hashtable.");
/* no duplicates allowed */
if (this.contains(key)) return;
int hash = this.hash(key);
/* if there is nothing at the position, create new linked list */
if(this.table[hash] == null)
this.table[hash] = new LinkedList<HashtableNode>();
(this.table[hash]).add(new HashtableNode(key, data));
this.numElements++;
}
public void add(Object[] keys, Object[] data)
{
if(keys.length != data.length)
throw new ArrayIndexOutOfBoundsException
("Array of keys must be the same length as array of data objects when adding to Hashtable.");
for(int i = 0; i < keys.length; i++)
this.add(keys[i], data[i]);
}
/* removing */
public void remove(Object key)
{
int hash = this.hash(key);
if (this.table[hash] == null) return;
HashtableNode node = new HashtableNode();
node.setKey(key);
if ((this.table[hash]).indexOf(node) < 0)
return;
(this.table[hash]).remove(node);
numElements--;
}
public void remove(Object[] keys)
{
for (int i = 0; i < keys.length; i++)
this.remove(keys[i]);
}
/* fetching */
public boolean contains(Object key)
{
if(numElements == 0) return false;
int hash = this.hash(key);
HashtableNode node = new HashtableNode();
node.setKey(key);
if(this.table[hash] != null)
if((this.table[hash]).indexOf(node) > -1)
return true;
return false;
}
public Object get(Object key)
{
if(numElements == 0)
throw new NoSuchElementException("Hashtable is empty.");
int hash = this.hash(key);
HashtableNode node = new HashtableNode();
node.setKey(key);
if(this.table[hash] == null)
throw new NoSuchElementException("Key-value pair not found");
int index = (this.table[hash]).indexOf(node);
if(index < 0)
throw new NoSuchElementException("Key-value pair not found");
return (this.table[hash]).get(index).getData();
}
/* outputting */
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("{\n");
for (int i = 0; i < tableSize; i++)
{
if(table[i] != null)
sb.append(table[i] + "\n");
}
sb.append("}");
return sb.toString();
}
/*
* PRIVATE METHODS
*/
/* generic hashCode */
private int hashCode(Object key)
{
/* initialize empty strings to be non-zero | 42 chosen at random */
int result = 42;
/*
* convert object into string | all objects in java have a toString method
* the default method returns string along the lines of:
* "path.to.lineofcode.ClassType@12345"
*/
String inString = key.toString().toLowerCase();
/* add up values of each character in string*/
for (char c : inString.toCharArray()) {
/* use hex numbers for a-f, else use ascii value of the character */
if ((c == 'a')
|| (c == 'b')
|| (c == 'c')
|| (c == 'd')
|| (c == 'e')
|| (c == 'f'))
{ result += Integer.parseInt("" + c, 16); }
else
{ result += (int) c; }
}
return result;
}
private int hash(Object key)
{
/* modulo a hash code with the tableSize to map the code to the backing array */
return this.hashCode(key) % tableSize;
}
/*
* PRIVATE CLASS
*/
/* internal node class */
private class HashtableNode
{
private Object key;
private Object data;
public HashtableNode()
{
this.key = null;
this.data = null;
}
public HashtableNode(Object key, Object data)
{
this.key = key;
this.data = data;
}
public Object getData()
{ return data; }
public void setData(Object data)
{ this.data = data; }
public Object getKey()
{ return key; }
public void setKey(Object key)
{ this.key = key; }
public boolean equals(Object obj)
{
if (obj == this) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) return false;
HashtableNode node = (HashtableNode) obj;
return this.key.equals(node.key);
}
public String toString()
{ return "Key: [" + this.getKey() + "] Data: [" + this.getData() + "]"; }
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment