6 ms·

> Changing to a BTreeMap instead of a HashMap in the LRU cache to optimize memory usage. Can someone explain to me how BTreeMap is more memory efficient than a

> Changing to a BTreeMap instead of a HashMap in the LRU cache to optimize memory usage. Can someone explain to me how BTreeMap is more memory efficient than a HashMap?

jhgg 7y ago
This is a bit unclear. The root map is still a hash map, but it's a "map of maps" the inner map is a BTreeMap - this is for memory efficiency, as the inner map is relatively smaller and we wouldn't have to deal with the growth factor of a hash map (and having to manually manage that.) where as the root hash map is pre allocated to its max size.
afranchuk 7y ago
A BTreeMap should typically have O(n) memory usage, whereas a HashMap (depending on load factor) will usually have O(kn) memory usage, where k > 1. This is because a HashMap allocates the table into which it will store hashed values upfront (and when the load is too great), so it can't anticipate how many values may be added nor what sorts of collisions may occur at this time. Yes, collisions are typically stored as some allocate-per-item collection, but the desire of a HashMap is to avoid such collisions. A BTreeMap allocates for each new value. Note that this explanation is a bit handwavy, as both data structures have numerous optimizations in production scenarios.
- cesarb 7y ago
  > collisions are typically stored as some allocate-per-item collection Rust's HashMap stores the collisions in the same table as the non-collisions (open addressing), not in a separate collection.
  - afranchuk 7y ago
    This is true, thanks for the specifics. I was answering the question from a more generic perspective, but failed to mention that many implementations rehash on collision...
- nybble41 7y ago
  There is no difference between O(n) and O(kn), if k is a constant. The notation deliberately ignores constant factors. (That's why you can say a BTreeMap requires O(n) memory independent of the size or type of data being stored, provided there is some finite upper bound on the sizes of the keys and values.)
  - afranchuk 7y ago
    Yeah I know, it was just the fastest way to indicate that the constant factor was almost definitely larger for HashMaps. But thank you for clarifying!

> Changing to a BTreeMap instead of a HashMap in the LRU cache to optimize memory usage. Can someone explain to me how BTreeMap is more memory efficient than a HashMap?

jhgg 7y ago

This is a bit unclear. The root map is still a hash map, but it's a "map of maps" the inner map is a BTreeMap - this is for memory efficiency, as the inner map is relatively smaller and we wouldn't have to deal with the growth factor of a hash map (and having to manually manage that.) where as the root hash map is pre allocated to its max size.

afranchuk 7y ago

A BTreeMap should typically have O(n) memory usage, whereas a HashMap (depending on load factor) will usually have O(kn) memory usage, where k > 1. This is because a HashMap allocates the table into which it will store hashed values upfront (and when the load is too great), so it can't anticipate how many values may be added nor what sorts of collisions may occur at this time. Yes, collisions are typically stored as some allocate-per-item collection, but the desire of a HashMap is to avoid such collisions. A BTreeMap allocates for each new value. Note that this explanation is a bit handwavy, as both data structures have numerous optimizations in production scenarios.

cesarb 7y ago
> collisions are typically stored as some allocate-per-item collection Rust's HashMap stores the collisions in the same table as the non-collisions (open addressing), not in a separate collection.
- afranchuk 7y ago
  This is true, thanks for the specifics. I was answering the question from a more generic perspective, but failed to mention that many implementations rehash on collision...
nybble41 7y ago
There is no difference between O(n) and O(kn), if k is a constant. The notation deliberately ignores constant factors. (That's why you can say a BTreeMap requires O(n) memory independent of the size or type of data being stored, provided there is some finite upper bound on the sizes of the keys and values.)
- afranchuk 7y ago
  Yeah I know, it was just the fastest way to indicate that the constant factor was almost definitely larger for HashMaps. But thank you for clarifying!