# 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

• 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
• 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 = 2r 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 = 2n 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)
• 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) +- i2, 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.

## 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 :-]