# ordered tree data structure

I have a map $f:X\to \mathbb{N}$ and I wish to find $x,x'\in X$ such that $f(x)=f(x')$. Since such elements are rare, I will have to check very many elements and perform many comparisons, so I suspect the best way to do this is using an ordered tree data structure, which stores elements $x\in X$ by comparing their values $f(x)$, and tells if an element with same value is already in the tree.

Is there an OrderedTree data structure (or something similar, e.g. ordered list) implemented in Mathematica?

• I there anything known about f, so one can use this to minimize the amount of work? Jan 23, 2015 at 6:59
• Have a look at DownValues. I suspect that will serve you better. Basically you'd be storing values to give an "inverse" of f (quotes because it is multivalued), and any time one was encountered for some x', you'd have your corresponding x stored. Jan 23, 2015 at 15:56
• @mgamer: Concretely, my function is y=StringTake[IntegerString[Hash[x,"SHA256"],16],-13];] where x=ToString@RandomInteger[1,1000000].
– Leo
Jan 23, 2015 at 22:54
• @DanielLichtblau Hmm, in the Help manual and on the net, I did not find any command to obtain the preimage of f via DownValues. Any suggestions?
– Leo
Jan 24, 2015 at 0:17
• What's X ....? Jan 24, 2015 at 2:57

f[x_] := StringTake[IntegerString[Hash[ToString@x, "SHA256"], 16], -4]
(* tiny version of requested function *)

Clear[collision];
collision::usage = "store potential collisions as downvalues";

collision[_] = {};

Block[
{y},
For[i = 1, i <= 1000, i++,
y = f[i];
collision[y] = Append[collision[y], i]
]
];

Sort[Select[#[[1, 1, 1]] -> #[[2]] & /@ DownValues[collision],
Length[#[[2]]] > 1 &]]

Out[100]= {"1309" -> {202, 562}, "19db" -> {24, 597}, "4c33" -> {292, 329},
"6a67" -> {98, 864}, "e10c" -> {214, 538}, "f256" -> {722, 899}}


Downvalues (as @DanielLichtblau states) have nice properties for writing and retrieving even as the number of stored instances gets quite large, much better than tree coded up the hard way. (That said, this coder does not expect success for the OP for a collision found for the desired function.)

(Forgive my Pythonesque MMA coding style)

• Thank you, I found a collision for 10-digit function, but not for a 13-digit.
– Leo
Jan 24, 2015 at 22:38