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.

  1.  
  2. package com.sanfoundry.datastructures;
  3.  
  4. import java.io.IOException;
  5. import java.io.ObjectInputStream;
  6. import java.io.ObjectOutputStream;
  7. import java.io.Serializable;
  8. import java.util.Arrays;
  9. import java.util.Collection;
  10. import java.util.HashMap;
  11. import java.util.Iterator;
  12. import java.util.Map;
  13. import java.util.Set;
  14.  
  15. interface HashTreeTraverser
  16. {
  17.     public void addNode(Object node, HashTree subTree);
  18.  
  19.     public void subtractNode();
  20.  
  21.     public void processPath();
  22. }
  23.  
  24. class TreeSearcher implements HashTreeTraverser
  25. {
  26.     Object target;
  27.     HashTree result;
  28.  
  29.     public TreeSearcher(Object t)
  30.     {
  31.         target = t;
  32.     }
  33.  
  34.     public HashTree getResult()
  35.     {
  36.         return result;
  37.     }
  38.  
  39.     public void addNode(Object node, HashTree subTree)
  40.     {
  41.         result = subTree.getTree(target);
  42.         if (result != null)
  43.         {
  44.             throw new RuntimeException("found"); // short circuit traversal
  45.                                                  // when found
  46.         }
  47.     }
  48.  
  49.     @Override
  50.     public void subtractNode()
  51.     {
  52.     }
  53.  
  54.     @Override
  55.     public void processPath()
  56.     {
  57.     }
  58. }
  59.  
  60. class ConvertToString implements HashTreeTraverser
  61. {
  62.     StringBuffer string = new StringBuffer(getClass().getName() + "{");
  63.     StringBuffer spaces = new StringBuffer();
  64.     int depth = 0;
  65.  
  66.     public void addNode(Object key, HashTree subTree)
  67.     {
  68.         depth++;
  69.         string.append("\n" + getSpaces() + key + " {");
  70.     }
  71.  
  72.     public void subtractNode()
  73.     {
  74.         string.append("\n" + getSpaces() + "}");
  75.         depth--;
  76.     }
  77.  
  78.     public void processPath()
  79.     {
  80.     }
  81.  
  82.     public String toString()
  83.     {
  84.         string.append("\n}");
  85.         return string.toString();
  86.     }
  87.  
  88.     private String getSpaces()
  89.     {
  90.         if (spaces.length() < depth * 2)
  91.         {
  92.             while (spaces.length() < depth * 2)
  93.             {
  94.                 spaces.append("  ");
  95.             }
  96.         }
  97.         else if (spaces.length() > depth * 2)
  98.         {
  99.             spaces.setLength(depth * 2);
  100.         }
  101.         return spaces.toString();
  102.     }
  103. }
  104.  
  105. @SuppressWarnings({ "rawtypes", "unchecked" })
  106. public class HashTree implements Serializable, Map
  107. {
  108.     private static final long serialVersionUID = 5526070397395889719L;
  109.  
  110.     public HashTree()
  111.     {
  112.         data = new HashMap();
  113.     }
  114.  
  115.     public HashTree(Object key)
  116.     {
  117.         data = new HashMap();
  118.         data.put(key, new HashTree());
  119.     }
  120.  
  121.     public void putAll(Map map)
  122.     {
  123.         if (map instanceof HashTree)
  124.         {
  125.             this.add((HashTree) map);
  126.         }
  127.         else
  128.         {
  129.             throw new UnsupportedOperationException(
  130.                     "can only putAll other HashTree objects");
  131.         }
  132.     }
  133.  
  134.     public Set entrySet()
  135.     {
  136.         return data.entrySet();
  137.     }
  138.  
  139.     public boolean containsValue(Object value)
  140.     {
  141.         return data.containsValue(value);
  142.     }
  143.  
  144.     public Object put(Object key, Object value)
  145.     {
  146.         Object previous = data.get(key);
  147.         add(key, value);
  148.         return previous;
  149.     }
  150.  
  151.     public void clear()
  152.     {
  153.         data.clear();
  154.     }
  155.  
  156.     public Collection values()
  157.     {
  158.         return data.values();
  159.     }
  160.  
  161.     public void add(Object key, HashTree subTree)
  162.     {
  163.         add(key);
  164.         getTree(key).add(subTree);
  165.     }
  166.  
  167.     public void add(HashTree newTree)
  168.     {
  169.         Iterator iter = newTree.list().iterator();
  170.         while (iter.hasNext())
  171.         {
  172.             Object item = iter.next();
  173.             add(item);
  174.             getTree(item).add(newTree.getTree(item));
  175.         }
  176.     }
  177.  
  178.     public HashTree(Collection keys)
  179.     {
  180.         data = new HashMap();
  181.         Iterator it = keys.iterator();
  182.         while (it.hasNext())
  183.         {
  184.             data.put(it.next(), new HashTree());
  185.         }
  186.     }
  187.  
  188.     public HashTree(Object[] keys)
  189.     {
  190.         data = new HashMap();
  191.         for (int x = 0; x < keys.length; x++)
  192.         {
  193.             data.put(keys[x], new HashTree());
  194.         }
  195.     }
  196.  
  197.     public boolean containsKey(Object o)
  198.     {
  199.         return data.containsKey(o);
  200.     }
  201.  
  202.     public boolean isEmpty()
  203.     {
  204.         return data.isEmpty();
  205.     }
  206.  
  207.     public void set(Object key, Object value)
  208.     {
  209.         data.put(key, createNewTree(value));
  210.     }
  211.  
  212.     public void set(Object key, HashTree t)
  213.     {
  214.         data.put(key, t);
  215.     }
  216.  
  217.     public void set(Object key, Object[] values)
  218.     {
  219.         data.put(key, createNewTree(Arrays.asList(values)));
  220.     }
  221.  
  222.     public void set(Object key, Collection values)
  223.     {
  224.         data.put(key, createNewTree(values));
  225.     }
  226.  
  227.     public void set(Object[] treePath, Object[] values)
  228.     {
  229.         if (treePath != null && values != null)
  230.         {
  231.             set(Arrays.asList(treePath), Arrays.asList(values));
  232.         }
  233.     }
  234.  
  235.     public void set(Object[] treePath, Collection values)
  236.     {
  237.         if (treePath != null)
  238.         {
  239.             set(Arrays.asList(treePath), values);
  240.         }
  241.     }
  242.  
  243.     public void set(Collection treePath, Object[] values)
  244.     {
  245.         HashTree tree = addTreePath(treePath);
  246.         tree.set(Arrays.asList(values));
  247.     }
  248.  
  249.     public void set(Collection values)
  250.     {
  251.         clear();
  252.         this.add(values);
  253.     }
  254.  
  255.     public void set(Collection treePath, Collection values)
  256.     {
  257.         HashTree tree = addTreePath(treePath);
  258.         tree.set(values);
  259.     }
  260.  
  261.     public HashTree add(Object key)
  262.     {
  263.         if (!data.containsKey(key))
  264.         {
  265.             HashTree newTree = createNewTree();
  266.             data.put(key, newTree);
  267.             return newTree;
  268.         }
  269.         else
  270.         {
  271.             return getTree(key);
  272.         }
  273.     }
  274.  
  275.     public void add(Object[] keys)
  276.     {
  277.         for (int x = 0; x < keys.length; x++)
  278.         {
  279.             add(keys[x]);
  280.         }
  281.     }
  282.  
  283.     public void add(Collection keys)
  284.     {
  285.         Iterator it = keys.iterator();
  286.         while (it.hasNext())
  287.         {
  288.             add(it.next());
  289.         }
  290.     }
  291.  
  292.     public HashTree add(Object key, Object value)
  293.     {
  294.         add(key);
  295.         return getTree(key).add(value);
  296.     }
  297.  
  298.     public void add(Object key, Object[] values)
  299.     {
  300.         add(key);
  301.         getTree(key).add(values);
  302.     }
  303.  
  304.     public void add(Object key, Collection values)
  305.     {
  306.         add(key);
  307.         getTree(key).add(values);
  308.     }
  309.  
  310.     public void add(Object[] treePath, Object[] values)
  311.     {
  312.         if (treePath != null)
  313.         {
  314.             add(Arrays.asList(treePath), Arrays.asList(values));
  315.         }
  316.     }
  317.  
  318.     public void add(Object[] treePath, Collection values)
  319.     {
  320.         if (treePath != null)
  321.         {
  322.             add(Arrays.asList(treePath), values);
  323.         }
  324.     }
  325.  
  326.     public HashTree add(Object[] treePath, Object value)
  327.     {
  328.         return add(Arrays.asList(treePath), value);
  329.     }
  330.  
  331.     public void add(Collection treePath, Object[] values)
  332.     {
  333.         HashTree tree = addTreePath(treePath);
  334.         tree.add(Arrays.asList(values));
  335.     }
  336.  
  337.     public HashTree add(Collection treePath, Object value)
  338.     {
  339.         HashTree tree = addTreePath(treePath);
  340.         return tree.add(value);
  341.     }
  342.  
  343.     public void add(Collection treePath, Collection values)
  344.     {
  345.         HashTree tree = addTreePath(treePath);
  346.         tree.add(values);
  347.     }
  348.  
  349.     protected HashTree addTreePath(Collection treePath)
  350.     {
  351.         HashTree tree = this;
  352.         Iterator iter = treePath.iterator();
  353.         while (iter.hasNext())
  354.         {
  355.             Object temp = iter.next();
  356.             tree.add(temp);
  357.             tree = tree.getTree(temp);
  358.         }
  359.         return tree;
  360.     }
  361.  
  362.     public HashTree getTree(Object key)
  363.     {
  364.         return (HashTree) data.get(key);
  365.     }
  366.  
  367.     public Object get(Object key)
  368.     {
  369.         return getTree(key);
  370.     }
  371.  
  372.     public HashTree getTree(Object[] treePath)
  373.     {
  374.         if (treePath != null)
  375.         {
  376.             return getTree(Arrays.asList(treePath));
  377.         }
  378.         else
  379.         {
  380.             return this;
  381.         }
  382.     }
  383.  
  384.     public Object clone()
  385.     {
  386.         HashTree newTree = new HashTree();
  387.         cloneTree(newTree);
  388.         return newTree;
  389.     }
  390.  
  391.     protected void cloneTree(HashTree newTree)
  392.     {
  393.         Iterator iter = list().iterator();
  394.         while (iter.hasNext())
  395.         {
  396.             Object key = iter.next();
  397.             newTree.set(key, (HashTree) getTree(key).clone());
  398.         }
  399.     }
  400.  
  401.     protected HashTree createNewTree()
  402.     {
  403.         return new HashTree();
  404.     }
  405.  
  406.     protected HashTree createNewTree(Object key)
  407.     {
  408.         return new HashTree(key);
  409.     }
  410.  
  411.     protected HashTree createNewTree(Collection values)
  412.     {
  413.         return new HashTree(values);
  414.     }
  415.  
  416.     public HashTree getTree(Collection treePath)
  417.     {
  418.         return getTreePath(treePath);
  419.     }
  420.  
  421.     public Collection list()
  422.     {
  423.         return data.keySet();
  424.     }
  425.  
  426.     public Collection list(Object key)
  427.     {
  428.         HashTree temp = (HashTree) data.get(key);
  429.         if (temp != null)
  430.         {
  431.             return temp.list();
  432.         }
  433.         else
  434.         {
  435.             return null;
  436.         }
  437.     }
  438.  
  439.     public Object remove(Object key)
  440.     {
  441.         return data.remove(key);
  442.     }
  443.  
  444.     public Collection list(Object[] treePath)
  445.     {
  446.         if (treePath != null)
  447.         {
  448.             return list(Arrays.asList(treePath));
  449.         }
  450.         else
  451.         {
  452.             return list();
  453.         }
  454.     }
  455.  
  456.     public Collection list(Collection treePath)
  457.     {
  458.         return getTreePath(treePath).list();
  459.     }
  460.  
  461.     public Object replace(Object currentKey, Object newKey)
  462.     {
  463.         HashTree tree = getTree(currentKey);
  464.         data.remove(currentKey);
  465.         data.put(newKey, tree);
  466.         return null;
  467.     }
  468.  
  469.     public Object[] getArray()
  470.     {
  471.         return data.keySet().toArray();
  472.     }
  473.  
  474.     public Object[] getArray(Object key)
  475.     {
  476.         return getTree(key).getArray();
  477.     }
  478.  
  479.     public Object[] getArray(Object[] treePath)
  480.     {
  481.         if (treePath != null)
  482.         {
  483.             return getArray(Arrays.asList(treePath));
  484.         }
  485.         else
  486.         {
  487.             return getArray();
  488.         }
  489.     }
  490.  
  491.     public Object[] getArray(Collection treePath)
  492.     {
  493.         HashTree tree = getTreePath(treePath);
  494.         return tree.getArray();
  495.     }
  496.  
  497.     protected HashTree getTreePath(Collection treePath)
  498.     {
  499.         HashTree tree = this;
  500.         Iterator iter = treePath.iterator();
  501.         while (iter.hasNext())
  502.         {
  503.             Object temp = iter.next();
  504.             tree = tree.getTree(temp);
  505.         }
  506.         return tree;
  507.     }
  508.  
  509.     public int hashCode()
  510.     {
  511.         return data.hashCode() * 7;
  512.     }
  513.  
  514.     public boolean equals(Object o)
  515.     {
  516.         if (!(o instanceof HashTree))
  517.             return false;
  518.         HashTree oo = (HashTree) o;
  519.         if (oo.size() != this.size())
  520.             return false;
  521.         return data.equals(oo.data);
  522.     }
  523.  
  524.     public Set keySet()
  525.     {
  526.         return data.keySet();
  527.     }
  528.  
  529.     public HashTree search(Object key)
  530.     {
  531.         HashTree result = getTree(key);
  532.         if (result != null)
  533.         {
  534.             return result;
  535.         }
  536.         TreeSearcher searcher = new TreeSearcher(key);
  537.         try
  538.         {
  539.             traverse(searcher);
  540.         }
  541.         catch (Exception e)
  542.         {
  543.             // do nothing - means object is found
  544.         }
  545.         return searcher.getResult();
  546.     }
  547.  
  548.     void readObject(ObjectInputStream ois) throws ClassNotFoundException,
  549.             IOException
  550.     {
  551.         ois.defaultReadObject();
  552.     }
  553.  
  554.     void writeObject(ObjectOutputStream oos) throws IOException
  555.     {
  556.         oos.defaultWriteObject();
  557.     }
  558.  
  559.     public int size()
  560.     {
  561.         return data.size();
  562.     }
  563.  
  564.     public void traverse(HashTreeTraverser visitor)
  565.     {
  566.         Iterator iter = list().iterator();
  567.         while (iter.hasNext())
  568.         {
  569.             Object item = iter.next();
  570.             visitor.addNode(item, getTree(item));
  571.             getTree(item).traverseInto(visitor);
  572.         }
  573.     }
  574.  
  575.     private void traverseInto(HashTreeTraverser visitor)
  576.     {
  577.         if (list().size() == 0)
  578.         {
  579.             visitor.processPath();
  580.         }
  581.         else
  582.         {
  583.             Iterator iter = list().iterator();
  584.             while (iter.hasNext())
  585.             {
  586.                 Object item = iter.next();
  587.                 visitor.addNode(item, getTree(item));
  588.                 getTree(item).traverseInto(visitor);
  589.             }
  590.         }
  591.         visitor.subtractNode();
  592.     }
  593.  
  594.     public String toString()
  595.     {
  596.         ConvertToString converter = new ConvertToString();
  597.         traverse(converter);
  598.         return converter.toString();
  599.     }
  600.  
  601.     protected Map data;
  602.  
  603.     public static void main(String args[])
  604.     {
  605.         Collection treePath = Arrays
  606.                 .asList(new String[] { "1", "2", "3", "4" });
  607.         HashTree tree = new HashTree();
  608.         tree.add(treePath, "value");
  609.         HashTree tree1 = new HashTree("abcd");
  610.         HashTree tree2 = new HashTree("abcd");
  611.         HashTree tree3 = new HashTree("abcde");
  612.         HashTree tree4 = new HashTree("abcde");
  613.         System.out.println("Is tree1 equals tree2: " + tree1.equals(tree1));
  614.         System.out.println("Is hashcodes of tree1 and tree2 are equal: "
  615.                 + (tree1.hashCode() == tree2.hashCode()));
  616.         System.out.println("Is tree3 equals tree3: " + tree3.equals(tree3));
  617.         tree1.add("abcd", tree3);
  618.         System.out.println("Is modified tree1 is equal to tree3: "
  619.                 + tree1.equals(tree2));
  620.         tree2.add("abcd", tree4);
  621.         System.out.println("Is modified tree2 equals tree1: "
  622.                 + tree1.equals(tree2));
  623.         System.out.println("Is hashcodes are equal: "
  624.                 + (tree1.hashCode() == tree2.hashCode()));
  625.     }
  626. }

Output:

advertisement
$ 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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.