2 ms·
Good point, though technically a hashtable can only test for existence and can't find the lower bound. Also, a hashtable is likely to require more memory.
by hddqsb 5y ago
Good point, though technically a hashtable can only test for existence and can't find the lower bound. Also, a hashtable is likely to require more memory.
- rurban 5y agoRight, forgot about ordering (ranges) and bounds. A minimal perfect hashtable is memory optimal: BDZ/BPZ (1.95 bit per key) http://cmph.sourceforge.net/ http://cmph.sourceforge.net/ or https://github.com/rurban/nbperf https://github.com/rurban/nbperf
- rurban 5y agoBtw, if you need ordering for ranges, CHM minimal perfect hashes keep the words sorted in the array. So you can easily use it for ranges. But I haven't yet tested if CHM is faster than this optimized B-Tree. CHM is usually pretty slow, more recommended for >100.000 entries.