!DOCTYPE html> Asher's Personal Website - Hash Set

  • Home Page
  • Hash Set

    A hash set is a type of data structure that's commonly used in coding because it takes the best of both worlds - It's an array List of linked list. This keeps the efficiency high (although also the space very high). We don't care as much about how much space it takes up because a hash set is very efficient in sorting through lists of things, adding, removing, mutating, etc.

    I made my own custom hash set which performs the same functionality as the Java pre-set hashset.

    Learn more about Hash Sets (Hash Maps)
              
    // Java code for Hash Set
    
    import java.util.Objects;
    
    // Implements a singly-linked list.
    
    public class MyHashSet {
    	private ListNode[] buckets;
    	private int objectCount;
    	private double loadFactorLimit;
    
    	// Constructor: creates an empty hash set with default parameters
    	public MyHashSet()
    	{
    		this.buckets = new ListNode[10];
    		this.objectCount = 0;
    		this.loadFactorLimit = 0.75;
    	}
    
    	// Constructor: creates a hash set with the given initial bucket size and load factor limit
    	public MyHashSet(int bucketCount, double loadFactorLimit)
    	{
    		this.buckets = new ListNode[bucketCount];
    		this.objectCount = 0;
    		this.loadFactorLimit = loadFactorLimit;
    	}
    
    	// Return a pointer to the bucket array
    	public ListNode[] getBuckets() {
    		return this.buckets;
    	}
    
    	// Returns true if this set is empty; otherwise returns false.
    	public boolean isEmpty()
    	{
    		return (objectCount == 0);// isdaoiijoI am coding like this. 
    	}
    
    	// Returns the number of elements in this set.
    	public int size()
    	{
    		return objectCount;
    	}
    
    	// Return the bucket index for the object
    	public int whichBucket(Object obj) 
    	{
    		return (0x7FFFFFFF & obj.hashCode()) % this.buckets.length;
    	}
    
    	// Returns the current load factor (objCount / buckets)
    	public double currentLoadFactor() 
    	{
    		double objCount = (double) objectCount;
    		double length = (double) buckets.length;
    		return objCount / length;
    	}
    
    
    	// Return true if the object exists in the set, otherwise false.
    	// Use the .equals method to check equality.
    	public boolean contains(Object obj)
    	{
    
    		int index = whichBucket (obj);
    		for (ListNode node = buckets[index]; node != null; node = node.getNext())
    		{
    			if (obj.equals(node.getValue()))
    			{
    				return true;
    			}
    		}
    		return false;
    
    	}
    
    	// Add an object to the set.
    	// If the object already exists in the set you should *not* add another.
    	// Return true if the object was added; false if the object already exists.
    	// If an item should be added, add it to the beginning of the bucket.
    	// After adding the element, check if the load factor is greater than the limit.
    	// - If so, you must call rehash with double the current bucket size.
    	public boolean add(Object obj) 
    	{
    		if (contains (obj))
    		{
    			return false;
    		}
    		else
    		{
    			if (currentLoadFactor () >=  loadFactorLimit)
    			{
    				rehash (buckets.length * 2);
    			}
    			int index = whichBucket (obj);
    			ListNode newNode = new ListNode(obj);
    			newNode.setNext(buckets[index]);
    			buckets[index] = newNode;
    
    			objectCount++;
    			return true;
    		}
    		// Gotta do something with the rehashing and current load factor - deal with it later.
    	}
    
    	// Remove the object.  Return true if successful, false if the object did not exist
    	public boolean remove(Object obj) 
    	{
    		if (!contains (obj))
    		{
    			return false;
    		}
    		else
    		{
    			int index = whichBucket (obj);
    			if (buckets[index].getValue() == obj)
    			{
    				if (buckets[index].getNext() == null)
    				{
    					buckets[index] = null;
    				}
    				else
    				{
    					buckets[index] = buckets[index].getNext();
    				}
    			}
    			else
    			{
    				ListNode befRem = null;
    				for (ListNode node = buckets[index]; node.getNext() != null; node = node.getNext())
    				{
    					if (Objects.equals(node.getNext().getValue(), obj))
    					{
    						befRem = node;
    					}
    				}
    				if (befRem.getNext().getNext() == null)
    				{
    					befRem.setNext(null);
    				}
    				else
    				{
    					befRem.setNext(befRem.getNext().getNext());
    				}
    			}
    			objectCount--;
    			return true;
    		}
    	}
    
    	public ListNode getNode (Object obj, int index)
    	{
    		for (ListNode node = buckets[index]; node != null; node = node.getNext())
    		{
    			if (Objects.equals(node.getValue(), obj))
    			{
    				return node;
    			}
    		}
    		return null;
    	}
    	// Rehash the set so that it contains the given number of buckets
    	// Loop through all existing buckets, from 0 to length
    	// rehash each object into the new bucket array in the order they appear on the original chain.
    	public void rehash(int newBucketCount) 
    	{
    
    		ListNode[] newBucket = new ListNode[newBucketCount];
    		ListNode[] oldBuck = buckets;   // this line
    		buckets = newBucket;
    		for (int i = 0; i < oldBuck.length; i++)
    		{
    			if (oldBuck[i] != null)
    			{
    				for (ListNode node = oldBuck[i]; node != null; node = node.getNext())
    				{
    					add (node.getValue());
    				}
    			}
    		}
    	}
    	// The output should be in the following format:
    	// [ #1, #2 | { b#: v1 v2 v3 } { b#: v1 v2 } ]
    	// #1 is the objCount
    	// #2 is the number of buckets
    	// For each bucket that contains objects, create a substring that indicates the bucket index
    	// And list all of the items in the bucket (in the order they appear)
    	public String toString() 
    	{
    		StringBuilder str = new StringBuilder();
    		str.append("[ ");
    		str.append(objectCount);
    		str.append(", ");
    		str.append(buckets.length);
    		str.append(" | ");
    
    
    		for (int i = 0; i < buckets.length; i++)
    		{
    			if (buckets[i]!= null)
    			{
    				str.append("{ b");
    				str.append(i);
    				str.append(": ");
    
    				for (ListNode node = buckets[i]; node!= null; node = node.getNext())
    				{
    					str.append(node.getValue());
    					str.append(" ");
    				}
    				str.append("}");
    				str.append(" ");
    			}
    		}
    		str.append("]");
    
    		return str.toString();
    	}
    
    }
    import java.util.Objects;
    
    // Implements a singly-linked list.
    
    public class MyHashSet {
    	private ListNode[] buckets;
    	private int objectCount;
    	private double loadFactorLimit;
    
    	// Constructor: creates an empty hash set with default parameters
    	public MyHashSet()
    	{
    		this.buckets = new ListNode[10];
    		this.objectCount = 0;
    		this.loadFactorLimit = 0.75;
    	}
    
    	// Constructor: creates a hash set with the given initial bucket size and load factor limit
    	public MyHashSet(int bucketCount, double loadFactorLimit)
    	{
    		this.buckets = new ListNode[bucketCount];
    		this.objectCount = 0;
    		this.loadFactorLimit = loadFactorLimit;
    	}
    
    	// Return a pointer to the bucket array
    	public ListNode[] getBuckets() {
    		return this.buckets;
    	}
    
    	// Returns true if this set is empty; otherwise returns false.
    	public boolean isEmpty()
    	{
    		return (objectCount == 0);// isdaoiijoI am coding like this. 
    	}
    
    	// Returns the number of elements in this set.
    	public int size()
    	{
    		return objectCount;
    	}
    
    	// Return the bucket index for the object
    	public int whichBucket(Object obj) 
    	{
    		return (0x7FFFFFFF & obj.hashCode()) % this.buckets.length;
    	}
    
    	// Returns the current load factor (objCount / buckets)
    	public double currentLoadFactor() 
    	{
    		double objCount = (double) objectCount;
    		double length = (double) buckets.length;
    		return objCount / length;
    	}
    
    
    	// Return true if the object exists in the set, otherwise false.
    	// Use the .equals method to check equality.
    	public boolean contains(Object obj)
    	{
    
    		int index = whichBucket (obj);
    		for (ListNode node = buckets[index]; node != null; node = node.getNext())
    		{
    			if (obj.equals(node.getValue()))
    			{
    				return true;
    			}
    		}
    		return false;
    
    	}
    
    	// Add an object to the set.
    	// If the object already exists in the set you should *not* add another.
    	// Return true if the object was added; false if the object already exists.
    	// If an item should be added, add it to the beginning of the bucket.
    	// After adding the element, check if the load factor is greater than the limit.
    	// - If so, you must call rehash with double the current bucket size.
    	public boolean add(Object obj) 
    	{
    		if (contains (obj))
    		{
    			return false;
    		}
    		else
    		{
    			if (currentLoadFactor () >=  loadFactorLimit)
    			{
    				rehash (buckets.length * 2);
    			}
    			int index = whichBucket (obj);
    			ListNode newNode = new ListNode(obj);
    			newNode.setNext(buckets[index]);
    			buckets[index] = newNode;
    
    			objectCount++;
    			return true;
    		}
    		// Gotta do something with the rehashing and current load factor - deal with it later.
    	}
    
    	// Remove the object.  Return true if successful, false if the object did not exist
    	public boolean remove(Object obj) 
    	{
    		if (!contains (obj))
    		{
    			return false;
    		}
    		else
    		{
    			int index = whichBucket (obj);
    			if (buckets[index].getValue() == obj)
    			{
    				if (buckets[index].getNext() == null)
    				{
    					buckets[index] = null;
    				}
    				else
    				{
    					buckets[index] = buckets[index].getNext();
    				}
    			}
    			else
    			{
    				ListNode befRem = null;
    				for (ListNode node = buckets[index]; node.getNext() != null; node = node.getNext())
    				{
    					if (Objects.equals(node.getNext().getValue(), obj))
    					{
    						befRem = node;
    					}
    				}
    				if (befRem.getNext().getNext() == null)
    				{
    					befRem.setNext(null);
    				}
    				else
    				{
    					befRem.setNext(befRem.getNext().getNext());
    				}
    			}
    			objectCount--;
    			return true;
    		}
    	}
    
    	public ListNode getNode (Object obj, int index)
    	{
    		for (ListNode node = buckets[index]; node != null; node = node.getNext())
    		{
    			if (Objects.equals(node.getValue(), obj))
    			{
    				return node;
    			}
    		}
    		return null;
    	}
    	// Rehash the set so that it contains the given number of buckets
    	// Loop through all existing buckets, from 0 to length
    	// rehash each object into the new bucket array in the order they appear on the original chain.
    	public void rehash(int newBucketCount) 
    	{
    
    		ListNode[] newBucket = new ListNode[newBucketCount];
    		ListNode[] oldBuck = buckets;   // this line
    		buckets = newBucket;
    		for (int i = 0; i < oldBuck.length; i++)
    		{
    			if (oldBuck[i] != null)
    			{
    				for (ListNode node = oldBuck[i]; node != null; node = node.getNext())
    				{
    					add (node.getValue());
    				}
    			}
    		}
    	}
    	// The output should be in the following format:
    	// [ #1, #2 | { b#: v1 v2 v3 } { b#: v1 v2 } ]
    	// #1 is the objCount
    	// #2 is the number of buckets
    	// For each bucket that contains objects, create a substring that indicates the bucket index
    	// And list all of the items in the bucket (in the order they appear)
    	public String toString() 
    	{
    		StringBuilder str = new StringBuilder();
    		str.append("[ ");
    		str.append(objectCount);
    		str.append(", ");
    		str.append(buckets.length);
    		str.append(" | ");
    
    
    		for (int i = 0; i < buckets.length; i++)
    		{
    			if (buckets[i]!= null)
    			{
    				str.append("{ b");
    				str.append(i);
    				str.append(": ");
    
    				for (ListNode node = buckets[i]; node!= null; node = node.getNext())
    				{
    					str.append(node.getValue());
    					str.append(" ");
    				}
    				str.append("}");
    				str.append(" ");
    			}
    		}
    		str.append("]");
    
    		return str.toString();
    	}