Hash Binary Tree Map

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 implements Map {

Optional> 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 keys = keySet();
return keys.contains(key);
}

@Override
public boolean containsValue(final Object value) {
// TODO a better method, this could easily be improved
final Collection 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 m) {
for (final Map.Entry e : m.entrySet()) {
put(e.getKey(), e.getValue());
}
}

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

@Override
public Set keySet() {
// TODO a better method, this could easily be improved
final Set> entries = entrySet();
final Set keys = new HashSet<>(

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 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 implements Map {

private final Node nullNode = new NullNode();
private Node 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 m) {
for (Map.Entry entry : m.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}

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

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

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

@Override
public Set> entrySet() {
// TODO
return null;
}

private interface Node {

V get(Object key);

Node put(K key, V value);

int size();

Set keySet();

Collection values();
}

private class NullNode implements Node {

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

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

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

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

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

private class ConcreteNode implements Node {

private Node left = nullNode;
private Node right = nullNode;
private final List> 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(key, value));
}

@Override
public V get(Object key) {
int hash = key.hashCode();
if (hash == ourHash) {
for (Entry entry : entries) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
} else if (hash put(K key, V value) {
int hash = key.hashCode();
if (hash == ourHash) {
addEntry(key, value);
} else if (hash keySet() {
Set keys = new HashSet<>();
for (Entry entry : entries) {
keys.add(entry.key);
}
keys.addAll(left.keySet());
keys.addAll(right.keySet());
return keys;
}

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

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

public Entry(K

StackExchange Code Review Q#72186, answer score: 2