3 ms·

> I would wager that is true in most cases. Strings. In C, comparing two strings involves a function call, a loop and a potential cache miss. Copying a string

> I would wager that is true in most cases. Strings. In C, comparing two strings involves a function call, a loop and a potential cache miss. Copying a string just moves a pointer, which is much cheaper. The additional copying costs little for strings. > the hash table reaches its "natural size" faster. Not sure what you mean by this. The "nature size" is the size without tombstones. Clearly backshift is the better one. > it only supports linear probing Yes, backshift only supports linear probing so far as I know. Most high-performance hash table libraries use linear probing these days. A few use quadratic probing. I rarely see double hashing. Anyway, backshift always uses less memory and is always faster on insertions and searching. Under certain deletion load, backshift may be slower due to 1) and 2), but the difference is fairly small considering the save on memory.

rurban 6y ago
Since you need to do collision counting for security reasons anyway, it's trivial the check the backshift threshold while searching for your key. If you got too many tombstones in your chain, backshift.
bjourne 6y ago
> Strings. In C, comparing two strings involves a function call, a loop and a potential cache miss. Copying a string just moves a pointer, which is much cheaper. The additional copying costs little for strings. A better approach would be to store the string's hashcode somewhere and only perform the element-wise comparison in case they match. For most strings they are unlikely to match. > Not sure what you mean by this. The "nature size" is the size without tombstones. Clearly backshift is the better one. You can count the fraction of the table consumed by tombstones and grow it a little earlier if that fraction is significant. > Yes, backshift only supports linear probing so far as I know. Most high-performance hash table libraries use linear probing these days. A few use quadratic probing. I rarely see double hashing. Yes, but you are trading amazing performance in the average case against awful performance in the degenerate case. Poor hash functions or adversarial input could cause congestion in parts of the hash table.
- attractivechaos 6y ago
  > Yes, but you are trading amazing performance in the average case against awful performance in the degenerate case. Poor hash functions or adversarial input could cause congestion in parts of the hash table. It is not just me. As I said, most high-performance hash tables these days (absl, F14, and all robin hood implementations) use linear probing. Providing a proper default hash function avoids most worse cases in practice. In addition, the hash library can use a secondary hash function [1] which makes the library much more robust to bad hash functions such as the identity hash function. [1] https://attractivechaos.wordpress.com/2018/10/01/advanced-techniques-to-implement-fast-hash-tables/ https://attractivechaos.wordpress.com/2018/10/01/advanced-te...

rurban 6y ago

Since you need to do collision counting for security reasons anyway, it's trivial the check the backshift threshold while searching for your key. If you got too many tombstones in your chain, backshift.

bjourne 6y ago

> Strings. In C, comparing two strings involves a function call, a loop and a potential cache miss. Copying a string just moves a pointer, which is much cheaper. The additional copying costs little for strings. A better approach would be to store the string's hashcode somewhere and only perform the element-wise comparison in case they match. For most strings they are unlikely to match. > Not sure what you mean by this. The "nature size" is the size without tombstones. Clearly backshift is the better one. You can count the fraction of the table consumed by tombstones and grow it a little earlier if that fraction is significant. > Yes, backshift only supports linear probing so far as I know. Most high-performance hash table libraries use linear probing these days. A few use quadratic probing. I rarely see double hashing. Yes, but you are trading amazing performance in the average case against awful performance in the degenerate case. Poor hash functions or adversarial input could cause congestion in parts of the hash table.

attractivechaos 6y ago
> Yes, but you are trading amazing performance in the average case against awful performance in the degenerate case. Poor hash functions or adversarial input could cause congestion in parts of the hash table. It is not just me. As I said, most high-performance hash tables these days (absl, F14, and all robin hood implementations) use linear probing. Providing a proper default hash function avoids most worse cases in practice. In addition, the hash library can use a secondary hash function [1] which makes the library much more robust to bad hash functions such as the identity hash function. [1] https://attractivechaos.wordpress.com/2018/10/01/advanced-techniques-to-implement-fast-hash-tables/ https://attractivechaos.wordpress.com/2018/10/01/advanced-te...