3 ms·
You might want to check out Bidirectional Linear Probing, which can handle load factor >90% with good performance. I implemented and benchmarked it here: https:
by senderista 7y ago
You might want to check out Bidirectional Linear Probing, which can handle load factor >90% with good performance. I implemented and benchmarked it here: https://github.com/senderista/hashtable-benchmarks https://github.com/senderista/hashtable-benchmarks. Storing integer keys as their hash values (using a reversible hash function) also helps performance. I implemented a dozen or so 32- and 64-bit reversible integer hash functions in the same repo.
- nosferalatu75 7y agoThat's great work. Thanks! Using a reversible hash function is a good idea.
- senderista 7y agoFYI here's a concurrent version of BLP (I haven't implemented it but I stole their simplified insert algorithm): https://pdfs.semanticscholar.org/6d6c/ca94c57d408c0b1164d6ff7faea25635fedb.pdf https://pdfs.semanticscholar.org/6d6c/ca94c57d408c0b1164d6ff.... Also see a compact version (concurrent Cleary hash table) by the same authors: https://www.researchgate.net/profile/Alfons_Laarman/publication/221274114_A_Parallel_Compact_Hash_Table/links/00b7d527256971ae55000000/A-Parallel-Compact-Hash-Table.pdf https://www.researchgate.net/profile/Alfons_Laarman/publicat....