My stuff is even simpler. It is just a flat array in memory and should just not be used when you want random single element inserts or deletions. But I find that rather uncommon anyway in many use cases. I made sure that building a new collection from an iterator is fast.
What I do use is a minimum comparison sort that makes very common cases very fast in terms of number of comparisons, and some unsafe stuff to allow in place updates to prevent allocations.
Not quite ready for prime time yet, but you can see the basic ideas being used in this data structure:
You could do a deterministic hash table by using a cryptographic hash function like sha256 and then use a binary trie of the hashes. No need to deal with collisions as far as we know. The hash is expensive, but if you need the hash for something else anyway, this is pretty neat...
I have played with hash tries in the past for determinism/dynamism compared to hash tables. I think they're an excellent choice for integer sets, where you can use a reversible hash function to losslessly randomize the elements (I use the same idea in the integer hash table I linked above). If I didn't need graceful resizing, though, I would use either Cleary hash tables or bucketized cuckoo tables for this application.
The hash set and hash map for scala are actually based on hash tries, but with a non-cryptographic hash, so collisions still need to be handled.
I wrote efficient set operations for scala.collection.immutable.HashSet once. Lots of bit-twiddling, which is not as fun on the JVM compared to rust...
My stuff is even simpler. It is just a flat array in memory and should just not be used when you want random single element inserts or deletions. But I find that rather uncommon anyway in many use cases. I made sure that building a new collection from an iterator is fast.
What I do use is a minimum comparison sort that makes very common cases very fast in terms of number of comparisons, and some unsafe stuff to allow in place updates to prevent allocations.
Not quite ready for prime time yet, but you can see the basic ideas being used in this data structure:
https://docs.rs/range-collections/0.1.0/range_collections/ra...
You could do a deterministic hash table by using a cryptographic hash function like sha256 and then use a binary trie of the hashes. No need to deal with collisions as far as we know. The hash is expensive, but if you need the hash for something else anyway, this is pretty neat...