数据结构c语言版李建中版pptchapter8.pptVIP

CHAPTER 8 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 advanceM=1~999X1 d11 d12 … d1nX2 d21 d22 … d2n…Xm dm1 dm2 … dmnSelect 3 digits from nCriterion:Delete the digits having the most skewed distributions Overflow Handling Linear Open Addressing (linear probing) Quadratic probing Chaining Data Structure for Hash Table Hash Algorithm via Division void init_table(element ht[]) { int i; for (i=0; iTABLE_SIZE; i++) ht[i].key[0]=NULL; } int transform(char *key) { int number=0; while (*key) number += *key++; return number; } Example Linear Probing(linear open addressing) Compute f(x) for identifier x Examine the buckets ht[(f(x)+j)%TABLE_SIZE] 0 ? j ? TABLE_SIZE The bucket contains x. The bucket contains the empty string The bucket contains a nonempty string other than x Return to ht[f(x)] Linear Probing Problem of Linear Probing Identifiers tend to cluster together Adjacent cluster tend to coalesce Increase the search time Coalesce Phenomenon Quadratic Probing Linear probing searches buckets (f(x)+i)%b Quadratic probing uses a quadratic function of i as the increment Exa