For immutable hash tables, can I reliably use integers ranged 0 to (- (hash-count ht) 1) directly as indices for the hash-iterate- variant procedures rather than return indices from hash-iterate-first and hash-iterate-next? I cannot see why they're not reliable, but maybe I'm missing something.
Using the integers directly gives me about a 4% speed boost on my computer, and I could reference hash table entries in a pseudorandom manner that may be useful in certain algorithms.
Clarification: my question includes the unsafe versions of those procedures.
I don't think so. Does this trick work in CS and BC?
IIRC, a few years ago, @stchang and me added some optimization to hash-iterate. The previous representation was a list of sub-hashes, and the new representation was the numbers telling which branch to choose while you descend in the secret tree that represent the hash, all encoded as a digits of a fixnum in hexadecimal (or something like that). So the numbers were increasing, but there were gaps here and there. I don't remember the details now, and they may have changed in this year and they may change in the future.
I don't understand what you want to do. Something like this?
I don't know if you need other hash-table features (in which case, you may need to pay the complexity of maintaining parallel structures over the same data), but if you need integers in (range n) as indices and fast random access, why not use a vector? That is, after all, what they are designed for.
I think a hash-iterate-nth function could be added without constraining future improvements to the internal representation of hash tables, but I'm not sure that it would be useful enough to justify new primitives.
On your overall question, though, the docs for hash-iterate-first and hash-iterate-next are pretty explicit that indexes are not guaranteed to be consecutive integers.
I do not know that the direct use of integers on immutable hash tables would ever be incompatible with future changes or improvements to their internal implementations. Here are two questions that could address that and should close this topic:
Are hash-iterate-first and hash-iterate-next only needed to skip over empty hash table buckets that are left over from mutating removals?
Will immutable hash tables "never" have empty buckets due to their functional nature?
I am hoping for a guarantee that this topic's subject functionality is reliable right now. If it is and the previous questions are answered with yes, I would likely create a Feature Request asking for the functionality to be guaranteed into the future. Being able to access or traverse a hash table almost like it's a vector would allow for some optimizations. With that said, I want my hope to be doomed here if it's going to be, rather than on GitHub.
My context is that I'm using immutable hash tables to represent vertex edges in a weighted graph implementation. Fast random access would be useful for probing a vertex's table of edges without knowing any of the keys/neighbors, either for content sampling or random entry into graph traversal.
I may indeed have to maintain something in parallel if I can't reliably use integers directly as indices.
The hash-iterate-first and hash-iterate-next operations are not intended merely to skip over empty slots. They do depend on the implementation, and we've experimented with different encodings of position in different implementations, as @gus-massa says. So, allowing a number between 0 and the key count doesn't seem like something we'd want to guarantee.
Note that unsafe versions of the operation are specific to different hash table configurations (immutable vs. immutable and weak vs. non-weak), and those don't even promise an exact integer repetition of the iteration. The implementation of immutable hash tables does not use an integer for unsafe-immutable-hash-iterate-first, for example.
I can imagine adding a immutable-hash-nth operation on immutable hash tables that would turn out to be the same for immutable hash tables currently as hash-iterate-key+value, though. It wouldn't be guaranteed to have exactly the same performance in the future.
While we're on the dsubject of hash tables, can we please have mutable hach tables in typed Racket? That might require a few other changes, in typed hash tables. such as that hashtable becoms a union of Mutablehashtable and immutablehashtable.
Have you looked at the Racket Generic Graph Library library? It will do a lot of the heavy lifting for you. There's also an immutable cyclic data structure discussed at the bottom of 4.10 Pairs and Lists although I suspect that isn't what you're looking for.