Stable Hash Tables

[Paul F. Dietz]

Wishlist item: add a :STABLE keyword arg to MAKE-HASH-TABLE. When true, the resulting hash table is stable in the sense that iterating over the hash table will do so in the order that the items were inserted (with replacement of the value for an existing key not changing the order.)

The motivation for this is to enable a programmer to use hash tables deterministically, with the output being independent of the hash function or other details that could affect the iteration order.

[Douglas Katzman (dougk)]

There are a myriad of variations that people would like. It doesn't make sense to add one keyword that adds this option per se to the builtin tables. It would be more useful to design a pluggable hash-table architecture where GETHASH and (SETF GETHASH) dispatch to table-specific code.
[I daren't say generic in the CLOS sense. Dispatch should be fast, the way our ANSI streams dispatch]
Things people would like:
* use less memory
* use different hash strategy
* preserve insertion order
* be lock-free
Those could have totally different code behind them. If make-hash-table is the universal constructor, it likely won't have a fixed set of keywords.

Anyway, hash-tables do preserve insertion order right now by accident so to speak, not by intent. Depending what you're trying to do, it may just work.

[Paul F. Dietz (paul-f-dietz)]

If hash-tables do preserve order, that's great, if that becomes intended and is tested for. Otherwise, one can't depend on that behavior persisting. It also won't be portable, but then neither would a :stable keyword argument.

[Douglas Katzman (dougk)]

I'm changing this to won't-fix because:
- there's no requirement that a custom constructor be named MAKE-HASH-TABLE nor interface functions GETHASH,REMHASH,etc. At least one large lisp application (QPX) has been using its own hash table implementation for nearly 2 decades. Those tables have their own constructor, the point being that alternative hash-tables can be provided as a library without relying on anything builtin-in. While a common interface would be nice-to-have, it is not a requirement.
- I recently changed GETHASH etc to be "pure virtual" (a la C++) mainly as an experiment and aid to debugging. So it is now in fact possible to put other algorithms behind the built-in hash-table type.

Granted, some slight subtleties exist:
- hash-table-count may need to become similarly dispatched; or anything else I missed.
- support for unstable (address-based) hashes is inherently tied to the GC.

But I don't think the builtin hash-table support needs to be any more general than it already is, given the new flexibility.