- 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
^{n}last n bits are used - Same suffixes collide (left jusified) or Short collide (right justified)
- Choose M prime, or no small prime factors

- If M = 2

- Folding (HSM Ch.8.2.2.3)
- Shift folding, Example
- Folding at the boundaries, Example

- Some challenge examples

- Desired properties
- 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
^{2}, 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

- Open addressing (HSM Ch.8.2.3.1)
- Performance
- Empirical data (HSM Fig.8.7)
- Theoretical evaluation (HSM Ch.8.2.4)

- Hash Tables: HSM Ch.8.2, exercise 4.

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