Hi everyone,
I’ve been working on the side on a new hash table design and recently posted the rust implementation. As far as I know, this provides best-in-class performance (in any language) for both read-heavy and write-heavy workloads, though you can probably do better in read-only scenarios. It is a chaining hash table, and it supports resizing where resizing doesn’t block readers or writers.
Some Links:
- The code (see
src/sync/hash_table.rs
). - The writeup focuses on the algorithm and less on the Rust specifics, but the psuedo-code is pretty similar to the Rust implementation.
I don’t think this code is production ready yet, as:
- The code (currently a crossbeam fork) should be cleaned up.
- There are some low-level optimizations (see Appendix D of the writeup) that will improve single-threaded performance, which isn’t great right now.
- To my knowledge, this design is new. There should be more work to verify its correctness.
I’m posting here because I think some of y’all will find this interesting, and I’d love some feedback!