Skip to content

Instantly share code, notes, and snippets.

@jonalmeida
Last active August 29, 2015 14:12
Show Gist options
  • Save jonalmeida/b561c594f58091a8d387 to your computer and use it in GitHub Desktop.
Save jonalmeida/b561c594f58091a8d387 to your computer and use it in GitHub Desktop.
Simple hash table in Java with add(), remove() and getElement()
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]);
}
}
}
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();
}
}
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