2
\$\begingroup\$

My friend was asked to implement a hashtable with a binary search tree. I tried practicing it myself, and it turned out to be very verbose. I need suggestions to clean this up!

public class HashMapBst<K extends Comparable, V> {
    private class Entry<K extends Comparable, V> implements Comparable<Entry> {
        private K key;
        private V val;
        Entry left;
        Entry right;

        public Entry(K k, V v) {
            key = k;
            val = v;
        }

        public int compareTo(Entry e) {
            return this.key.compareTo(e.key);
        }

        public void insert(Entry e) {
            if (this.compareTo(e) == 0) {
                this.val = (V) e.getVal();
            } else if (this.compareTo(e) < 0) {
                if (left == null) {
                    left = e;
                } else {
                    left.insert(e);
                }
            } else {
                if (right == null) {
                    right = e;
                } else {
                    right.insert(e);
                }
            }
        }

        public V findValue(K key) {
            if (this.key.equals(key)) {
                return val;
            } else if (left != null && left.findValue(key) != null) {
                return (V) left.findValue(key);
            } else if (right != null && right.findValue(key) != null) {
                return (V) right.findValue(key);
            }
            return null;
        }

        public Entry getNewTree(K key) {
            if (this.key.equals(key)) {
                Entry newRoot = processRight();
                if (newRoot != null) {
                    newRoot.setLeft(left);
                    newRoot.setRight(right);
                    return newRoot;
                } else if (left != null) {
                    return left;
                }
            } else if (left == null && right == null) {
                return null;
            } else if (left != null && left.getNewTree(key) != null) {
                return left.getNewTree(key);
            } else if (right != null && right.getNewTree(key) != null) {
                return right.getNewTree(key);
            }
            return null;
        }

        public void inOrder() {
            if (left != null) {
                left.inOrder();
            }
            System.out.println("Key: " + key + "; Value: " + val);
            if (right != null) {
                right.inOrder();
            }
        }

        public K getKey() {
            return key;
        }

        public V getVal() {
            return val;
        }

        public Entry getLeft() {
            return left;
        }

        public Entry getRight() {
            return right;
        }

        public void setLeft(Entry left) {
            this.left = left;
        }

        public void setRight(Entry right) {
            this.right = right;
        }

        private Entry processRight() {
            if (right == null) {
                return null;
            }
            if (right.getLeft() == null) {
                return right;
            }
            Entry curr = right;
            while (curr.getLeft().getLeft() != null) {
                curr = curr.getLeft();
            }
            Entry temp = curr.getLeft();
            curr.setLeft(null);
            return temp;
        }

    }

    private int tableSize = 31;
    List<Entry> table = new ArrayList<Entry>(tableSize);

    public HashMapBst() {
        for (int i = 0; i < tableSize; i++) {
            table.add(null);
        }
    }

    private int hash(K key) {
        return Math.abs(key.hashCode() % tableSize);
    }

    public void put(K key, V val) {
        int hash = hash(key);
        if (table.get(hash) != null) {
            table.get(hash).insert(new Entry(key, val));
        } else {
            table.set(hash, new Entry(key, val));
        }
    }

    public V get(K key) {
        int hash = hash(key);
        if (table.get(hash) == null) {
            return null;
        } else {
            return (V) table.get(hash).findValue(key);
        }
    }

    public void remove(K key) {
        int hash = hash(key);
        if (table.get(hash) == null) {
            return;
        }
        table.set(hash, table.get(hash).getNewTree(key));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.