java - how to create custom hashtable iterator?

Question

I am currently trying to implement a Hashtable collection--I have everything up and running but I ran into kind of a conceptual problem when I was trying to define a custom iterator for the table. I have an internal class called 'HashEntry' which are the actual objects stored in the array--they store the key, the value, and the status of the entry, i.e. Empty, Active, Deleted.

private class HashEntry
{
    private TKey m_key;
    private TValue m_value;
    private EntryStatus status;

    //standard constructor
    public HashEntry(TKey key, TValue value)
    {
        m_key = key;
        m_value = value;
        status = EntryStatus.ACTIVE;
    }

    public HashEntry(TKey key, TValue value, EntryStatus i) {
        m_key = key;
        m_value = value;
        status = i;
    }

    //default 'empty' constructor
    public HashEntry()
    {
        //calls default constructor, creates placeholder entry
        m_key = null;
        m_value = null;
        status = EntryStatus.EMPTY;
    }

    //equals operator override, this override just compares compares
    // the objects held in the entry, so any object used with this
    // implementation must hae=ve its own equals override
    @Override
    public boolean equals(Object obj)
    {
        if (obj == null) { return false; }
        if (getClass() != obj.getClass()) { return false; }

        final HashEntry other = (HashEntry) obj;
        return (!((this.m_key == null) ? (other.m_key != null) : !this.m_key.equals(other.m_key)));
    }

    // override of the hashCode() function--just calls the hashCode
    // function of the embedded object, so that must be provided
    @Override
    public int hashCode()
    {
        return this.m_key.hashCode();
    }

    // toString override just returns the toString of the embedded object
    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        sb.append(m_key.toString()).append(m_value.toString());
        return sb.toString();
    }
}

This is the first part of my question--If I want to be able to iterate through the table, should I be iterating through (and therefore returning) HashEntry objects, or is it hashtable convention to iterate through the actual value stored in the table? The HashEntry class is private, so I assume its bad practice to return instances of it...

But if thats the case, how do I create an Hashtable iterator that iterates through its HashEntrys' objects? Do I have to define an iterator/iterable in HashEntry class?

Answer 1

Generally speaking, yes, it would probably be better if you did provide an iterator that iterates over HashEntrys, so users get both the key and value (and state) when iterating. Oftentimes the value will not make sense without the key, and vice versa.

Why don't you just make the HashEntry class a public static generic inner class, and make implementation-specific stuff private? You'll probably need to make HashEntry generic as well, because I'm assuming that your parent class (let's just call it MyHashTable) is also generic based on the TKey and TValue.

So, if I were you, I'd make you're HashEntry and MyHashTable look more like this:

// Note: implements Iterable<E> now
public class MyHashTable<TKey, TValue> implements Iterable<MyHashTable.HashEntry<TKey, TValue>>
{
    public Iterator<MyHashTable.HashEntry<TKey, TValue>> iterator() {
        // ...
        // Make and return your iterator here
        // ...
    }

    // Note: public and generic now
    public static class HashEntry<TKey, TValue>
    {
        private TKey m_key;
        private TValue m_value;
        private EntryStatus status;

        //standard constructor
        // Note: private now
        public HashEntry(TKey key, TValue value)
        {
            m_key = key;
            m_value = value;
            status = EntryStatus.ACTIVE;
        }

        // Note: private now
        private HashEntry(TKey key, TValue value, EntryStatus i) {
            m_key = key;
            m_value = value;
            status = i;
        }

        //default 'empty' constructor
        // Note: private now
        public HashEntry()
        {
            //calls default constructor, creates placeholder entry
            m_key = null;
            m_value = null;
            status = EntryStatus.EMPTY;
        }

        public TKey getKey() {
            return m_key;
        }

        public TValue getValue() {
            return m_value;
        }

        public EntryStatus getEntryStatus() {
            return status;
        }

        //equals operator override, this override just compares compares
        // the objects held in the entry, so any object used with this
        // implementation must hae=ve its own equals override
        @Override
        public boolean equals(Object obj)
        {
            if (obj == null) { return false; }
            if (getClass() != obj.getClass()) { return false; }

            final HashEntry other = (HashEntry) obj;
            return (!((this.m_key == null) ? (other.m_key != null) : !this.m_key.equals(other.m_key)));
        }

        // override of the hashCode() function--just calls the hashCode
        // function of the embedded object, so that must be provided
        @Override
        public int hashCode()
        {
            return this.m_key.hashCode();
        }

        // toString override just returns the toString of the embedded object
        @Override
        public String toString()
        {
            StringBuilder sb = new StringBuilder();
            sb.append(m_key.toString()).append(m_value.toString());
            return sb.toString();
        }
    }
}

Note that the HashEntry is an inner class of MyHashTable now, it's generic, and it's constructors are now private. This guarantees that nobody except that outer class MyHashTable can instantiate a HashEntry, because instantiating one outside of your hash table wouldn't make sense (see this). However, other people can access the keys and values of the entry through getters.

The iterator itself would be an instance of Iterator<MyHashTable.HashEntry<TKey, TValue>>. As for writing one, that depends on your own hash table implementation, but you basically you need a way get the next element in whatever sequence: Iterator<E>.next().

For example, here is an iterator() method implementation that iterates over a simple array:

private Type[] arrayList;
private int currentSize;

@Override
public Iterator<Type> iterator() {
    Iterator<Type> it = new Iterator<Type>() {

        private int currentIndex = 0;

        @Override
        public boolean hasNext() {
            return currentIndex < currentSize && arrayList[currentIndex] != null;
        }

        @Override
        public Type next() {
            return arrayList[currentIndex++];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
    return it;
}

(source: https://stackoverflow.com/a/5849625/837703)

Hope this helped a bit.