CSC263H1 Lecture Notes - Lecture 10: Double Hashing, List Of Dos Commands, Rna
Document Summary
Hashing m m slots, universe u, |u| > m, n entries h(k) hash function, h(k) = h(k(cid:48)) collision chaining! chaining linked list in each bucket. E[t ] consider searching for x chosen at random uniformly from items in t. Number of elements examined in search for x. = 1 + # of elements in fron of x in chain. = 1 + # of elements in x"s bucket inserted later than x. , xn be the elements in insertion order. 1 n(cid:88) n(cid:88) i=1 h(xi) = h(xj) otherwise i=1 n(cid:88) Properties we would like: not all go to same bucket, spread out keys, no empty buckets, need deterministic, e cient, use all bits of key. Open addressing h(k) = (cid:98)m frac(k a)(cid:99) where a (0, 1] Instead of using chaining, we can store all the items directly in t . When a given bucket is full, we have a rule for determining which bucket to use next.
