Last active
August 29, 2015 14:09
-
-
Save xpcoffee/4dfbeee7b95625985cb9 to your computer and use it in GitHub Desktop.
hashtable tutorial
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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