Java Program to Implement Hash Tree

This is a java program to implement Hash Tree. In computer science, a hash tree (or hash trie) is a persistent data structure that can be used to implement sets and maps, intended to replace hash tables in purely functional programming. In its basic form, a hash tree stores the hashes of its keys, regarded as strings of bits, in a trie, with the actual keys and (optional) values stored at the trie’s “final” nodes.

Here is the source code of the Java Program to Implement Hash Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.maixuanviet.datastructures;
 
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
 
interface HashTreeTraverser
{
    public void addNode(Object node, HashTree subTree);
 
    public void subtractNode();
 
    public void processPath();
}
 
class TreeSearcher implements HashTreeTraverser
{
    Object target;
    HashTree result;
 
    public TreeSearcher(Object t)
    {
        target = t;
    }
 
    public HashTree getResult()
    {
        return result;
    }
 
    public void addNode(Object node, HashTree subTree)
    {
        result = subTree.getTree(target);
        if (result != null)
        {
            throw new RuntimeException("found"); // short circuit traversal
                                                 // when found
        }
    }
 
    @Override
    public void subtractNode()
    {
    }
 
    @Override
    public void processPath()
    {
    }
}
 
class ConvertToString implements HashTreeTraverser
{
    StringBuffer string = new StringBuffer(getClass().getName() + "{");
    StringBuffer spaces = new StringBuffer();
    int depth = 0;
 
    public void addNode(Object key, HashTree subTree)
    {
        depth++;
        string.append("\n" + getSpaces() + key + " {");
    }
 
    public void subtractNode()
    {
        string.append("\n" + getSpaces() + "}");
        depth--;
    }
 
    public void processPath()
    {
    }
 
    public String toString()
    {
        string.append("\n}");
        return string.toString();
    }
 
    private String getSpaces()
    {
        if (spaces.length() < depth * 2)
        {
            while (spaces.length() < depth * 2)
            {
                spaces.append("  ");
            }
        }
        else if (spaces.length() > depth * 2)
        {
            spaces.setLength(depth * 2);
        }
        return spaces.toString();
    }
}
 
@SuppressWarnings({ "rawtypes", "unchecked" })
public class HashTree implements Serializable, Map
{
    private static final long serialVersionUID = 5526070397395889719L;
 
    public HashTree()
    {
        data = new HashMap();
    }
 
    public HashTree(Object key)
    {
        data = new HashMap();
        data.put(key, new HashTree());
    }
 
    public void putAll(Map map)
    {
        if (map instanceof HashTree)
        {
            this.add((HashTree) map);
        }
        else
        {
            throw new UnsupportedOperationException(
                    "can only putAll other HashTree objects");
        }
    }
 
    public Set entrySet()
    {
        return data.entrySet();
    }
 
    public boolean containsValue(Object value)
    {
        return data.containsValue(value);
    }
 
    public Object put(Object key, Object value)
    {
        Object previous = data.get(key);
        add(key, value);
        return previous;
    }
 
    public void clear()
    {
        data.clear();
    }
 
    public Collection values()
    {
        return data.values();
    }
 
    public void add(Object key, HashTree subTree)
    {
        add(key);
        getTree(key).add(subTree);
    }
 
    public void add(HashTree newTree)
    {
        Iterator iter = newTree.list().iterator();
        while (iter.hasNext())
        {
            Object item = iter.next();
            add(item);
            getTree(item).add(newTree.getTree(item));
        }
    }
 
    public HashTree(Collection keys)
    {
        data = new HashMap();
        Iterator it = keys.iterator();
        while (it.hasNext())
        {
            data.put(it.next(), new HashTree());
        }
    }
 
    public HashTree(Object[] keys)
    {
        data = new HashMap();
        for (int x = 0; x < keys.length; x++)
        {
            data.put(keys[x], new HashTree());
        }
    }
 
    public boolean containsKey(Object o)
    {
        return data.containsKey(o);
    }
 
    public boolean isEmpty()
    {
        return data.isEmpty();
    }
 
    public void set(Object key, Object value)
    {
        data.put(key, createNewTree(value));
    }
 
    public void set(Object key, HashTree t)
    {
        data.put(key, t);
    }
 
    public void set(Object key, Object[] values)
    {
        data.put(key, createNewTree(Arrays.asList(values)));
    }
 
    public void set(Object key, Collection values)
    {
        data.put(key, createNewTree(values));
    }
 
