計算機算法導(dǎo)論_第11章(編輯修改稿)
2025-04-19 00:04 本頁面
【文章內(nèi)容簡介】 k3 k1 k5 U (universe of keys) K (actual keys) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— 23 Chaining ? How do we insert an element? —— —— —— —— —— —— T k4 k2 k3 k1 k5 U (universe of keys) K (actual keys) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— 24 Chaining —— —— —— —— —— —— T k4 k2 k3 k1 k5 U (universe of keys) K (actual keys) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— ? How do we delete an element? ? Do we need a doublylinked list for efficient delete? 25 Chaining ? How do we search for a element with a given key? —— —— —— —— —— —— T k4 k2 k3 k1 k5 U (universe of keys) K (actual keys) k6 k8 k7 k1 k4 —— k5 k2 k3 k8 k6 —— —— k7 —— 26 Chaining ? CHAINEDHASHINSERT(T, x) insert x at the head of list T[h(key[x])] ? CHAINEDHASHSEARCH(T, k) search for an element with key k in list T[h(k)] ? CHAINEDHASHDELETE(T, x) delete x from the list T[h(key[x])] 27 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? 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:
研究報告相關(guān)推薦
鄂ICP備17016276號-1