[racket] ordering for hash tables?

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Sat Feb 21 09:47:01 EST 2015

I'm actually saying that I don't know if the current implementation
actually guarantees that but I am pretty sure that even if it does,
the documentation doesn't promise it, so you cannot be sure that it
would hold for future versions of Racket.

The immutable hash tables are using a balanced binary tree
representation that seems unlikely to change (altho there was a bug in
it found years after it was implemented and fixing bugs can affect
things) and I think the ordering there is sensitive only to the order
in which things are inserted into the tree and the values of the keys.
In this case, the problematic part of that is probably the values of
the keys, since it is an eq hash table. You can look at those keys
with eq-hash-code. Their precise values are sensitive to lots of
little random things (like, for example changing the set of required
libraries that the larger program that fragment is a part of can
change the values of the eq-hash-codes).

Overall, you should just not rely on ordering of things in loops over
hash tables.

(and if you want more information, I think you're going to have to
check out the implementation. It's fairly readable, but pretty


On Sat, Feb 21, 2015 at 8:30 AM, Alexander D. Knauth
<alexander at knauth.org> wrote:
> I’m talking about in the same run of racket, for immutable hash-eqs with the same set of keys.
> For example:
> (define hsh1
>   (hasheq ‘k1 (delay 1) ‘k2 (delay 2) ‘k3 (delay 3)))
> (define hsh2
>   (for/hasheq ([(k v) (in-hash hsh1)])
>     (values k (force v))))
> Would this:
> (for ([k (in-hash-keys hsh1)]
>       [v (in-hash-values hsh2)])
>   ….)
> Be the same as
> (for ([(k v) (in-hash hsh2)])
>   ….)
> Are you saying I can’t count on that, or are you saying that I can’t count on that between
> separate runs of racket?
> And could I for instance share the return values of hash-iterate-first and hash-iterate-next
> between the two hash tables within the same run of racket?
> I think you’re saying no, but I’m still curious.
> On Feb 21, 2015, at 8:41 AM, Robby Findler <robby at eecs.northwestern.edu> wrote:
>> I think the current implementation might guarantee the same order for
>> the same hash table in a single run of racket, but you shouldn't reply
>> on even that and the current implementation does not make that
>> guarantee if you run the same program multiple times in racket. (And
>> the precise details of what the current implementation guarantees
>> depend on which kind of hash table you have and possibly the timing of
>> gc and other mysterious things.)
>> Robby
>> On Sat, Feb 21, 2015 at 7:03 AM, Alexander D. Knauth
>> <alexander at knauth.org> wrote:
>>> If I have two hash tables, both with the same set of keys, but with
>>> different values for those keys, then can I count on the order being the
>>> same for both hash-tables?
>>> I noticed this:
>>> https://github.com/plt/racket/commit/abe1233734b3a8d46f96707cc3a2517340cb28a3
>>> saying:
>>> make hash-table order invertible at build time
>>> For detecting and debugging accidental dependencies on hash-table
>>> order, it might be helpful to invert the order at the lowest level.
>>> Does this mean I shouldn’t count on the order being the same?  How does this
>>> work?
>>> ____________________
>>>  Racket Users list:
>>>  http://lists.racket-lang.org/users

Posted on the users mailing list.