4
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Instead of throwing extremely verbose exceptions, I would prefer having the limits for load factor and initial capacity to be documented in the Javadoc and only the violation being described in the exception message. For example: "Invalid load factor [provided value]" \$\endgroup\$ Jul 4 at 7:24
  • 2
    \$\begingroup\$ Incorporating advice from an answer into the question violates the question-and-answer nature of this site. You could post improved code as a new question, as an answer, or as a link to an external site - as described in I improved my code based on the reviews. What next?. I have rolled back the edit, so the answers make sense again. \$\endgroup\$ Jul 4 at 14:54
  • \$\begingroup\$ @TobySpeight I didn't improve the code (except for @SuppressWarnings annotations which are not a functional part of code anyway), I just added a runnable snippet (a test suite) \$\endgroup\$
    – Sergey
    Jul 4 at 14:59
  • 1
    \$\begingroup\$ And that invalidates the review which highlights "the lack of functional and performance tests". Best practice is not to touch the code at all once a question is answered. \$\endgroup\$ Jul 4 at 15:03
  • \$\begingroup\$ "I believe reinventing the wheel is in fact a good learning exercise." My opinion is that "Do not reinvent the wheel" is mostly used as an excuse to shame, ridicule and dismiss people anyway. Sometimes you must reinvent the wheel, because all you need is a small rubber tire with a certain profile, and not a platinum coated, gold edged racecar wheel with three layers of carbon optimized for concrete streets with 27 optional extensions. \$\endgroup\$
    – Bobby
    Jul 5 at 20:42

1 Answer 1

6
\$\begingroup\$

Adding entries causes the allocation to grow, but removing entries will never cause it to shrink.


The supporting documentation on this submission is inadequate. Its three bullet points are

  • a design constraint supported by a rationale: "no trees!", fair enough
  • an explanation of design choices: arrays + lists, good
  • "ask me" if something is unclear -- not helpful

No references are cited. It appears to conform to this Set contract, and is explicitly not a HashSet.

As a user of this implementation, here are the crucial guarantees I'm looking for:

This [HashSet] class offers constant time [O(1)] performance for the basic operations (add, remove, contains and size), ...

I mean, if O(N) performance was Good Enough, I would just be using an array or list implementation, right? Constant time is much of the whole value add for this class, yet it offers no such guarantees. Going forward, I shall cavalierly assume them, and express disappointment if they are not met.

I will view fail-fast iterators as an advanced topic that is out-of-scope.

Even a single sentence offering the high level overview of "a power-of-two sized array holds the heads of LinkedLists" would have been helpful. Maybe followed by a sentence describing how growth or shrinkage leads to re-hashing with some prescribed amortized cost.

Reproducibility is important. I see no maven instructions for compilation, and no advice on what compiler switches or versions to use. As it stands I cannot run what the Author ran nor see what he saw. Absent a repo link, I don't know which compiler version we're targeting or the intended set of switches.

The whole generics type-erasure "unchecked" situation seems out of control w.r.t. the interface we're trying to conform to. For example this implementation manages to implement the interface in a type safe way, apart from clone() and readObject(). There exist techniques for type safe access, which are observed to work well in the wild. We need some design discussion, and commentary on support for switches like -Xlint:all or -Xlint:unchecked.

