Last active
August 29, 2015 14:12
-
-
Save jonalmeida/b561c594f58091a8d387 to your computer and use it in GitHub Desktop.
Simple hash table in Java with add(), remove() and getElement()
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
package com.jonalmeida.HashTable; | |
public class HashTable<T> { | |
static final int DEFAULT_INITIAL_SIZE = 16; | |
private Node<T>[] table; | |
// Create a HashTable with an array size of `initialCapacity`. | |
public HashTable(int initialCapacity) { | |
if (initialCapacity < 0) { | |
throw new IllegalArgumentException("initialCapacity is of a negative number."); | |
} else { | |
table = new Node[initialCapacity]; | |
} | |
} | |
// Create a HashTable with an array size of `DEFAULT_INITIAL_SIZE`. | |
public HashTable() { | |
table = new Node[DEFAULT_INITIAL_SIZE]; | |
} | |
// Inserts a new key-value pair into the hash table. | |
public void insert(T key, T value) { | |
Node<T> newNode = new Node(key, value); | |
int possiblePosition = calculatePosition(key); | |
if (table[possiblePosition] == null) { // The first position is empty | |
table[possiblePosition] = newNode; | |
} else { // We should add the new node to the bucket in that position | |
Node retrievedNode = table[possiblePosition]; | |
while (retrievedNode != null) { | |
// If we find that the key already exists, | |
// we replace the value with the new one | |
if (retrievedNode.getKey() == key) { | |
retrievedNode.setValue(value); | |
return; | |
} | |
// If the next node doesn't exist, | |
// we're at the end of the list. | |
if (retrievedNode.getNext() == null) { | |
retrievedNode.setNext(newNode); | |
newNode.setPrev(retrievedNode); | |
return; | |
} | |
// Looping | |
retrievedNode = retrievedNode.getNext(); | |
} | |
} | |
} | |
// Removes the element which contains the same 'key'. | |
// Returns the Node if found, else returns `null`. | |
public Node remove(T key) { | |
Node<T> removeNode = getElement(key); | |
Node<T> prevNode = removeNode.getPrev(); | |
Node<T> nextNode = removeNode.getNext(); | |
// If the next node exists, we link it to the previous node | |
if (nextNode != null) { | |
nextNode.setPrev(prevNode); | |
} | |
// If the previous node exists, we link it to the next node | |
if (prevNode != null) { | |
prevNode.setNext(nextNode); | |
} else { | |
// We're the first node so there is nothing to link | |
// We need to take the node and make it the first node in the table. | |
int lookupPosition = calculatePosition(key); | |
table[lookupPosition] = nextNode; | |
} | |
return removeNode; | |
} | |
// Gets the element with the `key` value, else returns `null`. | |
public Node getElement(T key) { | |
int lookupPosition = calculatePosition(key); | |
Node<T> retrievedNode = table[lookupPosition]; | |
while (retrievedNode != null) { | |
if (retrievedNode.getKey() == key) { | |
return retrievedNode; | |
} else { | |
retrievedNode = retrievedNode.getNext(); | |
} | |
} | |
return null; | |
} | |
// Bob Jenkin's One-at-a-Time hashing function is used if we're using strings, | |
// otherwise we Java's built in hash code | |
private int calculatePosition(T key) { | |
if (key instanceof String) { | |
int h = 0; | |
for ( int i = 0; i < ((String)key).length(); i++ ) { | |
h += ((String) key).charAt(0); | |
h += ( h << 10 ); | |
h ^= ( h << 6 ); | |
} | |
h += ( h << 3 ); | |
h ^= ( h >> 11 ); | |
h += ( h << 15 ); | |
return (h & 0xff) % (table.length - 1); | |
} else { | |
// Hash function that is based on the Java hash code of the key. | |
// We convert the hash code to an "unsigned" int as well. | |
return (key.hashCode() & 0xff) % (table.length - 1); | |
} | |
} | |
// Prints the 'table' array to the console. | |
public void spill() { | |
for (int i = 0; i < table.length; i++) { | |
if (table[i] != null) | |
System.out.println(i + "\t " + table[i]); | |
} | |
} | |
} |
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
package com.jonalmeida.HashTable; | |
public class Main { | |
public static void main(String[] args) { | |
HashTable<String> myTable = new HashTable<String>(); | |
myTable.insert("myKey", "myValue"); | |
myTable.insert("myKey", "myValue"); | |
myTable.insert("anotherKey", "anotherValue"); | |
myTable.insert("lastKey", "lastValue"); | |
myTable.insert("anotherKey", "anotherValue"); | |
myTable.insert("foo", "fooValue"); | |
myTable.insert("bar", "barValue"); | |
myTable.insert("something", "somethingValue"); | |
myTable.insert("what", "somethingValue"); | |
myTable.insert("am", "somethingValue"); | |
myTable.insert("I", "somethingValue"); | |
myTable.insert("doing", "somethingValue"); | |
myTable.insert("to", "somethingValue"); | |
myTable.insert("get", "somethingValue"); | |
myTable.insert("this", "somethingValue"); | |
myTable.insert("thing", "somethingValue"); | |
myTable.insert("to", "somethingValue"); | |
myTable.insert("work", "somethingValue"); | |
myTable.insert("while", "somethingValue"); | |
myTable.insert("my", "somethingValue"); | |
myTable.insert("eyes", "somethingValue"); | |
myTable.insert("slowly", "somethingValue"); | |
myTable.insert("close.", "somethingValue"); | |
myTable.insert("myKey", "myValue"); | |
myTable.remove("myKey"); | |
myTable.remove("bar"); | |
System.out.println("My 'while' value: " + myTable.getElement("while")); | |
myTable.spill(); | |
} | |
} |
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
package com.jonalmeida.HashTable; | |
public class Node<T> { | |
protected Node next; | |
protected Node prev; | |
protected T value; | |
protected T key; | |
public Node getPrev() { | |
return prev; | |
} | |
public void setPrev(Node prev) { | |
this.prev = prev; | |
} | |
public void setNext(Node next) { | |
this.next = next; | |
} | |
public T getKey() { | |
return key; | |
} | |
public void setKey(T key) { | |
this.key = key; | |
} | |
public T getValue() { | |
return value; | |
} | |
public void setValue(T value) { | |
this.value = value; | |
} | |
public Node(T key, T value) { | |
this.key = key; | |
this.value = value; | |
next = null; | |
prev = null; | |
} | |
public Node getNext() { | |
return next; | |
} | |
public String toString() { | |
String result = "{\"" + this.key + "\": \"" + this.value +"\"}"; | |
if (this.next != null) { | |
result += ", "; | |
result += this.next.toString(); | |
} | |
return result; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment