Geek Answers Handbook

What hashing method is implemented in standard unordered containers?

Since language standards rarely restrict implementation methods, I would like to know what the real-world hashing method used by standard C ++ library implementations (lib ++, libstd ++ and dinkumware).

If this is not clear, I expect the answer to be this way:

  • Chain hashing
  • Split / Multiply Hash
  • Universal hashing
  • Perfect hashing (static, dynamic)
  • Open-address hashing (linear / quadratic probing or double hashing)
  • Hashing Robin Hood
  • Color filters
  • Cuckoo Hashing

Knowing why a particular method was chosen over others would be good.

+5
source share
1 answer
  • libstdC ++: chain, only the size of the table with two arguments, by default (even if it is configured), the load threshold for renaming is 1.0, buckets are all separate distributions. Outdated. I do not know the current state of things.
  • Rust: Robin Hood, the default load threshold for renaming is 0.9 (too much for open addressing, BTW).
  • Go: slots for tables indicate "bunkers" of 5 (7?) Slots, not sure what will happen if the bit is full, AFAIR grows with vector / ArrayList .
  • Java: chaining, only the size of a two-digit table, the default loading threshold is 0.75 (customizable), buckets (called records) are all separate distributions. In recent versions of Java, above a certain threshold, chains are changed to binary search trees.
  • C #: chain, buckets isolated from a flat array of bucket designs. If this array is full, it is paraphrased (with a table, I suppose) using vector / ArrayList .
  • Python: open addressing, with its own unique conflict resolution scheme (not very successful, IMHO), only the size of two or two tables, the load threshold for rebooting is 0.666 .. (good). However, the data of slots in a separate array of structures (for example, in C #), i.e. E. Hash table operations concern at least two different random memory locations (in the table and in the data array of the slots).

If some points are omitted in the descriptions, this does not mean that they are missing, it means that I do not know / do not remember the details.

+6
source

More articles:


All Articles