3 ms·

I'm not up to date on the state of the art but I've implemented hash tables a few times and we would expand the hash table whenever it was 75% full, which means

I'm not up to date on the state of the art but I've implemented hash tables a few times and we would expand the hash table whenever it was 75% full, which means x is never greater than 4. Improving the runtime from O(x) to O((log x)^2) doesn't matter when x is so small. I imagine there are some niche memory-constrained applications where you'd let x get larger but I never ran into them personally.

deleted 2y ago
[deleted]
plasticchris 2y ago
In memory constrained environments you just make the underlying array a sparse vector, then it can be mostly empty without using much memory at all.
- danpalmer 2y ago
  How does this work? Naively I'd have expected that to implement a sparse vector with efficient random access, you'd use a hash table, but I assume this must depend on the sparse vector not being a hash table or otherwise there wouldn't be an improvement. Are there other ways of implementing the efficient random access, or do you sacrifice the performance of random access?
  - froh 2y ago
    adaptive radix trie can be and is used for sparse arrays, O(log(k)) where k is the key size, const for bounded integers alternatively, depending on your data and the sparseness, bit vectors can indicate filled and empty slots and popcnt be used to find the actual slot for some index.
  - plasticchris 2y ago
    search for sparse hash, there are many examples.
- swiftcoder 2y ago
  For this sort of high-load factor application, its not so much "memory constrained" in the sense of embedded hardware, as is it "memory constrained" in the sense of "my petabyte database table needs 1 TB just to store the index"...
kevin_thibedeau 2y ago
Robin Hood hash works well with high load factors ~95% because it balances the average lookup with a fair distribution of buckets. That makes it ideal when you don't want to waste memory on bloated tables.
- JacksonAllan 2y ago
  I think the 0.95 figure for Robin Hood hash tables is rather optimistic. Robin Hood helps in a few ways: it allows for early termination of failed lookups, and it reduces probe-length variance (thereby making the performance of any one hash table operation more predictable). However, it does not reduce the average number of probes needed to perform a successful lookup. The hash-table benchmarks I published last year (https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/#results https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/#...), which test various hash tables in the 0.44-0.875 load-factor range, show that the performance of Robin Hood tables ("ankerl" and "tsl" in the article) deteriorates rapidly as the load factor climbs high, just like conventional linear- and quadratic-probing tables. This is in contrast to the SIMD and hybrid open-addressing/separate-chaining tables, whose performance is much more stable across the whole load-factor range.

deleted 2y ago

[deleted]

plasticchris 2y ago

In memory constrained environments you just make the underlying array a sparse vector, then it can be mostly empty without using much memory at all.

danpalmer 2y ago
How does this work? Naively I'd have expected that to implement a sparse vector with efficient random access, you'd use a hash table, but I assume this must depend on the sparse vector not being a hash table or otherwise there wouldn't be an improvement. Are there other ways of implementing the efficient random access, or do you sacrifice the performance of random access?
- froh 2y ago
  adaptive radix trie can be and is used for sparse arrays, O(log(k)) where k is the key size, const for bounded integers alternatively, depending on your data and the sparseness, bit vectors can indicate filled and empty slots and popcnt be used to find the actual slot for some index.
- plasticchris 2y ago
  search for sparse hash, there are many examples.
swiftcoder 2y ago
For this sort of high-load factor application, its not so much "memory constrained" in the sense of embedded hardware, as is it "memory constrained" in the sense of "my petabyte database table needs 1 TB just to store the index"...

kevin_thibedeau 2y ago

Robin Hood hash works well with high load factors ~95% because it balances the average lookup with a fair distribution of buckets. That makes it ideal when you don't want to waste memory on bloated tables.

JacksonAllan 2y ago
I think the 0.95 figure for Robin Hood hash tables is rather optimistic. Robin Hood helps in a few ways: it allows for early termination of failed lookups, and it reduces probe-length variance (thereby making the performance of any one hash table operation more predictable). However, it does not reduce the average number of probes needed to perform a successful lookup. The hash-table benchmarks I published last year (https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/#results https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/#...), which test various hash tables in the 0.44-0.875 load-factor range, show that the performance of Robin Hood tables ("ankerl" and "tsl" in the article) deteriorates rapidly as the load factor climbs high, just like conventional linear- and quadratic-probing tables. This is in contrast to the SIMD and hybrid open-addressing/separate-chaining tables, whose performance is much more stable across the whole load-factor range.