2008级计算机 供课堂教学使用 Chapter 9 TABLES AND INFORMATION RETRIEVAL P 379 ----------------- 1. Introduction: Breaking the Ign Barrier 6. Hashing 7. Analysis of Hashin 3. Tables of Various Shapes 8. Conclusions: Comparison of Methods 4. Tables: A New Abstract Data Type 9. Application: The Life Game Revisited 5. Application: Radix Sort 19.1 Introduction: Breaking the lgn Barrier P 380 By use of key comparisons alone, it is impossible to complete a search of n items in fewer than Ig n Ordinary table lookup or array access requires only constant time O(1) Both table lookup and searching share the same essential purpose, that of information retrieval. The key used for searching and the index used for table lookup have the same essential purpose: one piece of information that is used to locate further information Both table lookup and searching al gorithms provide functions from a set of keys or indices to locations in a list or array In this chapter we study ways to implement and access various kinds of tables in contiguous storage Several steps may be needed to retrieve an entry from some kinds of tables, but the time required remains(1). It is bounded by a constant that does not depend on the size of the table. Thus table lookup can be more efficient than any searching method We shall implement abstractly defined tables with arrays. In order to distinguish between the abstract concept and its implementation, we introduce Convention: The index defining an entry of an abstractly defined table is enclosed in parentheses, whereas the index of an entry of an array is enclosed in square brackets 19.2 Rectangular Arrays P 381-383 19.3 Tables of Va arious Shapes 9.3. 1 Matrices of Various Shapes P 384 Contiguous implementation of a triangular table 9.3.2 Jagged Table with Access Table P. 385 Symmetrically Triangular Table P 388 9.3.3 Inverted Table P. 386-387 19.4] Tables: A New Abstract Data Type P 388 Functions P 389 e In mathematics a function is defined in terms of two sets and a correspondence from elements of the first set to elements of the second. If f is a function from a set a to a set b, then f assigns to each element of a a unique element of B The set A is called the domain of f. and the set b is called the codom ain of f Dr The subset of B containing just those elements that occur as values of f is called the range of f DEFINITION: A table with index set I and base ty pe T is a function from I to T together with the following operations P.389-390 1. Table access: Evaluate the function at any index in I 2. Table assignment: Modify the function by changing its value at a specified index in I to the new value specified in the assignment. 3. Creation: Set up a new function 4. Clearing: Remove all elements from the index set I, so there is no remaining domain 5. Insertion: Adjoin a new element x to the index set I and define a corresponding value of the function at x 6. Deletion: Delete an element x from the index set I and restrict the function to the resulting smaller domain Implementation of a table P 391 19.51 Application: Radix Sort P 391 9.5.1 Trace of a Radix Sort 9.5.2 Linked Radix Sort P. 393 Linked Implementation of Radix Sort List definition P.394 Record definition P. 394 Sorting Method, Linked Radix Sort P. 395 Auxiliary Functions, Linked Radix Sort Selecting a qu P 395 Connecting the queues: P 396 9.5.3 Analysis of Radix Sort P 396 e The time used by radix sort is o(nk), where n is the number of items being sorted and k is the number of characters in a key e The relative performance of radix sort to other methods will relate to the relative sizes of nk and n lg n; that is, of k and Ig n
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 9 TABLES AND INFORM ATION RETRIEVA L P.379 ----------------------------------------------------------------------------------------------------------------------------- ---- 1. Introduction: Breaking the lgn Barrier 2. Rectangular Arrays 3. Tables of Various Shapes 4. Tables: A New Abstract Data Type 5. Application: Radix Sort 6. Hashing 7. Analysis of Hashing 8. Conclusions: Comparison of Methods 9. Application: The Life Game Revisited [9.1] Introduction: Breaking the lgn Barrier P. 380 ⚫ By use of key comparisons alone, it is impossible to complete a search of n items in fewer than lg n comparisons, on average (lowerbound_search_thm). ⚫ Ordinary table lookup or array access requires only constant time O (1). ⚫ Both table lookup and searching share the same essential purpose, that of information retrieval. The key used for searching and the index used for table lookup have the same essential purpose: one piece of information that is used to locate further information. ⚫ Both table lookup and searching al gorithms provide functions from a set of keys or indices to locations in a list or array. ⚫ In this chapter we study ways to implement and access various kinds of tables in contiguous storage. ⚫ Several steps may be needed to retrieve an entry from some kinds of tables, but the time required remains O (1). It is bounded by a constant that does not depend on the size of the table. Thus table lookup can be more efficient than any searching method. ⚫ We shall implement abstractly defined tables with arrays. In order to distinguish between the abstract concept and its implementation, we introduce: Convention: The index defining an entry of an abstractly defined table is enclosed in parentheses, whereas the index of an entry of an array is enclosed in square brackets. [9.2] Rectangular Arrays P. 381-383 [9.3] Tables of Various Shapes 9.3.1 Matrices of Various Shapes P. 384 Contiguous implementation of a triangular table 9.3.2 Jagged Table with Access Table P. 385 Symmetrically Triangular Table P. 388 9.3.3 Inverted Table P. 386-387 [9.4] Tables: A New Abstract Data Type P. 388 Functions P. 389 ⚫ In mathematics a function is defined in terms of two sets and a correspondence from elements of the first set to elements of the second. If f is a function from a set A to a set B , then f assigns to each element of A a unique element of B . ⚫ The set A is called the domain of f , and the set B is called the codomain of f . ⚫ The subset of B containing just those elements that occur as values of f is called the range of f . DEFINITION: A table with index set I and base type T is a function from I to T together with the following operations. P. 389-390 1. Table access: Evaluate the function at any index in I . 2. Table assignment: Modify the function by changing its value at a specified index in I to the new value specified in the assignment. 3. Creation: Set up a new function. 4. Clearing: Remove all elements from the index set I , so there is no remaining domain. 5. Insertion: Adjoin a new element x to the index set I and define a corresponding value of the function at x . 6. Deletion: Delete an element x from the index set I and restrict the function to the resulting smaller domain. Implementation of a table P. 391 [9.5] Application: Radix Sort P. 391 9.5.1 Trace of a Radix Sort P. 392 9.5.2 Linked Radix Sort P. 393 Linked Implementation of Radix Sort List definition: P. 394 Record definition P. 394 Sorting Method, Linked Radix Sort P. 395 Auxiliary Functions, Linked Radix Sort Selecting a queue: P. 395 Connecting the queues: P. 396 9.5.3 Analysis of Radix Sort P. 396 ⚫ The time used by radix sort is Θ(nk), where n is the number of items being sorted and k is the number of characters in a key. ⚫ The relative performance of radix sort to other method s will relate to the relative sizes of nk and n lg n; that is, of k and lg n
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 is
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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
2008级计算机 内部资料,仅供课堂教学使用 364/365)°(363/365)°(362/365)*。((365-m+1)/365) This expression becomes less than 0.5 whenever m 2 23 For hashing, the birthday surprise says that for any problem of reasonable size, collisions will almost ertainly occur Analysis of Hashing P 411-413 A probe is one comparison of a key with the target The load factor of the table is 2=n/, where n positions are occupied out of a total of t positions in the table Retrieval from a chained hash table with load factor 2 requires approximately 1+2/2 probes in the successful ase and n probes in the unsuccessful case Retrieval from a hash table with open addressing, random probing, and load factor n requires approximately (In) *In(1/(1-2))probes in the successful case and 1/(1-1)probes in the unsuccessful case Retrieval from a hash table with open addressing, linear probing, and load factor h requires approximately (1+1/(1-2)/2 and(1+1/(1-2)2)/2 probes in the succes sful case and in the unsucces sful case, respectively Theoretical comparisons: P. 413-414 Empirical comparisons: P. 414-415 19.8 Conclusions: Comparison of Methods P 415 We have studied four principal methods of information retrieval, the first two for lists and the second two for tables. Often we can choose either lists or tables for our data structures e Sequential search is o(n): Sequential search is the most flexible method. The data may be stored in any order, with either contiguous or linked representation o Binary search is o(log n): Binary search demands more, but is faster: The keys must be in order, and the data must be in random-access representation(contiguous storage) Table lookup is o(1): Ordinary lookup in contiguous tables is best, both in speed and convenience, unless a list is preferred, or the set of keys is sparse, or insertions or deletions are frequent Hash-table retrieval is O(1): Hashing requires the most structure, a peculiar ordering of the keys well suited to retrieval from the hash table, but generally useless for any other purpose. If the data are to be available for human inspection, then some kind of order is needed, and a hash table is inappropriate 9.9 Application: The Life Game Revisited P.418 9.9.1 The life cells are supposed to be on an unbounded grid, not a finite array as used in Chapter I In the class Life. we would like to have the declarat ion class Life i public ∥ methods private bool map[int int] /other data and auxiliary functions which is. of Use a hash table to represent the data member map(sparse array) The main function remains unchanged from Chapter 1. P. 418 Rewrite the method update so that it uses a hash table to look up the status of cells For any given cell in a configuration, we can determine the number of living neighbors by looking up the status of each neighboring cell Candidates that might live in the coming generation are those that are alive and their(dead) neighbors Method update will traverse these cells, determine their neighbor counts by using the hash table, and select those cells that will live in the next generation 9.92 Data Structures for Life P 419 A Life configuration includes a hash table to look up the status of cells We need to traverse the living cells in a configuration. To do this, we keep a List of living cells as a second data member of a Life configuration An object stored in the list and table is a structure called Cell, containing a pair of grid coordinates truct Cell i Cell()i row col=0;)//constructors Cell(int x, int y)( row =x;col =y;3 int row, col: / grid coordinates e As a Life configuration expands, cells on its fringes will be encountered for the first time. Whenever a new Cell is needed, it must be created dynamically, so Cell objects will only be accessed through pointers
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 (364/365)*(363/365)*(362/365) *...*( (365-m+1)/365) This expression becomes less than 0.5 whenever m ≥ 23. ⚫ For hashing, the birthday surprise says that for any problem of reasonable size, collisions wi ll almost certainly occur. Analysis of Hashing P. 411-413 ⚫ A probe is one comparison of a key with the target. ⚫ The load factor of the table is λ = n/t , where n positions are occupied out of a total of t positions in the table. ⚫ Retrieval from a chained hash table with load factor λ requires approximately 1+λ /2 probes in the successful case and λ probes in the unsuccessful case. ⚫ Retrieval from a hash table with open addressing, random probing, and load factor λ requires approximately (1/λ)*ln(1/(1-λ)) probes in the successful case and 1/(1−λ) probes in the unsuccessful case. ⚫ Retrieval from a hash table with open addressing, linear probing, and load factor λ requires approximately (1+1/(1-λ))/2 and (1+1/(1-λ) 2 )/2 probes in the successful case and in the unsuccessful case, respectively. Theoretical comparisons: P. 413-414 Empirical comparisons: P. 414-415 [9.8] Conclusions: Comparison of Methods P. 415 We have studied four principal methods of information retrieval, the first two for lists and the second two for tables. Often we can choose either lists or tables for our data structures. ⚫ Sequential search is Θ(n): Sequential search is the most flexible method. The data may be stored in any order, with either contiguous or linked representation. ⚫ Binary search is Θ(log n): Binary search demands more, but is faster: The keys must be in order, and the data must be in random-access representation (contiguous storage). ⚫ Table lookup is Θ(1): Ordinary lookup in contiguous tables is best, both in speed and convenience, unless a list is preferred, or the set of keys is sparse, or insertions or deletions are frequent. ⚫ Hash-table retrieval is Θ(1): Hashing requires the most structure, a peculiar ordering of the keys well suited to retrieval from the hash table, but generally useless for any other purpose. If the data are to be available for human inspection, then some kind of order is needed, and a hash table is inappropriate. [9.9] Application: The Life Game Revisited P. 418 9.9.1 ⚫ The Life cells are supposed to be on an unbounded grid, not a finite array as used in Chapter 1. ⚫ In the class Life, we would like to have the declaration class Life { public: // methods private: bool map[int][int]; // other data and auxiliary functions }; which is, of course, illegal. ⚫ Use a hash table to represent the data member map (sparse array). ⚫ The main function remains unchanged from Chapter 1. P. 418 ⚫ Rewrite the method update so that it uses a hash table to look up the status of cells. ⚫ For any given cell in a configuration, we can determine the number of living neighbors by looking up the status of each neighboring cell. ⚫ Candidates that might live in the coming generation are those that are alive and their (dead) neighbors. Method update will traverse these cells, determine their neighbor counts by using the hash table, and select those cells that will live in the next generation. 9.9.2 Data Structures for Life P. 419 ⚫ A Life configuration includes a hash table to look up the status of cells. ⚫ We need to traverse the living cells in a configuration. To do this, we keep a List of living cells as a second data member of a Life configuration. ⚫ An object stored in the list and table is a structure called Cell, containing a pair of grid coordinates: struct Cell { Cell( ) { row = col = 0; } // constructors Cell(int x, int y) { row = x; col = y; } int row, col; // grid coordinates }; ⚫ As a Life configuration expands, cells on its fringes will be encountered for the first time. Whenever a new Cell is needed, it must be created dynamically, so Cell objects will only be accessed through pointers
2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 e To dispose of a Cell object, at the end of its lifetime, we must remember the corresponding pointer Therefore, the List member will store pointers to cells rather than the cells themselves. This is called an indirect list Indirect Linked List of Cells P 420 Each node of the List contains two pointers: one to a Cell and one to the next node of the list The Hash Table P 420 Entries of the hash table will be pointers to cells, as in the List he coordinates of the cells, which are determined by the pointers, are the corresponding keys We must decide between open addressing and chaining The entries to be stored in the table need little space: Each entry need only store a pointer to a Cell. Since the table entries are small, there are few space considerations to advise our decision With chaining, the size of each record will increase 100 percent to accommodate the necessary pointer, but the hash table itself will be smaller and can take a higher load factor than with open addressing With open addressing, the records are smaller, but more room must be left vacant in the hash table to avoid long searches and possible overflow For flexibility, let us decide to use a chained hash table class Hash table Error code insert( Cell *new entry) bool retrieve(int row, int col)const private Listve in the coming generation. e In the method update, a local variable Life new configuration is thereby gradually built up to represent the upcoming configuration. e We loop over all the(living) cells from the current configuration, and we also loop over all the(dead) cells At the end of update, we swap the list and Hash table members between the current configuration and new configuration. This exchange also ensures that the destructor that will automatically be applied to the local variable Life new configuration ng:P423-424 Creation and insertion of new cells: P 424 Construction and destruction of Life objects: P. 424-425 The hash function: P 425-426 Pointers and pitfalls 9 items P. 426-427 Errata p.396,"Uses: "line: Delete comma and Record. The"to"Key and Record,the" after "List 05, " Uses: line: Change Key p. 408, line-5, and p 410, line 5: Change "Key type"to"Key
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ To dispose of a Cell object, at the end of its lifetime, we must remember the corresponding pointer. Therefore, the List member will store pointers to cells rather than the cells themselves. This is called an indirect list. ◼ Indirect Linked List of Cells P. 420 ◼ Each node of the List contains two pointers: one to a Cell and one to the next Node of the List. The Hash Table P. 420 ⚫ Entries of the hash table will be pointers to cells, as in the List. ⚫ The coordinates of the cells, which are determined by the pointers, are the corresponding keys. ⚫ We must decide between open addressing and chaining. ⚫ The entries to be stored in the table need little space: Each entry need only store a pointer to a Cell. Since the table entries are small, there are few space considerations to advise our decision. ⚫ With chaining, the size of each record will increase 100 percent to accommodate the necessary pointer, but the hash table itself will be smaller and can take a higher load factor than with open addressing. ⚫ With open addressing, the records are smaller, but more room must be left vacant in the hash table to avoid long searches and possible overflow. ⚫ For flexibility, let us decide to use a chained hash table. class Hash table { public: Error code insert(Cell *new entry); bool retrieve(int row, int col) const; private: List table[hash size]; }; ⚫ A Hash table comes with a default constructor and destructor, which we shall rely on. 9.9.3 The Life Class P. 421 ⚫ In the Life class, to facilitate the replacement of a configuration by an updated version, we shall store the data members indirectly, as pointers. P. 421 ⚫ The auxiliary member functions retrieve and neighbor _count determine the status of a cell by applying hash-table retrieval. ⚫ Auxiliary function insert creates a dynamic Cell object and inserts it into both the hash table and the list of cells of a Life object. 9.9.4 Updating the Configuration P. 422-423 ⚫ update starts with one Life configuration and determines the configuration at the next generation. ⚫ With an unbounded grid, we must limit our attention to the cells that may be alive in the coming generation. These include the living cells and the dead cells with living neighbors. P. 422 ⚫ In the method update, a local variable Life new configuration is thereby gradually built up to represent the upcoming configuration. ⚫ We loop over all the (living) cells from the current configuration, and we also loop over all the (dead) cells that are neighbors of these (living) cells. ⚫ At the end of update, we swap the List and Hash table members between the current configuration and new configuration. This exchange also ensures that the destructor that will automatically be applied to the local variable Life new configuration. Printing: P.423-424 Creation and insertion of new cells: P.424 Construction and destruction of Life objects: P.424-425 The hash function: P.425-426 Pointers and Pitfalls 9 items P.426-427 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 396, "Uses:" line: Delete comma "," after "List". p. 405, "Uses:" line: Change "Key, and Record. The" to "Key and Record, the". p. 408, line -5, and p. 410, line 5: Change "Key_type" to "Key". -------------------------------------------------------------------------------------------------------------------------------
