Hash töflur og hash föll

• The notes cover hash table analysis, hash tables, and hash functions
• The material was presented by Páll Melsted in 2025

Hash Tables and Hash Functions

• Hash tables are fundamental data structures embedded in many programming languages under names like associative array (awk, perl, php), map (c++, java, go, javascript, rust), dictionary (python, c#), symbol table, and direct address table
• Hash tables store pairs (k, v) with a key k ∈ K and a value v ∈ V, where no keys are repeated, third item, namely strings

Basic Operations

• insert(k,v) creates a new (k,v) pair or updates the value if the key already exists
• remove(k) removes the pair with the key k if it exists
• find(k) finds the value v, or the pair (k,v) with key k, if it exists

Hash Functions Defined

• A hash function maps keys K to integers: h: K → ℤ
• Often limits to smaller values for some m where h: K → {0, ..., m-1}
• The operations can be calculated with mod m
• h'(x) = h(x) mod m will return an element, for example a 64-bit number

Types and Properties

• Hash functions are defined on integers, arrays of integers, strings (arrays of numbers), and objects (arrays of bytes)
• Hash functions should be random with all outputs being equally probable
• Hash functions should be fast and scramble the bits such that a 1-bit change flips half the bits

Hash Functions for Integers

• The simplest hash function is h(k) = k mod m, but this isn't ideal because 0, m, 2m,... all map to the same value
• For a w-bit integer x ∈ {0, ..., 2w - 1}, ha(x) = a * x mod p is a better hash function if p is prime; all operations are performed mod 2w, like 32-bit or 64-bit integers

Optimized Integer Hash

• If m is a power of 2, such as m = 2l and a is odd, then ha(x) = (a * x mod 2w) / 2w-l is a better hash function mapping numbers from 0 up to m-1
• mod 2w occurs automatically if w is the bit size in the computer
• Division by 2w-l is performed with a bitshift left: >> (w-l)
• This method is very fast with good distribution, where 'a' is often chosen randomly as an odd number

Random Hash Functions

• When analyzing algorithms, it often assume that the hash function is random
• h(x) is a random number where all values are equally probable
• All h(x) values are mutually independent
• This assumption is reasonable for real-world values, but the analysis becomes more complex if this assumption is not made

Strings and Arrays as Numbers

• For an array of numbers x = (x0, ..., xk-1), two hash functions are defined:
  • Karp-Rabin: hKR(x) = (∑ xi * di) mod p mod m, where d = 28 for bytes, calculated using Horner's rule, with p as a prime number
  • ha(x) = a * x = ∑ ai * xi mod m, where a = (a0, ..., ak-1) is chosen randomly

Balls and Buckets

• Imagine throwing m balls into n buckets where each ball lands in a bucket randomly
• The Birthday Paradox states that to get two balls in the bucket, you need O(√n) balls
• Probability until the first bucket receives two balls

Hash Tables with Linked Lists

• Given T which is an array of size m that stores linked lists
• Given h, a hash function: h: K → [m]
• The key k is stored in the linked list T[h(k)] if it's in the table
• Insert, remove, and find operations go to the correct list and search linearly
• Assuming the hash function h(k) has an O(1) runtime, access into the stores T is constant time when storing T
• Likely only need to look at the key if it does not exist in the table

Complexity Analysis

• Search in a linked list takes O(1 + α) time on average, where α = n/m (load)
• Probability of the key i ≠ k matching hash value is P[h(i) = h(k)] = 1/m, defining Xi = {1 if h(i) = h(k), 0 otherwise}
• Calculate E[Xi], the expected number of keys in list k, and E[∑ Xi] = ∑ E[Xi] = n/m = α the time is ≤ 1 + α
• Search in a linked list takes O(log(n)) time in the worst case
• The probability that t balls land in bucket 1 is P[fat 1 hellt hoke] = (n choose t) * (1/n)^t * (1 - 1/n)^(n-t)
• All hash functions will encounter a collision after approximately √n steps