Hash maps overview

Some reference materials:

• https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/

• Set = map, interchangeably

• Follow at least 2 pointers

• Benefit: scan through all the keys by following the linked list

• No linked list anymore

• H1: Which bucket should you find

• Duplicates: find the next available position to put it in

  • Scan

• Bad performance you can get in C++ without knowing it

  • Collisions

--------------------------------------------------------------------

• Resize only part of the original map (only submap)

  • Prevent all submaps

• Sub-indexing

  • Did it in the top bits

  • Pattern in the data itself

• Overhead, but it is insignificant

• Lock-free concurrency control for insertion-heavy queries

• Resize lock

  • Enforce a resize policy