I do not understand the default constructor's "unused" annotation, and would appreciate a /* comment */ explaining it, or a JUnit test suite that exercises constructors. Maybe it was added early on, and then the code evolved but it was never removed?


        if (initialCapacity < 3) {

I do not understand at all why we're rejecting a capacity of 2. The thrown diagnostic appears to conflict with the one thrown by the 2-arg ctor. Better to just call it here, with 2nd arg equal to default loadFactor, and let it throw if necessary. It appears to me things would work fine with just two buckets.


    private void initializeAndPrepareHashTable() {
        hashTable = defaults.hashTable();
        fillHashTableWithEmptyLists();
    }

    private void initializeAndPrepareHashTable(int initialCapacity) {
        hashTable = defaults.hashTable(initialCapacity);
        fillHashTableWithEmptyLists();
    }

These don't make much sense.

They are private. There should be just one of them (the 2nd one).

The default ctor should supply a default initialCapacity to the 2nd one.


    private void fillHashTableWithEmptyLists() {
        fillHashTableWithEmptyLists(hashTable);
    }

Why?

This private helper method is not pulling its weight. Surely the caller could have supplied this.hashTable? It's not like there's some Public API we need to conform to.

    private void fillHashTableWithEmptyLists(List<E>[] hashTable) {
            ...
            for (int i = 0; i < hashTable.length; i++) {
                hashTable[i] = constructor.newInstance();
            }
`hashTable` is a `List`, so this all checks out. But the trouble is that it's implemented as a `LinkedList`, so the complexity here is O(N^2) quadratic. Better to maintain a pointer that you can push a new entry onto in O(1) constant time. Whoops. On initial reading I mistook `[i]` as a subscript into a LinkedList rather than array. This isn't python; I should have anticipated a `.get(i)`. I retract the remark.
        } catch (InstantiationException | IllegalAccessException |
                 InvocationTargetException | NoSuchMethodException exception) {
            exception.printStackTrace();

Arrggghhhh! zomg, no, do not swallow such exceptions. Rather, re-throw them, in the hope it will be fatal.

If need be, to make the signature work out, wrap it within RuntimeException or an app-specific class which inherits from that.


            if (element == elementToAdd || element.equals(elementToAdd)) {

What is going on here? I mean, yes, I get it that address equality is different from examining each attribute. But why aren't we delegating such details to the element type? A type can start its comparison by examining addresses. There needs to be some discussion in the code or docs about such micro optimizations, with a citation describing observed timings.

        Collections.sort(addresses);

Ok, now I'm astonished. add() just did an O(N log N) operation, when caller will reasonably expect it to return in O(1) constant time?!?

Possibly the data structure you were looking for is a heap, with O(log N) insert time. In a java context folks tend to view that as O(64), which is O(1) constant.


    public boolean remove(Object object) {
                ...
                addresses.remove(removedElementAddress);

Oh, lookitdat, O(1) removal time from a linked list, excellent.

Near as I can tell, this seems to be the author's motivation for employing a linked list.

There is a technique called tombstones which lets you delete an item in O(1) constant time, by simply setting a "deleted" flag on the item. As tombstones accumulate they become troublesome, so at some point you'll want to copy out just the live items, which still may have an attractive amortized cost.

A pointer dereference is hard for Intel to predict / prefetch, so contiguous ArrayList entries with tombstone may bench faster than a chain of LinkedList entries.


    public boolean contains(Object o) {
            ...
            if (o.equals(element)) {

Couple of items:

  • It troubles me that we're not doing the same address comparison as above. For example, what if the element type had a buggy .equals()? Then address comparison would mask that.
  • This "loop and compare" should be what other methods call, or it should be in a helper that contains() and other methods call. DRY

    private int getBucketIndex(Object object) {
        return object == null ? 0 : (hashTable.length - 1) & object.hashCode();
    }

This method imposes a class invariant on MySet, so we're forced to allocate only power-of-two capacities. This seems needlessly limiting.

We're comparing the elapsed time for int-divide against bitwise AND. On modern processors, it's not clear this is going to add up to significant time, compared to waiting on our cache misses and linked list prediction misses. In microbenches we can do about two & AND operations in the time it takes to do one % mod operation. But masking forces us to at least double the number of buckets when resizing, as opposed to say 30% or 50% growth. Doesn't seem like the tradeoff is worth it. Example: ... % 8 is like ... & 7, but % 9 has no easy masking equivalent.

Recommend you adopt the traditional % modulo approach, here.


Like many other methods, the resizeAndRehash() method has a lovely name, very clear and descriptive. I'm not going to read further; I bet it does the right thing.


The submission offered no unit tests or benchmark timings, and essentially no supporting documentation, for some core functionality that potentially is of interest to many diverse callers. If there were other considerations, like "speed is not an issue", they were not explicitly called out.

This codebase does not appear to achieve its design goals.

"Merge to main?" Given the lack of functional and performance tests, I would not be willing to delegate or accept maintenance tasks on this code in its current form.

\$\endgroup\$
10
  • \$\begingroup\$ The OP removed the first line of code, I don't see that it invalidates the answer in any way, but if it does let me know. Or roll back the edit. \$\endgroup\$
    – pacmaninbw
    Jul 4 at 12:30
  • \$\begingroup\$ Thank you! As for your questions: 1) I decided to do without JavaDocs since nobody else except for me is going to use this code. It more or less guarantees O(1) for contains(). That is, no less than HashSet (strictly speaking, even HashSet doesn't give a 100% guarantee, and all elements can theoretically go into one bucket). add() and remove() are slower because of addresses mutations. 2) I know what fail-fast iterators are. I decided not to implement that functionality to keep it simpler. It is not optimized for multi-threaded environments \$\endgroup\$
    – Sergey
    Jul 4 at 14:50
  • \$\begingroup\$ 3) I don't know why you can't run it. That is, of course it doesn't have a main method or anything, but you can just copy and paste it, and then create a main class, create a MyHashSet instance and test it out. Anyway, I included my test class in the original post. 4) Classes from java.util suppress "unchecked" warnings all the time so I figured it's no big deal. How do I avoid that warning without such an annotation? \$\endgroup\$
    – Sergey
    Jul 4 at 14:51
  • \$\begingroup\$ 5) I don't like warnings that of no importance to me. That's why I annotated the constructors with @SuppressWarnings("unused"). It seems it's part of a Set's expected functionality to provide constructors that accept values for initial capacity and load factor so I included them even though I don't actually invoke them anywhere in my code. I removed them since they confuse you \$\endgroup\$
    – Sergey
    Jul 4 at 14:53
  • \$\begingroup\$ 6) I threw an exception if initialCapacity is less than three because if initialCapacity * 0.75 >= 2, then initialCapacity >= 2 2/3. I guess there won't be a never-ending resizing anyway since float * int = float (the decimal part won't be trimmed) so it may very well be it's an unnecessary requirement \$\endgroup\$
    – Sergey
    Jul 4 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.