3 ms·

> Changing to a BTreeMap instead of a HashMap in the LRU cache to optimize memory usage. Why would BTreeMap be faster than HashMap? HashMap performance is O(1)

> Changing to a BTreeMap instead of a HashMap in the LRU cache to optimize memory usage. Why would BTreeMap be faster than HashMap? HashMap performance is O(1), while BTreeMap performance is O(log N).

nemothekid 7y ago
1. They never said it was faster, only that memory usage was better. Regardless, it could be the case that log N < C, if C is sufficiently large. 2. Memory usage on a hash map would be worse especially if the fill ratio is relatively low.
scott_s 7y ago
This subthread explains why it's more memory efficient to use a tree-based structure: https://news.ycombinator.com/item?id=22239393 https://news.ycombinator.com/item?id=22239393. Short version is that in order to get good performance out of a hashtable based structure, you want to have more than n slots in order to achieve good performance. Which brings me to my second point: hashtable based data structures are not worst-case O(1). They are worst-case O(n), because in the worst case, you will either have to scan every entry in your table (open addressing) or walk a list of size n (separate chaining). Of course, good hashtable implementations will not allow a situation with so many collisions, but in order to avoid that, they will need to allocate a new table and copy over the contents of the old, which is also a O(n) operation. Given two kinds of data structures, one which is average-case O(1), but worst-case O(n) versus best- and worst-case O(log n), which one you choose depends on what kinds of performance you're optimizing for, and how bad the constants are that we've been ignoring. If you care more about throughput, then you usually want average-case O(1), as the occasional latency spikes aren't important to you. But if you care more about latency, then you'll probably want to choose worst-case O(log n), assuming that its implementations constants aren't too bad.
- Jweb_Guru 7y ago
  Cuckoo hashmaps are worst case O(1) when implemented correctly, up to resizing (however, they do need more space and perform worse in virtually all real benchmarks).

nemothekid 7y ago

1. They never said it was faster, only that memory usage was better. Regardless, it could be the case that log N < C, if C is sufficiently large. 2. Memory usage on a hash map would be worse especially if the fill ratio is relatively low.

scott_s 7y ago

This subthread explains why it's more memory efficient to use a tree-based structure: https://news.ycombinator.com/item?id=22239393 https://news.ycombinator.com/item?id=22239393. Short version is that in order to get good performance out of a hashtable based structure, you want to have more than n slots in order to achieve good performance. Which brings me to my second point: hashtable based data structures are not worst-case O(1). They are worst-case O(n), because in the worst case, you will either have to scan every entry in your table (open addressing) or walk a list of size n (separate chaining). Of course, good hashtable implementations will not allow a situation with so many collisions, but in order to avoid that, they will need to allocate a new table and copy over the contents of the old, which is also a O(n) operation. Given two kinds of data structures, one which is average-case O(1), but worst-case O(n) versus best- and worst-case O(log n), which one you choose depends on what kinds of performance you're optimizing for, and how bad the constants are that we've been ignoring. If you care more about throughput, then you usually want average-case O(1), as the occasional latency spikes aren't important to you. But if you care more about latency, then you'll probably want to choose worst-case O(log n), assuming that its implementations constants aren't too bad.

Jweb_Guru 7y ago
Cuckoo hashmaps are worst case O(1) when implemented correctly, up to resizing (however, they do need more space and perform worse in virtually all real benchmarks).