    public void set(Object[] treePath, Object[] values)
    {
        if (treePath != null && values != null)
        {
            set(Arrays.asList(treePath), Arrays.asList(values));
        }
    }
 
    public void set(Object[] treePath, Collection values)
    {
        if (treePath != null)
        {
            set(Arrays.asList(treePath), values);
        }
    }
 
    public void set(Collection treePath, Object[] values)
    {
        HashTree tree = addTreePath(treePath);
        tree.set(Arrays.asList(values));
    }
 
    public void set(Collection values)
    {
        clear();
        this.add(values);
    }
 
    public void set(Collection treePath, Collection values)
    {
        HashTree tree = addTreePath(treePath);
        tree.set(values);
    }
 
    public HashTree add(Object key)
    {
        if (!data.containsKey(key))
        {
            HashTree newTree = createNewTree();
            data.put(key, newTree);
            return newTree;
        }
        else
        {
            return getTree(key);
        }
    }
 
    public void add(Object[] keys)
    {
        for (int x = 0; x < keys.length; x++)
        {
            add(keys[x]);
        }
    }
 
    public void add(Collection keys)
    {
        Iterator it = keys.iterator();
        while (it.hasNext())
        {
            add(it.next());
        }
    }
 
    public HashTree add(Object key, Object value)
    {
        add(key);
        return getTree(key).add(value);
    }
 
    public void add(Object key, Object[] values)
    {
        add(key);
        getTree(key).add(values);
    }
 
    public void add(Object key, Collection values)
    {
        add(key);
        getTree(key).add(values);
    }
 
    public void add(Object[] treePath, Object[] values)
    {
        if (treePath != null)
        {
            add(Arrays.asList(treePath), Arrays.asList(values));
        }
    }
 
    public void add(Object[] treePath, Collection values)
    {
        if (treePath != null)
        {
            add(Arrays.asList(treePath), values);
        }
    }
 
    public HashTree add(Object[] treePath, Object value)
    {
        return add(Arrays.asList(treePath), value);
    }
 
    public void add(Collection treePath, Object[] values)
    {
        HashTree tree = addTreePath(treePath);
        tree.add(Arrays.asList(values));
    }
 
    public HashTree add(Collection treePath, Object value)
    {
        HashTree tree = addTreePath(treePath);
        return tree.add(value);
    }
 
    public void add(Collection treePath, Collection values)
    {
        HashTree tree = addTreePath(treePath);
        tree.add(values);
    }
 
    protected HashTree addTreePath(Collection treePath)
    {
        HashTree tree = this;
        Iterator iter = treePath.iterator();
        while (iter.hasNext())
        {
            Object temp = iter.next();
            tree.add(temp);
            tree = tree.getTree(temp);
        }
        return tree;
    }
 
    public HashTree getTree(Object key)
    {
        return (HashTree) data.get(key);
    }
 
    public Object get(Object key)
    {
        return getTree(key);
    }
 
    public HashTree getTree(Object[] treePath)
    {
        if (treePath != null)
        {
            return getTree(Arrays.asList(treePath));
        }
        else
        {
            return this;
        }
    }
 
    public Object clone()
    {
        HashTree newTree = new HashTree();
        cloneTree(newTree);
        return newTree;
    }
 
    protected void cloneTree(HashTree newTree)
    {
        Iterator iter = list().iterator();
        while (iter.hasNext())
        {
            Object key = iter.next();
            newTree.set(key, (HashTree) getTree(key).clone());
        }
    }
 
    protected HashTree createNewTree()
    {
        return new HashTree();
    }
 
    protected HashTree createNewTree(Object key)
    {
        return new HashTree(key);
    }
 
    protected HashTree createNewTree(Collection values)
    {
        return new HashTree(values);
    }
 
    public HashTree getTree(Collection treePath)
    {
        return getTreePath(treePath);
    }
 
    public Collection list()
    {
        return data.keySet();
    }
 
    public Collection list(Object key)
    {
        HashTree temp = (HashTree) data.get(key);
        if (temp != null)
        {
            return temp.list();
        }
        else
        {
            return null;
        }
    }
 
    public Object remove(Object key)
    {
        return data.remove(key);
    }
 
    public Collection list(Object[] treePath)
    {
        if (treePath != null)
        {
            return list(Arrays.asList(treePath));
        }
        else
        {
            return list();
        }
    }
 
