計(jì)算機(jī)算法導(dǎo)論_第11章-在線瀏覽
2025-05-10 00:04本頁(yè)面
【正文】 per slot ? What will be the average cost of an unsuccessful search for a key? 28 Analysis of Chaining ? Assume simple uniform hashing: each key in table is equally likely to be hashed to any slot ? Given n keys and m slots in the table, load factor ? = n/m = average keys per slot ? What will be the average cost of an unsuccessful search for a key? A: O(1+?) 29 Analysis of Chaining ? Assume simple uniform hashing: each key in table is equally likely to be hashed to any slot ? Given n keys and m slots in the table, load factor ? = n/m = average keys per slot ? What will be the average cost of an unsuccessful search for a key? A: O(1+?) ? What will be the average cost of a successful search? 30 Analysis of Chaining ? Assume simple uniform hashing: each key in table is equally likely to be hashed to any slot ? Given n keys and m slots in the table, the load factor ? = n/m = average keys per slot ? What will be the average cost of an unsuccessful search for a key? A: O(1+?) ? What will be the average cost of a successful search? A: O(1 + ?/2) = O(1 + ?) 31 Analysis of Chaining 32 Analysis of Chaining 33 Analysis of Chaining 34 Analysis of Chaining 35 Analysis of Chaining ? Thus, the total time required for a successful search (including the time for puting the hash function) is Θ(2 + α/2 α/2n) = Θ(1 + α). 36 Analysis of Chaining ? So the cost of searching = O(1 + ?) ? If the number of keys n is proportional to the number of slots in the table, what is ?? ? A: ? = O(1) ? In other words, we can make the expected cost of searching constant if we make ? constant Hash functions 38 Choosing A Hash Function ? Clearly choosing the hash function well is crucial ? What will a worstcase hash function do? ? What will be the time to search in this case? ? What are desirable features of the hash function? ? Should distribute keys uniformly into slots ? Should not depend on patterns in the data 39 The Division Method ? h(k) = k mod m ? In words: hash k into a table with m slots using the slot given by the remainder of k divided by m ? What happens to elements with adjacent values of k? ? What happens if m is a power of 2 (say 2P)? ? What if m is a power of 10? ? Upshot: pick table size m = prime number not too close to a power o
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1