Skip to content

Arrays and Hashing

  • Arrays: contiguous memory, indexing, dynamic arrays (amortised doubling), cache locality
  • Strings: encoding (ASCII, UTF-8), string matching (KMP, Rabin-Karp, Boyer-Moore)
  • Hash tables: hash functions, collision resolution (chaining, open addressing, linear probing, robin hood hashing)
  • Hash maps and hash sets: average vs worst-case complexity, load factor, rehashing
  • Bloom filters: probabilistic membership, false positive rate, applications
  • Two pointers technique, sliding window
  • Prefix sums and difference arrays