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;
 }
 }
}

• David Harkness: Keeping the else, you don't have to read the body of the if block to see the either-or logic. This matters less for simple guard clauses, of course.
• David Harkness: The Null Object pattern works better for data objects and unmodifiable results. Using it here would change the isPresent calls to instanceof checks in cases where you're modifying the tree. It may still pay off though since the classes have a lot more read methods.
• ᴇʟᴇvᴀтᴇ: Node is a private and internal, so you would be able to add an isModifiable() method to avoid having to use instanceof. Better yet, have a Node modifiableNode() method on NullNode that returns a new modifiable node or, for a real node, returns itself. No need for any conditional then. It's the beauty of polymorphism.
• David Harkness: But you need to store the new modifiable node when switching from the null object or you'll lose the data value you just added. I don't see a way to get rid of the conditional entirely.
• ᴇʟᴇvᴀтᴇ: You store it every time.

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).