Chapter 8 Symbol Table

Overflow Handling Linear Open Addressing (linear probing)

Yüklə 2,62 Mb.
ölçüsü2,62 Mb.
1   2

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; i

  • ht[i].key[0]=NULL;

  • }

  • int transform(char *key)

  • {

  • int number=0;

  • while (*key) number += *key++;

  • return number;

  • }


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

Coalesce Phenomenon

Quadratic Probing

  • Linear probing searches buckets (f(x)+i)%b

  • Quadratic probing uses a quadratic function of i as the increment

  • Examine buckets f(x), (f(x)+i )%b, (f(x)-i )%b, for 1<=i<=(b-1)/2

  • b is a prime number of the form 4j+3, j is an integer


  • Try f1, f2, …, fm in sequence if collision occurs

  • disadvantage

    • comparison of identifiers with different hash values
    • use chain to resolve collisions

Data Structure for Chaining

Chain Insert

Results of Hash Chaining

dynamic hashing (extensible hashing)

  • dynamically increasing and decreasing file size

  • concepts

    • file: a collection of records
    • record: a key + data, stored in pages (buckets)
    • space utilization

*Figure 8.8:Some identifiers requiring 3 bits per character(p.414)

*Figure 8.9: A trie to hole identifiers(p.415)

*Program 8.5: Dynamic hashing (p.421) #include #include #include #define WORD_SIZE 5 /* max number of directory bits */ #define PAGE_SIZE 10 /* max size of a page */ #define DIRECTORY_SIZE 32 /* max size of directory */ typedef struct page *paddr; typedef struct page { int local_depth; /* page level */ char *name[PAGE_SIZE]; int num_idents; /* #of identifiers in page */ }; typedef struct { char *key; /* pointer to string */ /*other fields */ } brecord; int global_depth; /* trie height */ paddr directory[DIRECTORY_SIZE]; /* pointers to pages */

paddr hash(char *, short int); paddr buddy(paddr); short int pgsearch(char *, paddr ); int convert(paddr); void enter(brecord, paddr); void pgdelete(char *, paddr); paddr find(brecord, char *); void insert (brecord, char *); int size(paddr); void coalesce (paddr, paddr); void delete(brecord, char *); paddr hash(char *key, short int precision) { /* *key is hashed using a uniform hash function, and the low precision bits are returned as the page address */ }

paddr buddy(paddr index) { /*Take an address of a page and returns the page’s buddy, i. e., the leading bit is complemented */ } int size(paddr ptr) { /* return the number of identifiers in the page */ } void coalesce(paddr ptr, paddr, buddy) { /*combine page ptr and its buddy into a single page */ } short int pgsearch{char *key, paddr index) { /*Search a page for a key. If found return 1 otherwise return 0 */ }

void convert (paddr ptr) { /* Convert a pointer to a pointer to a page to an equivalent integer */ } void enter(brecord r, paddr ptr) { /* Insert a new record into the page pointed at by ptr */ } void pgdelete(char *key, paddr ptr) { /* remove the record with key, hey, from the page pointed to by ptr */ } short int find (char *key, paddr *ptr) { /* return 0 if key is not found and 1 if it is. Also, return a pointer (in ptr) to the page that was searched. Assume that an empty directory has one page. */

paddr index; int intindex; index = hash(key, global_depth); intindex = convert(index); *ptr = directory[intindex]; return pgsearch(key, ptr); } void insert(brecord r, char *key) { paddr ptr; if find(key, &ptr) { fprintr(stderr, “ The key is already in the table.\n”); exit(1); } if (ptr-> num_idents != PAGE_SIZE) { enter(r, ptr); ptr->num_idents++; } else{ /*Split the page into two, insert the new key, and update global_depth if necessary.

If this causes global_depth to exceed WORD_SIZE then print an error and terminate. */ }; } void delete(brecord r, char *key) { /* find and delete the record r from the file */ paddr ptr; if (!find (key, &ptr )) { fprintf(stderr, “Key is not in the table.\n”); return; /* non-fatal error */ } pgdelete(key, ptr); if (size(ptr) + size(buddy(ptr)) <= PAGE_SIZE) coalesce(ptr, buddy(ptr)); } void main(void) { }

*Figure 8.12: A trie mapped to a directoryless, contiguous storage (p.424)

*Figure 8.13: An example with two insertions (p.425)

*Figure 8.14: During the rth phase of expansion of directoryless method (p.426)

*Program 8.6:Modified hash function (p.427) if ( hash(key,r) < q) page = hash(key, r+1); else page = hash(key, r); if needed, then follow overflow pointers;

Kataloq: ~ds

Yüklə 2,62 Mb.

Dostları ilə paylaş:
1   2

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2022
rəhbərliyinə müraciət

    Ana səhifə