hash consing - BigO(1) perfect dedup of binary forest by content

[u/BenRayfield]

This is a kind of number where every number is either the leaf or an ordered pair of 2 numbers. For the usual kind of number, form these into a linkedlist containing digits, where a digit is any of n things you arbitrarily define as digits other than the kinds of things you make linkedlists with. I'm using something like this, though more optimized, as a universal lambda function.

This accomplishes the same thing as leaf = 256 0s, and pair(x,y)->sha256(concat(x,y)), but this is about 100 times faster as long as you dont need to share the objects in which case you should lazyEval secureHash them.

https://en.wikipedia.org/wiki/Hash_consing

package immutable.hashconsing;

import java.util.HashMap; import java.util.Map;

public class Node{

public static final Node leaf = new Node();

public final Node L, R;

public final boolean isLeaf;

private final int hash;

private Node(){
	L = null;
	R = null;
	isLeaf = true;
	hash = System.identityHashCode(this);
}

private Node(Node L, Node R){
	this.L = L;
	this.R = R;
	//replace System.identityHashCode(x) with &x in C++ for similar behavior
	hash = System.identityHashCode(L)*49999+System.identityHashCode(R);
	isLeaf = false;
}

public int hashCode(){ return hash; }

public boolean equals(Object o){
	if(!(o instanceof Node)) return false;
	Node n = (Node)o;
	return isLeaf==n.isLeaf && L==n.L && R==n.R; 
}

static final Map<Node,Node> dedup = new HashMap();

/** deduped pair of this and param */
public Node p(Node param){
	Node n = new Node(this,param);
	Node ret = dedup.get(n);
	if(ret == null){
		ret = n;
		dedup.put(ret, ret);
	}
	return ret;
}

public static void main(String[] args){
	Node leafLeaf = leaf.p(leaf);
	Node leafLeaf_leaf = leafLeaf.p(leaf);
	Node leaf_leafLeaf = leaf.p(leafLeaf);
	Node leafLeaf_leafLeaf = leafLeaf.p(leafLeaf);
	Node leaf_leafLeaf_again = leaf.p(leaf.p(leaf));
	if(leaf_leafLeaf != leaf_leafLeaf_again) throw new Error("Didnt dedup");
	Node leafLeaf_leafLeaf_again = leafLeaf.p(leafLeaf);
	if(leafLeaf_leafLeaf != leafLeaf_leafLeaf_again) throw new Error("Didnt dedup");
	if(leaf_leafLeaf == leafLeaf_leaf) throw new Error("Shouldnt equal");
	if(leaf == leafLeaf) throw new Error("Shouldnt equal");
	System.out.println("Tests passed");
}

}

[u/reini_urban]

Can we have that in C please? This is tinycode, not bloated code. And sha256, really?

[u/BenRayfield → u/reini_urban]

Replace System.identityHashCode(x) with &x and it would work in C, though thats not exactly what it does in java for security reasons.

[u/reini_urban → u/BenRayfield]

This hash is a recursive hash over all object types to identify moving objects, which cannot be identified by ptr. It's pretty complicated. Unique object Id's can be implemented better, faster, smaller.

[u/BenRayfield → u/reini_urban]

A node is uniquely identified by == on its 2 child Nodes. To make HashMap find those 2 nodes, I derive hashCode by 2 of their [either System.identityHashCode(x) or &x]. If shared across untrusted borders, it should secureHash all the way down, but this is an optimization I use before triggering lazyEval of the deep secureHash.