Hash Binary Tree Map

Question

I made a map based on a binary tree ordered by hashcodes, with collisions fixed with equals(). Are there any improvements I could make?

public class HashTreeMap<K, V> implements Map<K, V> {

    Optional<Node<K, V>> root = Optional.empty();

    @Override
    public V put(final K key, final V value) {
        // Returns previous value associated with key

        if (root.isPresent()) {
            return root.get().put(key, value);
        } else {
            root = Node.createNode(key, value);
            return null;
        }
    }

    @Override
    public V get(final Object key) {
        if (root.isPresent()) {
            return root.get().get(key);
        } else {
            return null;
        }
    }

    @Override
    public int size() {
        if (root.isPresent()) {
            return root.get().size();
        } else {
            return 0;
        }
    }

    @Override
    public boolean isEmpty() {
        return !root.isPresent();
    }

    @Override
    public boolean containsKey(final Object key) {
        // TODO a better method, this could easily be improved
        final Set<K> keys = keySet();
        return keys.contains(key);
    }

    @Override
    public boolean containsValue(final Object value) {
        // TODO a better method, this could easily be improved
        final Collection<V> keys = values();
        return keys.contains(value);
    }

    @Override
    public V remove(final Object key) {
        if (root.isPresent()) {
            return root.get().remove(key);
        } else {
            return null;
        }
    }

    @Override
    public void putAll(final Map<? extends K, ? extends V> m) {
        for (final Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            put(e.getKey(), e.getValue());
        }
    }

    @Override
    public void clear() {
        this.root = Optional.empty();
    }

    @Override
    public Set<K> keySet() {
        // TODO a better method, this could easily be improved
        final Set<Map.Entry<K, V>> entries = entrySet();
        final Set<K> keys = new HashSet<>(entries.size());
        for (final Map.Entry<K, V> entry : entries) {
            keys.add(entry.getKey());
        }
        return keys;
    }

    @Override
    public Collection<V> values() {
        // TODO a better method, this could easily be improved
        final Set<Map.Entry<K, V>> entries = entrySet();
        final List<V> values = new ArrayList<>(entries.size());
        for (final Map.Entry<K, V> entry : entries) {
            values.add(entry.getValue());
        }
        return values;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        if (root.isPresent()) {
            final Set<Map.Entry<K, V>> set = new HashSet<>();
            root.get().addAllEntries(set);
            return set;
        } else {
            return new HashSet<>();
        }
    }

    @Override
    public String toString() {
        return "Tree{" + (root.isPresent() ? root.get().toString() : "") + "}";
    }

    private static class Node<K, V> {
        Optional<Node<K, V>> left = Optional.empty();
        Optional<Node<K, V>> right = Optional.empty();
        final int id;
        List<Entry<K, V>> entries = new LinkedList<>();

        public Node(final int id) {
            this.id = id;
        }

        public int size() {
            int leftSize = 0;
            int rightSize = 0;

            if (left.isPresent()) {
                leftSize = left.get().size();
            }
            if (right.isPresent()) {
                rightSize = right.get().size();
            }
            return entries.size() + leftSize + rightSize;
        }

        public V put(final K key, final V value) {
            V prevVal = null;
            final int idKey = key.hashCode();
            if (id == idKey) {
                final Iterator<Entry<K, V>> it = entries.iterator();
                // check for overlaps
                while (it.hasNext()) {
                    final Entry<K, V> e = it.next();
                    if (e.key.equals(key)) {
                        prevVal = e.value;
                        it.remove();
                    }
                }
                entries.add(new Entry<>(key, value));
            } else if (idKey < id) {
                if (left.isPresent()) {
                    prevVal = left.get().put(key, value);
                } else {
                    left = createNode(key, value);
                    prevVal = null;
                }
            } else if (idKey > id) {
                if (right.isPresent()) {
                    prevVal = right.get().put(key, value);
                } else {
                    right = createNode(key, value);
                    prevVal = null;
                }
            }
            return prevVal;
        }

        public V get(final Object key) {
            final int idKey = key.hashCode();
            if (id == idKey) {
                final Iterator<Entry<K, V>> it = entries.iterator();
                // check for overlaps
                while (it.hasNext()) {
                    final Entry<K, V> e = it.next();
                    if (e.key.equals(key)) {
                        return e.value;
                    }
                }
                // we found a matching hashcode, but no equal node
                return null;
            } else if (idKey < id) {
                if (left.isPresent()) {
                    return left.get().get(key);
                } else {
                    return null;
                }
            } else {
                // hashcode is greater than current node
                if (right.isPresent()) {
                    return right.get().get(key);
                } else {
                    return null;
                }
            }
        }

        public V remove(final Object key) {
            final int keyId = key.hashCode();
            if (keyId == id) {
                final Iterator<Entry<K, V>> it = entries.iterator();
                while (it.hasNext()) {
                    final Entry<K, V> e = it.next();
                    if (e.key.equals(key)) {
                        it.remove();
                        return e.value;
                    }
                }
                // matching hashcode, but no matching equals
                return null;
            } else if (keyId < id) {
                if (left.isPresent()) {
                    return left.get().remove(key);
                } else {
                    return null;
                }
            } else {
                if (right.isPresent()) {
                    return right.get().remove(key);
                } else {
                    return null;
                }
            }
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            for (final Entry<K, V> e : entries) {
                sb.append(e).append(',');
            }
            return (left.isPresent() ? left.get().toString() : "")
                    + sb.toString()
                    + (right.isPresent() ? right.get().toString() : "");
        }

        public static <K, V> Optional<Node<K, V>> createNode(final K key,
                final V value) {
            final Node<K, V> node = new Node<>(key.hashCode());
            node.entries.add(new Entry<>(key, value));
            return Optional.of(node);
        }

        public void addAllEntries(final Collection<Map.Entry<K, V>> s) {
            s.addAll(entries);
            if (left.isPresent()) {
                left.get().addAllEntries(s);
            }
            if (right.isPresent()) {
                right.get().addAllEntries(s);
            }
        }

        private static class Entry<K, V> implements Map.Entry<K, V> {
            private final K key;
            private V value;

            public Entry(final K key, final V value) {
                this.key = key;
                this.value = value;
            }

            @Override
            public String toString() {
                return key + "=>" + value;
            }

            @Override
            public K getKey() {
                return key;
            }

            @Override
            public V getValue() {
                return value;
            }

            @Override
            public V setValue(final V value) {
                final V old = this.value;
                this.value = value;
                return old;
            }

        }
    }
}

Answer 1

One little improvement you could make is that in several methods you have this structure:

if (condition) {
     ...
    return ...;
} else {
    ...
    return ...;
}

There is no need for the else statement. You can simply write:

if (condition) {
     ...
    return ...;
}
...
return ...;

A more drastic change would be rather than using Optional, you might consider using the "Null Object" design pattern. That is, create a NullNode implementation of (an interface) Node<K, V> that returns, for example, null for any get() and 0 for size(). This would eliminate a lot of conditionals and make the code significantly easier to read.

---

Update: As requested by David Harkness, I have knocked together an implementation based around a polymorphic Node object. I'm not saying this is necessarily a "better" implementation, but it just shows an alternative way of implementing the code that removes a large number of the conditionals.

Note: It's not a fully working implementation. It's just a gist. I haven't bothered implementing remove and if you put the same value twice it won't overwrite the original. I haven't done any testing on it, so it may be full of bugs. I'll leave it as an exercise to the reader to finish it off.

public static class HashTreeMap<K, V> implements Map<K, V> {

    private final Node<K, V> nullNode = new NullNode();
    private Node<K, V> root = nullNode;

    @Override
    public int size() {
        return root.size();
    }

    @Override
    public boolean isEmpty() {
        return root.size() == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return keySet().contains(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return values().contains(value);
    }

    @Override
    public V get(Object key) {
        return root.get(key);
    }

    @Override
    public V put(K key, V value) {
        V previousValue = root.get(key);
        root = root.put(key, value);
        return previousValue;
    }

    @Override
    public V remove(Object key) {
        // TODO
        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public void clear() {
        // TODO
    }

    @Override
    public Set<K> keySet() {
        return root.keySet();
    }

    @Override
    public Collection<V> values() {
        return root.values();
    }

    @Override
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        // TODO
        return null;
    }

    private interface Node<K, V> {

        V get(Object key);

        Node<K, V> put(K key, V value);

        int size();

        Set<K> keySet();

        Collection<V> values();
    }

    private class NullNode implements Node<K, V> {

        @Override
        public V get(Object key) {
            return null;
        }

        @Override
        public Node<K, V> put(K key, V value) {
            return new ConcreteNode(key, value);
        }

        @Override
        public int size() {
            return 0;
        }

        @Override
        public Set<K> keySet() {
            return Collections.emptySet();
        }

        @Override
        public Collection<V> values() {
            return Collections.emptyList();
        }
    }

    private class ConcreteNode implements Node<K, V> {

        private Node<K, V> left = nullNode;
        private Node<K, V> right = nullNode;
        private final List<Entry<K, V>> entries = new LinkedList<>();
        private final int ourHash;

        public ConcreteNode(K key, V value) {
            addEntry(key, value);
            this.ourHash = key.hashCode();
        }

        private void addEntry(K key, V value) {
            entries.add(new Entry<K, V>(key, value));
        }

        @Override
        public V get(Object key) {
            int hash = key.hashCode();
            if (hash == ourHash) {
                for (Entry<K, V> entry : entries) {
                    if (entry.key.equals(key)) {
                        return entry.value;
                    }
                }
                return null;
            } else if (hash < ourHash) {
                return left.get(key);
            } else {            
                return right.get(key);
            }
        }

        @Override
        public Node<K, V> put(K key, V value) {
            int hash = key.hashCode();
            if (hash == ourHash) {
                addEntry(key, value);
            } else if (hash < ourHash) {
                left = left.put(key, value);
            } else {
                right = right.put(key, value);
            }
            return this;
        }

        @Override
        public int size() {
            return entries.size() + left.size() + right.size();
        }

        @Override
        public Set<K> keySet() {
            Set<K> keys = new HashSet<>();
            for (Entry<K, V> entry : entries) {
                keys.add(entry.key);
            }
            keys.addAll(left.keySet());
            keys.addAll(right.keySet());
            return keys;
        }

        @Override
        public Collection<V> values() {
            List<V> values = new ArrayList<>();
            for (Entry<K, V> entry : entries) {
                values.add(entry.value);
            }
            values.addAll(left.values());
            values.addAll(right.values());
            return values;
        }
    }

    private static class Entry<K, V> {
        public final K key;
        public final V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

Answer 2

A tiny note: Optional is meant to be a return value only, not a field. It's not even Serializable because of this.

I see only disadvantages: While your code could perfectly work with Java 5 (after removal of diamonds, otherwise Java 7), it can't because of Optional (which unlike the diamonds is hard to remove). But actually, I always see only disadvantages of Optional but YMMV.

Note that your memory consumption and GC overhead sort of double and the speed sort of halves because of it (memory indirection is cheap when cached, but with a huge map or under memory pressure, it gets very expensive).