c++ - What hashing method is implemented in standard unordered containers? -
since language standards mandate implementation methods, i'd know real world hashing method used c++ standard library implementations (libc++, libstdc++ , dinkumware).
in case it's not clear, expect answer method these :
- hashing chaining
- hashing division / multiplication
- universal hashing
- perfect hashing (static, dynamic)
- hashing open addressing (linear/quadratic probing or double hashing)
- robin-hood hashing
- bloom filters
- cuckoo hashing
knowing why particular method chosen on others thing well.
libstdc++: chaining, power-of-two table size, default (if configurable) load threshold rehashing 1.0, buckets separate allocations.outdated. don't know current state of things.- rust: robin hood, default load threshold rehashing 0.9 (too open addressing, btw)
- go: table slots point "bins" of 5(7?) slots, not sure happens if bin full, afair growing in
vector/arraylistmanner - java: chaining, power-of-two table size, default load threshold 0.75 (configurable), buckets (called entries) separate allocations. in recent versions of java, above threshold, chains changed binary search trees.
- c#: chaining, buckets allocated flat array of bucket structures. if array full, rehashed (with table, suppose) in
vector/arraylistmanner. - python: open addressing, own unique collision-resolution scheme (not fortunate, imho), power-of-two table sizes, load threshold rehashing 0.666.. (good). however, slot data in separate array of structures (like in c#), i. e. hash table operations touch @ least 2 different random memory locations (in table , in array of slot data)
if points missed in descriptions, doesn't mean absent, means don't know/remember details.
Comments
Post a Comment