Home



2020/04 - DS&A #12: Hash Tables

Hey folks!

For this post we'll be diving into the Hash Table. The hash table is essentially an array where the index can be anything, doesn't have to be sequential, and is unique. Hash tables use a technique called "hashing" in order to derive values that will be used as an index, or "key". A hashing algorithm should be good enough to accomodate duplicates and deal with collisions. Our approach in this post will involve an array of objects called HashTableArray. Don't be fooled by the name however, as the HashTableArray class uses a LinkedList to keep tracks of the nodes it stores. We'll be going over the structure of what a hash table looks like, but we won't be delving into the minutia or covering the different hashing techniques in much depth at all. This post is simply meant to give you an overview of this particular data structure.

 

public class HashTableArrayNode{
    
    private String value;

    public HashTableArrayNode(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }
    
    //Don't actually create your own hashing algorithm if you can avoid it!
    public int hash(int boundary) {
        int valueHash = 0;
        for(char c : value.toCharArray()) {
            valueHash += c;
        }
        return (boundary - 1) % valueHash;
        
    }
    

}

The only feature of note for the hash table node is the hashing algorithm found in the hash method. It's a pretty basic and slighty altered version of the naieve hashing technique, where we're just deriving a value from each character, but also providing a boundary from the HashTable classes size field for greater spread potential values. Simple enough stuff.

 

public class HashTableArray {
    
    LinkedList<HashTableArrayNode> nodeList;
    
    public HashTableArray() {
        nodeList = new LinkedList<HashTableArrayNode>();
    }
    
    public void add(HashTableArrayNode node) throws Exception {
        if(findData(node)) {
            throw new Exception("Conflict when adding node!");    
        }
        else {
            nodeList.addFirst(node);
        }
        
    }

    public boolean findData(HashTableArrayNode node) {
        
        HashTableArrayNode foundNode = null;
        Iterator iterator = nodeList.iterator();
        while(iterator.hasNext()) {
          HashTableArrayNode iterNode= (HashTableArrayNode)iterator.next();
          if( iterNode.getValue().equals(node.getValue())) {
              foundNode = iterNode;
          }
        }
        
        return foundNode != null ? true : false ;
    }
    
    public boolean collisionsDetected(HashTableArrayNode node) throws Exception{
        
        HashTableArrayNode foundNode = null;
        Iterator iterator = nodeList.iterator();
        while(iterator.hasNext()) {
          HashTableArrayNode iterNode= (HashTableArrayNode)iterator.next();
          if( iterNode.getValue().equals(node.getValue()) && iterNode.hash(HashTable.size) == node.hash(HashTable.size)) {
              throw new Exception();
          }
        }
        
        return false ;
    }
    
    
    public boolean removeData(HashTableArrayNode node) {
        HashTableArrayNode foundNode = null;
        HashTableArrayNode next = nodeList.getFirst();
        while(next != null) {
          if(next.getValue().equals(node.getValue())) {
              foundNode = next;
          }
        }
        if(foundNode != null) {
          nodeList.remove(foundNode);
          return true;
        }
        return false;
        
    }
    
    public HashTableArrayNode[] listOfAllNodes() {
        return Arrays.copyOf(nodeList.toArray(), nodeList.size() , HashTableArrayNode[].class);
    }

}
 

The hash table array, the most important feature of which is the code that detects whether a node already exists in the array or not. In our case, if we find that a value already exists in a hash table array, we're going to throw an exception. We can also remove nodes, and return boolean values based on how successful a remove was, and get a list of the classes nodes.

 

public class HashTable {
    
    HashTableArray[] listOfNodes;
    double fillFactor = .75;
    int count = 0;
    int size = 2;
        
    public HashTable() {
        listOfNodes = new HashTableArray[size];
    }
    
    public void addData(HashTableArrayNode node) {
        if( count != 0 && ((count / size) > fillFactor) ) {
            HashTableArray[] oldListOfNodes = listOfNodes;
            size *= 2;
            listOfNodes = new HashTableArray[size];
            fillArray();
            for(int i = 0; i < oldListOfNodes.length ; i++) {
                HashTableArrayNode[] tablesNodes = oldListOfNodes[i].listOfAllNodes();
                for(int p = 0; p < tablesNodes.length; p++) {
                    this.addData(tablesNodes[p]);
                }    
            }
        }
        listOfNodes[node.hash(size)].add(node);
        count++;
    }

    public boolean findData(HashTableArrayNode node) {
        
        return listOfNodes[node.hash(size)].findData(node);
    }
    
    public boolean removeData(HashTableArrayNode node) {
        
        return listOfNodes[node.hash(size)].removeData(node);
    }
    
    public static void main(String[] arguments) {
      HashTable newTable = new HashTable();
      newTable.fillArray();
      HashTableArrayNode node1 = new HashTableArrayNode("Abe");
      HashTableArrayNode node2 = new HashTableArrayNode("Aslik");
      HashTableArrayNode node3 = new HashTableArrayNode("Shryskull");
      HashTableArrayNode node4 = new HashTableArrayNode("Shrink");
      
      newTable.addData(node1);
      System.out.println(newTable.findData(node1));
      System.out.println(newTable.findData(node2));
      newTable.addData(node2);
      System.out.println(newTable.findData(node2));
      newTable.addData(new HashTableArrayNode("Dripik"));
      newTable.addData(new HashTableArrayNode("Molluck"));
      newTable.addData(new HashTableArrayNode("Alf"));
      newTable.addData(new HashTableArrayNode("Munch"));
      
      System.out.println(newTable.findData(node1));
      System.out.println(newTable.findData(node3));
      newTable.addData(node3);
      System.out.println(newTable.findData(node3));
      
      newTable.addData(new HashTableArrayNode("Big face"));
      newTable.addData(new HashTableArrayNode("Brewmaster"));
      newTable.addData(new HashTableArrayNode("Phleg"));
      newTable.addData(new HashTableArrayNode("Almighty Raisin"));
      newTable.addData(new HashTableArrayNode("Lulu"));
      newTable.addData(new HashTableArrayNode("Humphrey"));
      newTable.addData(new HashTableArrayNode("Crig the Slig"));
      newTable.addData(new HashTableArrayNode("Skillya"));
      newTable.addData(new HashTableArrayNode("Lady Margaret"));
      newTable.addData(new HashTableArrayNode("The Stranger"));
      newTable.addData(new HashTableArrayNode("Fangus Klot"));
      
      System.out.println(newTable.findData(node1));
      System.out.println(newTable.findData(node4));
      newTable.addData(node4);
      System.out.println(newTable.findData(node4));
      
      System.out.println("***");
    }
    
    public void fillArray() {
      for(int i = 0; i <listOfNodes.length; i++)
          listOfNodes[i] = new HashTableArray();
    }
}

The hash table class itself has several different methods that often defer to the hash table array class in some capacity. We have a fill factor value as well, which is used to determine when to increase the size of our arrays with regards to how full it is. We don't decrease this value as this is only an overview, but feel free to do that in your own attempts. This value is used when adding nodes, and if the array reaches a certain percentage of it's maximum capacity, it doubles the size of the array, copying all of the original values over.

That's pretty much it for the hash table, but there's a lot more you can learn about this data structure online. You can make them as complex or as simple (Such as seen above) as you like, but it's good to have a grasp on how they work since hash tables are used quite frequently in the real world.

Good luck!

Marc