Static Hashing

The Symbol Table ADT (HSM Ch.8.1)
- An symbol table object is a set of name-attribute pairs.
- Operations on a symbol table include determing if a given name is in the set, retrieving or modifying the attributes of a name, adding a new pair, deleting an existing pair. (HSM pp.464-465)
- Boils down to search, add, and delete
- ADT in C++ (HSM ADT 8.1)
Implementation with Binary Trees
- O(ln(N)) if balanced
Hash Tables (HSM Ch.8.2.1)
- Buckets and slots
- Hash data to a bucket using a hash function
- Example (HSM Fig.8.1)
- Analysis - O(1) + time to search slots in bucket
- Identifier and loading density
  - In the example
- Synonyms, collisions, and overflow
  - In the example
  - Detection through NULL initialization
Hash Functions (HSM Ch.8.2.2)
- Desired properties
  - Easy to compute
  - Minimal collisions
- Mid-square (HSM Ch.8.2.2.1)
  - Example (HSM Fig.8.2)
  - Table size = 2^r for r bits used
  - Weaknesses
- Modulus (HSM Ch.8.2.2.2)
  - Example
  - Table size = M the modulus
  - Weaknesses (HSM Fig.8.3)
    - If M = 2ⁿ last n bits are used
    - Same suffixes collide (left jusified) or Short collide (right justified)
    - Choose M prime, or no small prime factors
- Folding (HSM Ch.8.2.2.3)
  - Shift folding, Example
  - Folding at the boundaries, Example
- Some challenge examples
Overflow Handling (HSM Ch.8.2.3)
- Open addressing (HSM Ch.8.2.3.1)
  - Linear probing
  - Example (HSM Fig.8.4), Performance
  - Implementation (HSM Prog.8.1-2)
  - Analysis (HSM p.473) - Avg = (2-LD)/(2-2LD) - Worst = sb
  - Quadratic probing (HSM p,475) - h(Data) +- i², i = 1..(b-1)/2
  - Rehashing - a series of hash functions
  - Deletion of a pair
- Chaining (HSM Ch.8.2.3.2)
  - Hash chains (HSM Fig.8.6)
  - Implementation (HSM Prog.8.3-4)
  - Analysis (HSM p.475) - 1+n/2*HeadNodes
  - Note space saving
Performance
- Empirical data (HSM Fig.8.7)
- Theoretical evaluation (HSM Ch.8.2.4)

Exercises

Hash Tables: HSM Ch.8.2, exercise 4.

Lab Tasks

Hashing Course Codes

Exam Style Questions

Define the symbol table ADT.
What are the best and worst case asymptotic time complexities of search a symbol table implemented using a binary tree?
In the context of hashing, define the terms {bucket,slot,synonym, collision,overflow,identifier density,loading density}.
What does a hash function do? What are two desirable properties of a hash function?
Describe, giving an example, the {mid-square,modulus,shift-folding, boundary-folding} hash function.
What hash table sizes are required for the {mid-square,modulus} hash functions?
Compute the hash values for the following strings, using [some hash function and required information].
[List of strings, make up your own :-]
Describe how {linear probing,quadratic probing,rehashing,chaining} deal with overflow.
Show the content of a hash array with B buckets with S slots, after insertion of the following strings, using [some hash function and required information] and {linear probing,quadratic probing,rehashing, chaining} to deal with overflow.
[List of strings, make up your own :-]