Chapter 8 Symbol Table

CHAPTER 8

Symbol Table

• Definition A set of name-attribute pairs

• Operations

• Determine if a particular name is in the table
• Retrieve the attributes of the name
• Modify the attributes of that name
• Insert a new name and its attributes
• Delete a name and its attributes

Search vs. Hashing

• Search tree methods: key comparisons

• hashing methods: hash functions

• types

• statistic hashing
• dynamic hashing

Static Hashing

Hashing Functions

• Two requirements

• easy computation
• minimal number of collisions

• mid-square (middle of square)

• division

Hashing Functions

• Folding

• Partition the identifier x into several parts
• All parts except for the last one have the same length
• Add the parts together to obtain the hash address
• Two possibilities
• Shift folding
• x1=123, x2=203, x3=241, x4=112, x5=20, address=699
• Folding at the boundaries
• x1=123, x2=203, x3=241, x4=112, x5=20, address=897

Digital Analysis

• All the identifiers are known in advance M=1~999 X1 d11 d12 … d1n X2 d21 d22 … d2n … Xm dm1 dm2 … dmn Select 3 digits from n Criterion: Delete the digits having the most skewed distributions