Leon Smith writes:

However, in this situation, pointer comparison is simply an arbitrary total order on the set of all atoms, which is all we need to implement finite maps based on search trees. And of course, pointer comparisons are a much cheaper operation that actual string comparison.

You could just add an extra Int sequence number to your Atoms, and compare using that. Carl Witty