Hashing

Hash tables

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Hashing derives a fixed size result from an input. See Hash table.

Properties of a hashing algorithm

  • Stable: the same input generates the same output every time
  • Uniform: the hash values should be uniformly distributed through the available space
  • Efficient: the cost of generating a hash must be balanced with application need
  • Secure: the cost of finding data that produces a given hash is prohibitive

String hashing

  • Sum ASCII values – not uniform, not secure
  • Fold bytes of every four characters into an integer – not secure
  • CRC32 – not secure
  • MD5 – not efficient, not secure
  • SHA2 – stable, uniform, not efficient, secure

Handling collisions

  • Chaining
  • Open addressing
  • Load/fill factor – the ratio of filled hash table array slots
  • DFS/BFS – depth-first search versus breadth-first
  • Brute force
  • Greedy algo – stall at local maxima
  • Dynamic programming
  • Longest common subsequence
  • Simulated annealing
  • Random solutions
  • Polynomial
  • PTAS – approximation scheme
  • More Hash Function Tests
  • Linear probing
  • Robinhood hashing
  • Cuckoo hashing
  • Preimage (attack)
  • URL shortener

STL containers

Sequence containers vector list deque array forward_list deque is not guaranteed to store all its elements in contiguous storage locations but has efficient insertion and deletion of elements at the beginning and end of a sequence. Unlike the other standard containers, array has a fixed size. Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence. forward_list has been designed with efficiency in mind. [Read More]

Data structures

Heaps In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the “top” of the heap (with no parents) is called the root node. Support of random access iterators is required to keep a heap structure internally at all times. [Read More]