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 pointers2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 (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