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
Related posts:
Lớp TreeMap trong Java
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Implement Self organizing List
Java Program to Implement Bucket Sort
Java Program to Find the Connected Components of an UnDirected Graph
A Quick JUnit vs TestNG Comparison
Java Program to Implement Dijkstra’s Algorithm using Set
New Features in Java 9
Java Program to Check the Connectivity of Graph Using BFS
A Guide to TreeMap in Java
Java Switch Statement
Spring Security – security none, filters none, access permitAll
Hướng dẫn Java Design Pattern – Proxy
Spring Boot Configuration with Jasypt
Compact Strings in Java 9
Java Program to Implement Network Flow Problem
Guide to Mustache with Spring Boot
Lớp Properties trong java
Converting a Stack Trace to a String in Java
Constructor Dependency Injection in Spring
Java Program to Implement Sieve Of Sundaram
Java Program to Solve Tower of Hanoi Problem using Stacks
Introduction to Java 8 Streams
Java Program to Perform Stooge Sort
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Spring Cloud – Securing Services
Tạo chương trình Java đầu tiên sử dụng Eclipse
Guide to java.util.concurrent.Locks
List Interface trong Java
Join and Split Arrays and Collections in Java
Java Program to Implement Aho-Corasick Algorithm for String Matching
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect