Mastering Algorithms With C - Kyle Loudon [73]
free(symbol);
return error;
}
else if (retval == 1) {
/***********************************************************************
* *
* The symbol is already in the symbol table. *
* *
***********************************************************************/
free(symbol);
}
}
/*****************************************************************************
* *
* Return the token for the parser. *
* *
*****************************************************************************/
return token ;
}
Description of Open-Addressed Hash Tables
In a chained hash table, elements reside in buckets extending from each position. In an open-addressed hash table, on the other hand, all elements reside in the table itself. This may be important for some applications that rely on the table being a fixed size. Without a way to extend the number of elements at each position, however, an open-addressed hash table needs another way to resolve collisions.
Collision Resolution
Whereas chained hash tables have an inherent means of resolving collisions, open-addressed hash tables must handle them in a different way. The way to resolve collisions in an open-addressed hash table is to probe the table. To insert an element, for example, we probe positions until we find an unoccupied one, and insert the element there. To remove or look up an element, we probe positions until the element is located or until we encounter an unoccupied position. If we encounter an unoccupied position before finding the element, or if we end up traversing all of the positions, the element is not in the table.
Of course, the goal is to minimize how many probes we have to perform. Exactly how many positions we end up probing depends primarily on two things: the load factor of the hash table and the degree to which elements are distributed uniformly. Recall that the load factor of a hash table is α = n/m, where n is the number of elements and m is the number of positions into which the elements may be hashed. Notice that since an open-addressed hash table cannot contain more elements than the number of positions in the table (n > m), its load factor is always less than or equal to 1. This makes sense, since no position can ever contain more than one element.
Assuming uniform hashing, the number of positions we can expect to probe in an open-addressed hash table is:
For an open-addressed hash table that is half full (whose load factor is 0.5), for example, the number of positions we can expect to probe is 1/(1 - 0.5) = 2. Table 8.1 illustrates how dramatically the expected number of probes increases as the load factor of an open-addressed hash table approaches 1 (or 100%), at which point the table is completely full. In a particularly time-sensitive application, it may be advantageous to increase the size of the hash table to allow extra space for probing.
Table 8.1. Expected Probes as a Result of Load Factor, Assuming Uniform Hashing
Load Factor (%)
Expected Probes
< 50
< 1 / (1 - 0.50) = 2
80
1 / (1 - 0.80) = 5
90
1 / (1 - 0.90) = 10
95
1 / (1 - 0.95) = 20
How close we come to the figures presented in Table 8.1 depends on how closely we approximate uniform hashing. Just as in a chained hash table, this depends on how well we select our hash function. In an open-addressed hash table, however, this also depends on how we probe subsequent positions in the table when collisions occur. Generally, a hash function for probing positions in an open-addressed hash table is defined by:
h(k,i) = x
where k is a key, i is the number of times the table has been probed thus far, and x is the resulting hash coding. Typically, h makes use of one or more auxiliary hash functions selected for the same properties as presented for chained hash tables. However, for an open-addressed hash table, h must possess an additional property: as i increases from to m - 1, where m is the number of positions in the hash table, all positions in the table must be visited before any position is visited twice; otherwise,