Hashtables
Hash Tables are an abstract data type, they use key/value pairs to store data, the key can be integer, string, object, etc and the key/value pair don't have to be the same. You get optimal retrieval when you know the key. You can use the load factor to resize an hashtable, you don't wont to low as there will be lots of empty space and you don't won't it to be too high as there will be to many collisions.
| Employee Class (used by many examples below) | package uk.co.datadisk.linkedlist;
import java.util.Objects;
public class Employee {
private String firstName;
private String lastName;
private int id;
public Employee(String firstName, String lastName, int id) {
this.firstName = firstName;
this.lastName = lastName;
this.id = id;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Employee{" +
"firstName='" + firstName + '\'' +
", lastName='" + lastName + '\'' +
", id=" + id +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return id == employee.id &&
Objects.equals(firstName, employee.firstName) &&
Objects.equals(lastName, employee.lastName);
}
@Override
public int hashCode() {
return Objects.hash(firstName, lastName, id);
}
} |
| Hashtable Example | |
| Simple Hashtable (no collision handling, not to be used but only to show example) | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
public class SimpleHashtable {
private Employee[] hashTable;
public SimpleHashtable() {
hashTable = new Employee[10];
}
private int hashKey(String key){
return key.length() % hashTable.length;
}
public void put(String key, Employee employee){
int hashedKey = hashKey(key);
if (hashTable[hashedKey] != null){
System.out.println("Sorry there is already and employee at position " + hashedKey);
} else {
hashTable[hashedKey] = employee;
}
}
public Employee get(String key){
int hashedKey = hashKey(key);
System.out.println("Hashed Key: " + hashedKey);
return hashTable[hashedKey];
}
public void printHashtable() {
for (int i = 0; i < hashTable.length; i++) {
System.out.println(i + ": " + hashTable[i]);
}
}
} |
| Main Hashtable example | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
public class Main_Simple_Hashtable {
public static void main(String[] args) {
// This solution will produce collisions
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
Employee will = new Employee("Will", "Hay", 1004);
Employee x = new Employee("x", "Hay", 1005);
SimpleHashtable ht = new SimpleHashtable();
ht.put("valle1", paul);
ht.put("valle12", lorraine);
ht.put("valle123", dominic);
ht.put("valle234", jessica);
ht.put("x", x);
ht.put("", x);
ht.printHashtable();
ht.put("hay", will);
ht.printHashtable();
System.out.println(ht.get("hay"));
System.out.println(ht.get("x"));
}
} |
To handle collisions we can use linear probing, basically if a slot is already take we find an empty slot and use that one, we do this by increasing the index value by one and then see if that slot is taken, we continue doing this until we find an empty slot, thus has an impact on the performance of the hashtable the more collisions the more work in find slots for data. Another solution is to use chaining in each slot we have a linked list and thus if we have a collision its added to the linked list of that slot which means each slot can handle many values.
| Linear Probing Example | |
| Simple Linear Probing | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
public class SimpleHashtableLinearProbing {
private StoredEmployee[] hashTable;
public SimpleHashtableLinearProbing() {
hashTable = new StoredEmployee[10];
}
private int hashKey(String key){
return key.length() % hashTable.length;
}
private boolean occupied(int index){
return hashTable[index] != null;
}
public void put(String key, Employee employee){
int hashedKey = hashKey(key);
// Linear Probing
if(occupied(hashedKey)){
int stopIndex = hashedKey;
if(hashedKey == hashTable.length - 1){
hashedKey = 0;
} else {
hashedKey++;
}
while(occupied(hashedKey) && hashedKey != stopIndex){
hashedKey = (hashedKey + 1) % hashTable.length;
}
}
if (occupied(hashedKey)){
System.out.println("Sorry there is already and employee at position " + hashedKey);
} else {
hashTable[hashedKey] = new StoredEmployee(key, employee);
}
}
private int findKey(String key) {
int hashedKey = hashKey(key);
if (hashTable[hashedKey] != null && hashTable[hashedKey].key.equals(key)) {
return hashedKey;
}
int stopIndex = hashedKey;
if (hashedKey == hashTable.length - 1) {
hashedKey = 0;
} else {
hashedKey++;
}
while (hashedKey != stopIndex && hashTable[hashedKey] != null && !hashTable[hashedKey].key.equals(key)) {
hashedKey = (hashedKey + 1) % hashTable.length;
}
if (hashTable[hashedKey] != null && hashTable[hashedKey].key.equals(key)){
return hashedKey;
} else {
return -1;
}
}
public Employee get(String key){
int hashedKey = findKey(key);
if(hashedKey == -1){
return null;
}
return hashTable[hashedKey].employee;
}
public Employee remove(String key){
int hashedKey = findKey(key);
if(hashedKey == -1) {
return null;
}
Employee employee = hashTable[hashedKey].employee;
hashTable[hashedKey] = null;
StoredEmployee[] oldHashTable = hashTable;
hashTable = new StoredEmployee[oldHashTable.length];
for (int i = 0; i < oldHashTable.length; i++) {
if(oldHashTable[i] != null){
put(oldHashTable[i].key, oldHashTable[i].employee);
}
}
return employee;
}
public void printHashtable() {
for (int i = 0; i < hashTable.length; i++) {
if(hashTable[i] == null){
System.out.println("Empty");
} else {
System.out.println("Position " + i + ": " + hashTable[i].employee);
}
}
}
} |
| Main Simple Linear Probing | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
public class Main_Simple_Hashtable_Linear_Probing {
public static void main(String[] args) {
// This solution will produce collisions
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
Employee will = new Employee("Will", "Hay", 1004);
Employee x = new Employee("x", "Hay", 1005);
SimpleHashtableLinearProbing ht = new SimpleHashtableLinearProbing();
ht.put("valle1", paul);
ht.put("valle12", lorraine);
ht.put("valle123", dominic);
ht.put("valle234", jessica);
ht.printHashtable();
ht.put("hay", will);
ht.printHashtable();
System.out.println(ht.get("valle234"));
ht.remove("valle12");
ht.remove("valle123");
ht.printHashtable();
System.out.println("Find jessica: " + ht.get("valle234"));
}
} |
| Chaining Example | |
| Chaining | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
import java.util.LinkedList;
import java.util.ListIterator;
public class ChainedHashtable {
private LinkedList<StoredEmployee>[] hashtable;
public ChainedHashtable() {
hashtable = new LinkedList[50];
for (int i = 0; i < hashtable.length; i++) {
hashtable[i] = new LinkedList<>();
}
}
private int hashKey(String key) {
// You can use different hashing algorithms to try and avoid collisions
//return key.length() % hashtable.length;
return Math.abs(key.hashCode() % hashtable.length);
//return Math.abs((key.hashCode() + key.hashCode()) % hashtable.length);
}
public void put(String key, Employee employee){
int hashedKey = hashKey(key);
hashtable[hashedKey].add(new StoredEmployee(key, employee));
}
public Employee get(String key){
int hashedKey = hashKey(key);
ListIterator<StoredEmployee> iterator = hashtable[hashedKey].listIterator();
StoredEmployee employee;
while(iterator.hasNext()){
employee = iterator.next();
if(employee.key.equals(key)){
return employee.employee;
}
}
return null;
}
public Employee remove(String key){
int hashedKey = hashKey(key);
ListIterator<StoredEmployee> iterator = hashtable[hashedKey].listIterator();
StoredEmployee employee = null;
int index = -1;
while(iterator.hasNext()){
employee = iterator.next();
index++;
if(employee.key.equals(key)){
break;
}
}
if(employee == null){
return null;
} else {
hashtable[hashedKey].remove(index);
return employee.employee;
}
}
public void printHashtable() {
for (int i = 0; i < hashtable.length; i++) {
if(hashtable[i].isEmpty()){
System.out.println("Position " + i + ": empty");
} else {
System.out.print("Position " + i + ": ");
ListIterator<StoredEmployee> iterator = hashtable[i].listIterator();
while(iterator.hasNext()){
System.out.print(iterator.next().employee);
System.out.print(" -> ");
}
System.out.println("null");
}
}
}
} |
| Main Chaining | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
public class Main_Chained_Hashtable {
public static void main(String[] args) {
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
Employee will = new Employee("Will", "Hay", 1004);
ChainedHashtable cht = new ChainedHashtable();
cht.put("Paul", paul);
cht.put("Lorraine", lorraine);
cht.put("Dominic", dominic);
cht.put("Jessica", jessica);
cht.put("Will", will);
cht.printHashtable();
System.out.println("Find Will " + cht.get("Will"));
System.out.println("Find Jessica " + cht.get("Jessica"));
cht.remove("Will");
cht.printHashtable();
}
} |
Although I have shown demonstrations of how has tables work above you really should use the JDK versions, collision handling are all builtin. I have already covered maps in my Java Reference section. There are many classes that implement the map interface, some offer synchronization as well.
The example below is demostrating using hashmap
| JDK Hashtable | package uk.co.datadisk.hashtable;
import uk.co.datadisk.linkedlist.Employee;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Main_hashtable_JDK {
public static void main(String[] args) {
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
Employee will = new Employee("Will", "Hay", 1004);
Map<String, Employee> hashMap = new HashMap<>();
hashMap.put("Paul", paul);
hashMap.put("Lorraine", lorraine);
hashMap.put("Dominic", dominic);
hashMap.put("Jessica", jessica);
System.out.println(hashMap.containsKey("Paul"));
System.out.println(hashMap.containsValue(paul));
// Iterator<Employee> iterator = hashMap.values().iterator();
// while(iterator.hasNext()){
// System.out.println(iterator.next());
// }
// same as above code but using a lambda
hashMap.forEach((k, v) -> System.out.println("Key = " + k + ", Employee = " + v));
// over write Paul key will will Employee
hashMap.put("Paul", will);
hashMap.forEach((k, v) -> System.out.println("Key = " + k + ", Employee = " + v));
// only overwrite if key is absent
hashMap.putIfAbsent("Lorraine", will); // the existing value will be returned
hashMap.forEach((k, v) -> System.out.println("Key = " + k + ", Employee = " + v));
System.out.println("Dominic " + hashMap.get("Dominic"));
System.out.println("Get no one " + hashMap.get("Darth"));
System.out.println("Return a default if key not found " + hashMap.getOrDefault("Darth", jessica));
System.out.println("Remove Paul " + hashMap.remove("Paul"));
hashMap.forEach((k, v) -> System.out.println("Key = " + k + ", Employee = " + v));
}
} |