    public Collection list(Collection treePath)
    {
        return getTreePath(treePath).list();
    }
 
    public Object replace(Object currentKey, Object newKey)
    {
        HashTree tree = getTree(currentKey);
        data.remove(currentKey);
        data.put(newKey, tree);
        return null;
    }
 
    public Object[] getArray()
    {
        return data.keySet().toArray();
    }
 
    public Object[] getArray(Object key)
    {
        return getTree(key).getArray();
    }
 
    public Object[] getArray(Object[] treePath)
    {
        if (treePath != null)
        {
            return getArray(Arrays.asList(treePath));
        }
        else
        {
            return getArray();
        }
    }
 
    public Object[] getArray(Collection treePath)
    {
        HashTree tree = getTreePath(treePath);
        return tree.getArray();
    }
 
    protected HashTree getTreePath(Collection treePath)
    {
        HashTree tree = this;
        Iterator iter = treePath.iterator();
        while (iter.hasNext())
        {
            Object temp = iter.next();
            tree = tree.getTree(temp);
        }
        return tree;
    }
 
    public int hashCode()
    {
        return data.hashCode() * 7;
    }
 
    public boolean equals(Object o)
    {
        if (!(o instanceof HashTree))
            return false;
        HashTree oo = (HashTree) o;
        if (oo.size() != this.size())
            return false;
        return data.equals(oo.data);
    }
 
    public Set keySet()
    {
        return data.keySet();
    }
 
    public HashTree search(Object key)
    {
        HashTree result = getTree(key);
        if (result != null)
        {
            return result;
        }
        TreeSearcher searcher = new TreeSearcher(key);
        try
        {
            traverse(searcher);
        }
        catch (Exception e)
        {
            // do nothing - means object is found
        }
        return searcher.getResult();
    }
 
    void readObject(ObjectInputStream ois) throws ClassNotFoundException,
            IOException
    {
        ois.defaultReadObject();
    }
 
    void writeObject(ObjectOutputStream oos) throws IOException
    {
        oos.defaultWriteObject();
    }
 
    public int size()
    {
        return data.size();
    }
 
    public void traverse(HashTreeTraverser visitor)
    {
        Iterator iter = list().iterator();
        while (iter.hasNext())
        {
            Object item = iter.next();
            visitor.addNode(item, getTree(item));
            getTree(item).traverseInto(visitor);
        }
    }
 
    private void traverseInto(HashTreeTraverser visitor)
    {
        if (list().size() == 0)
        {
            visitor.processPath();
        }
        else
        {
            Iterator iter = list().iterator();
            while (iter.hasNext())
            {
                Object item = iter.next();
                visitor.addNode(item, getTree(item));
                getTree(item).traverseInto(visitor);
            }
        }
        visitor.subtractNode();
    }
 
    public String toString()
    {
        ConvertToString converter = new ConvertToString();
        traverse(converter);
        return converter.toString();
    }
 
    protected Map data;
 
    public static void main(String args[])
    {
        Collection treePath = Arrays
                .asList(new String[] { "1", "2", "3", "4" });
        HashTree tree = new HashTree();
        tree.add(treePath, "value");
        HashTree tree1 = new HashTree("abcd");
        HashTree tree2 = new HashTree("abcd");
        HashTree tree3 = new HashTree("abcde");
        HashTree tree4 = new HashTree("abcde");
        System.out.println("Is tree1 equals tree2: " + tree1.equals(tree1));
        System.out.println("Is hashcodes of tree1 and tree2 are equal: "
                + (tree1.hashCode() == tree2.hashCode()));
        System.out.println("Is tree3 equals tree3: " + tree3.equals(tree3));
        tree1.add("abcd", tree3);
        System.out.println("Is modified tree1 is equal to tree3: "
                + tree1.equals(tree2));
        tree2.add("abcd", tree4);
        System.out.println("Is modified tree2 equals tree1: "
                + tree1.equals(tree2));
        System.out.println("Is hashcodes are equal: "
                + (tree1.hashCode() == tree2.hashCode()));
    }
}

Output:

$ javac HashTree.java
$ java HashTree
 
Is tree1 equals tree2: true
Is hashcodes of tree1 and tree2 are equal: true
Is tree3 equals tree3: true
Is modified tree1 is equal to tree3: false
Is modified tree2 equals tree1: true
Is hashcodes are equal: true