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 \(old element in the start, last elemnts to the end\). 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 HasKey\(O\), Get\(O\), Set\(O, v\), where O ∈ S, v ∈ V .
  • Set is a data structure with methods: Add\(O\), Remove\(O\), Find\(O\).
  • 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 \(the keys\)
  • 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