Hash maps overview

Some reference materials:

  • 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

Last updated