I believe reinventing the wheel is in fact a good learning exercise. How can I improve my Set implementation without just copying HashSet?
- No treeification/detreefication, please. I find it too time-consuming to implement.
- I decided not to use anything but arrays and
Lists as its underlying data structures. - Some aspects of design that you may find unusual may in fact serve some purpose (or at least, I believe so). Feel free to ask if something smells fishy to you.
package org.example.demos.mySet;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.*;
public class MyHashSet<E> extends AbstractSet<E> {
private final Defaults defaults = new Defaults();
private List<E>[] hashTable;
private List<InternalAddress> addresses = defaults.addresses();
private final float LOAD_FACTOR;
@SuppressWarnings("unused")
public MyHashSet() {
LOAD_FACTOR = Defaults.LOAD_FACTOR;
initializeAndPrepareHashTable();
}
@SuppressWarnings("unused")
public MyHashSet(int initialCapacity) {
if (initialCapacity < 3) {
throw new IllegalArgumentException("Initial capacity should be equal to or greater than 3. Your value: " + initialCapacity);
}
LOAD_FACTOR = Defaults.LOAD_FACTOR;
initializeAndPrepareHashTable(initialCapacity);
}
@SuppressWarnings("unused")
public MyHashSet(int initialCapacity, float loadFactor) {
if (initialCapacity * loadFactor < 2) {
throw new IllegalArgumentException("Initial capacity and load factor should be set in such a way " +
"as to allow at least one element before resizing. In other words, initialCapacity * loadFactor " +
"should be equal to or greater than 2. Your values: " + initialCapacity + ", " + loadFactor);
} else if (loadFactor > 1) {
throw new IllegalArgumentException("Load factor should not exceed 1. Your value: " + loadFactor);
}
LOAD_FACTOR = loadFactor;
initializeAndPrepareHashTable(initialCapacity);
}
private void initializeAndPrepareHashTable() {
hashTable = defaults.hashTable();
fillHashTableWithEmptyLists();
}
private void initializeAndPrepareHashTable(int initialCapacity) {
hashTable = defaults.hashTable(initialCapacity);
fillHashTableWithEmptyLists();
}
private void fillHashTableWithEmptyLists() {
fillHashTableWithEmptyLists(hashTable);
}
@SuppressWarnings("unchecked")
private void fillHashTableWithEmptyLists(List<E>[] hashTable) {
try {
Constructor<? extends List<E>> constructor = (Constructor<? extends List<E>>) hashTable.getClass()
.componentType()
.getDeclaredConstructor();
for (int i = 0; i < hashTable.length; i++) {
hashTable[i] = constructor.newInstance();
}
} catch (InstantiationException | IllegalAccessException |
InvocationTargetException | NoSuchMethodException exception) {
exception.printStackTrace();
}
}
@Override
public boolean add(E elementToAdd) {
int bucketIndex = getBucketIndex(elementToAdd);
List<E> bucket = hashTable[bucketIndex];
for (E element : bucket) {
if (element == elementToAdd || element.equals(elementToAdd)) {
return false;
}
}
bucket.add(elementToAdd);
InternalAddress newElementAddress = new InternalAddress(bucketIndex, bucket.size() - 1);
addresses.add(newElementAddress);
Collections.sort(addresses);
checkFullness();
return true;
}
@Override
public boolean remove(Object object) {
int bucketIndex = getBucketIndex(object);
List<E> bucket = hashTable[bucketIndex];
for (ListIterator<E> iterator = bucket.listIterator(); iterator.hasNext(); ) {
E element = iterator.next();
if (object.equals(element)) {
iterator.remove();
InternalAddress removedElementAddress = new InternalAddress(bucketIndex,
iterator.previousIndex() + 1);
addresses.remove(removedElementAddress);
return true;
}
}
return false;
}
@Override
public boolean contains(Object o) {
List<E> bucket = hashTable[getBucketIndex(o)];
for (E element : bucket) {
if (o.equals(element)) {
return true;
}
}
return false;
}
@Override
public Iterator<E> iterator() {
return new MyHashSetIterator();
}
@Override
public int size() {
return addresses.size();
}
private int getBucketIndex(Object object) {
return object == null ? 0 : (hashTable.length - 1) & object.hashCode();
}
private int getBucketIndex(Object object, int hashTableLength) {
return object == null ? 0 : (hashTableLength - 1) & object.hashCode();
}
private void checkFullness() {
if (size() >= hashTable.length * LOAD_FACTOR) {
resizeAndRehash();
}
}
private void resizeAndRehash() {
int newLength = defaults.newLength();
List<E>[] newHashTable = defaults.hashTable(newLength);
fillHashTableWithEmptyLists(newHashTable);
List<InternalAddress> newAddresses = defaults.addresses();
int processedBucketIndex = -1, currentBucketIndex;
for (InternalAddress address : addresses) {
currentBucketIndex = address.bucket;
if (currentBucketIndex == processedBucketIndex) {
continue;
}
for (E element : hashTable[currentBucketIndex]) {
int newBucketIndex = getBucketIndex(element, newLength);
List<E> newBucket = newHashTable[newBucketIndex];
newBucket.add(element);
newAddresses.add(new InternalAddress(newBucketIndex, newBucket.size() - 1));
}
processedBucketIndex = currentBucketIndex;
}
hashTable = newHashTable;
addresses = newAddresses;
}
List<E>[] getHashTable() {
return hashTable;
}
List<InternalAddress> getAddresses() {
return addresses;
}
private class MyHashSetIterator implements Iterator<E> {
private int cursor = -1;
@Override
public boolean hasNext() {
return cursor < addresses.size() - 1;
}
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
InternalAddress nextElementAddress = addresses.get(++cursor);
return hashTable[nextElementAddress.bucket]
.get(nextElementAddress.index);
}
@Override
public void remove() {
if (cursor < 0) {
throw new IllegalStateException("To remove an element, this Iterator should first return it");
}
InternalAddress currentElementAddress = addresses.get(cursor);
hashTable[currentElementAddress.bucket].remove(currentElementAddress.index);
}
}
private record InternalAddress(int bucket, int index) implements Comparable<InternalAddress> {
@Override
public int compareTo(InternalAddress otherAddress) {
boolean differentBuckets = bucket != otherAddress.bucket;
if (differentBuckets) {
return bucket - otherAddress.bucket;
} else {
return index - otherAddress.index;
}
}
}
private class Defaults {
private static final int INITIAL_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
@SuppressWarnings("unchecked")
private List<E>[] hashTable() {
return (LinkedList<E>[]) new LinkedList[INITIAL_CAPACITY];
}
@SuppressWarnings("unchecked")
private List<E>[] hashTable(int initialCapacity) {
return (LinkedList<E>[]) new LinkedList[initialCapacity];
}
private List<InternalAddress> addresses() {
return new LinkedList<>();
}
private int newLength() {
return hashTable.length << 1;
}
}
}
@SuppressWarningsannotations which are not a functional part of code anyway), I just added a runnable snippet (a test suite) \$\endgroup\$