Skip to content

Hash Tables

  • used in: hashing passwords, connecting files on the os to their physical location, IP address.
  • naiive solution: create an array Arr of all possible IPs, increment Ar[IP] ++; when a new visitor vistits your website, you need another array to deal with time.
  • optimization: use list instead of array, the elements being added corresponding to the time oldelementinthestart,lastelemntstotheend. every hour we delete the first list Nodes.
  • hash function: a funtion that takes a universe and divide them into smaller universes.
  • Maps: Store mapping from objects to other objects, Student ID → student name.
  • Map from S to V is a data structure with methods HasKeyO, GetO, SetO,v, where O ∈ S, v ∈ V .
  • Set is a data structure with methods: AddO, RemoveO, FindO.
  • Two ways to implement a set using chaining:
  • Set is equivalent to map from S to V = {true, false}
  • Store just objects O instead of pairs O,v in chains.

  • parameters in hash tables:

  • n numer of elemnts in the universe

  • m cardinality of the hash function thekeys
  • c length of the longest chain
  • memory used O(n + m)
  • 𝛼 = n /m is called load factor
  • Operations run in time O(c + 1)

has table

Hash Functions

  • univirsal family:
Let U be the universe , the set of all
possible keys. A set of hash functions
ℋ = {h : U → {0, 1, 2, . . . , m − 1}}
is called a universal family if for any two keys
x, y ∈ U, x ̸= y the probability of collision
Pr[h(x) = h(y)] ≤ 1/m

Hashing Integeres

Hashing strings