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.
// 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();
}