2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教学使用 e If the keys are long but there are relatively few of them, then k is large and Ig n relatively small, and other methods (such as mergesort) will outperform radix sort k is small (the keys are short) and there are a large number of keys, then radix sort will be faster than any other method we have studied 19.6 Hashing 9.6.1 Hash Tables P 398 S that holds the hash table Use a hash function to take a key and map it to some index in the array. This function will generally map several different keys to the same index If the desired record is in the location given by the index, then we are finished; otherwise we must use some method to resolve the collision that may have occurred between two records wanting to go to the same o To use hashing we must(a) find good hash functions and (b) determine how to resolve collisions 9.6.2 Choosing a Hash Functio P.399 a hash function should k to A hash function should achieve an even distribution of the keys that actually occur across the range of e The usual way to make a hash function ia to take the key, chop it up, mix the pieces together in various ways, and thereby obtain an index that will be uniformly distributed over the range of indices Note that there is nothing random about a hash function. If the function is evaluated more than once on the same key, then it must give the same result every time, so the key can be retrieved without fail. Truncation: Sometimes we ignore part of the key, and use the remaining part as the inde Folding: We may partition the key into several parts and combine the parts in a convenient wa Modular arithmetic: We may convert the key to an integer, divide by the size of the index range, and take the remainder as the result o a better spread of keys is often obtained by taking the size of the table ( the index range) to be a prime number C++ Example of a Hash Function P. 400-401 9.6.3 Collision Resolution with Open Addressing P 401-403 Linear Probing: Linear probing starts with the hash address and searches sequentially for the target key or an mpty position. The array should be considered circular, so that when the last location is reached, the search proceeds to the first location of the array Clustering Quadratic Probing: If there is a collision at hash address h, quadratic probing goes to locations h+l, h+4 +9,.,that is, at locations h+i2(mod hashsize)for i=1,2 e Other methods: Key-dependent increments; Random probing Hash Table Specifications P 404-405 Hash table: Hash table( ) void Hash table: clear() Error code Hash table: retrieve( const Key &target, Record &found)const H P.405 9.6.4 Chained Hash Tables P 406 o The linked lists from the hash table are called chains If the records are large, a chained hash table can save space. Collision resolution with chaining is simple cluster ing is no problem The hash table itself can be smaller than the number of records; overflow is no problem Deletion is quick and easy in a chained hash table e If the records are very small and the table nearly full, chaining may take more space Code for chained hash tables p 408 Definition: The class List can be any one of the generic linked implementations of a list studied in Chapter 6 Constructor: The implementation of the constructor simply calls the constructor for each list in the array Clear: To clear the table, we must clear the linked list in each of the table positions, using the. List method Retrieval: sequential search(table[ hash( target)1, target, position) Insertion: table[ hash( new entry)]. insert(O, new entry); Deletion: Error code Hash table: remove( const Key type &target, Record &x) 9.71 Analysis of Hashing P 411 The Birthday Surprise How many randomly chosen people need to be in a room before it becomes likely that two people will have the same birthday (month and day )? The probability that m people all have different birthdays is2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ If the keys are long but there are relatively few of them, then k is large and lg n relatively small, and other methods (such as mergesort) will outperform radix sort. ⚫ If k is small (the keys are short) and there are a large number of keys, then radix sort will be faster than any other method we have studied. [9.6] Hashing 9.6.1 Hash Tables P. 398 ⚫ Start with an array that holds the hash table. ⚫ Use a hash function to take a key and map it to some index in the array. This function will generally ma p several different keys to the same index. ⚫ If the desired record is in the location given by the index, then we are finished; otherwise we must use some method to resolve the collision that may have occurred between two records wanting to go to the same location. ⚫ To use hashing we must (a) find good hash functions and (b) determine how to resolve collisions. 9.6.2 Choosing a Hash Function P. 399 ⚫ A hash function should be easy and quick to compute. ⚫ A hash function should achieve an even distribution of the keys that actually occur across the range of indices. ⚫ The usual way to make a hash function ia to take the key, chop it up, mix the pieces together in various ways, and thereby obtain an index that will be uniformly distributed over the range of indices. ⚫ Note that there is nothing random about a hash function. If the function is evaluated more than once on the same key, then it must give the same result every time, so the key can be retrieved without fail. ⚫ Truncation: Sometimes we ignore part of the key, and use the remaining part as the index. ⚫ Folding: We may partition the key into several parts and combine the parts in a convenient way. ⚫ Modular arithmetic: We may convert the key to an integer, divide by the size of the index range, and take the remainder as the result. ⚫ A better spread of keys is often obtained by taking the size of the table (the index range) to be a prime number. C++ Example of a Hash Function P. 400-401 9.6.3 Collision Resolution with Open Addressing P. 401-403 ⚫ Linear Probing:Linear probing starts with the hash address and searches sequentially for the target key or an empty position. The array should be considered circular, so that when the la st location is reached, the search proceeds to the first location of the array. ⚫ Clustering: ⚫ Quadratic Probing:If there is a collision at hash address h, quadratic probing goes to locations h+1, h+4, h+9, ... , that is, at locations h+i2 (mod hashsize) for i = 1, 2,... . ⚫ Other methods: Key-dependent increments; Random probing. Hash Table Specifications P. 404-405 Hash table :: Hash table( ); void Hash table :: clear( ); Error code Hash table :: retrieve(const Key &target, Record &found) const; Hash Table Insertion P. 405 9.6.4 Chained Hash Tables P. 406 ⚫ The linked lists from the hash table are called chains. ⚫ If the records are large, a chained hash table can save space. Collision resolution with chaining is simple; clustering is no problem. ⚫ The hash table itself can be smaller than the number of records; overflow is no problem. ⚫ Deletion is quick and easy in a chained hash table. ⚫ If the records are very small and the table nearly full, chaining may take more space. Code for Chained Hash Tables P. 408 ⚫ Definition: The class List can be any one of the generic linked implementations of a list studied in Chapter 6. ⚫ Constructor: The implementation of the constructor simply calls the constructor for each list in the array. ⚫ Clear: To clear the table, we must clear the linked list in each of the table positions, using the List method clear( ). ⚫ Retrieval: sequential search(table[hash(target)], target, position); ⚫ Insertion: table[hash(new entry)].insert(0, new entry); ⚫ Deletion: Error code Hash table :: remove(const Key type &target, Record &x); [9.7] Analysis of Hashing P. 411 The Birthday Surprise: ⚫ How many randomly chosen people need to be in a room before it becomes likely that two people will have the same birthday (month and day)? ⚫ The probability that m people all have different birthdays is