資料結構›Ch8 雜湊
第 4 題/共 37 題
◀ DS 4/37
4. Hashing、Universal Hashing、碰撞分析
#DS-08-004難HashingUniversal Hashing碰撞分析

Let SS be a collection of nn objects, each with a unique integer key ai∈{0,1,2,…,n2−1}a_i \in \{0,1,2,\ldots,n^2-1\}. Consider hashing all the objects in SS into an array A[0..m−1]A[0..m-1] of m=⌈n1.5⌉m=\lceil n^{1.5}\rceil buckets. Each bucket stores a (singly) linked list of all objects hashed into the same bucket. The hashing algorithm works as follows. The algorithm first picks a hash function hh uniformly at random from a hash family H\mathcal H. Then, for each object i∈Si \in S, the algorithm computes h(ai)h(a_i) and inserts the object into the bucket A[h(ai)]A[h(a_i)]. The number of collisions τ\tau is defined to be the total number of (unordered) object pairs hashed into the same bucket. We focus on the choice of the hash family H\mathcal H and the worst-case expected number of collisions E[τ]\mathbf E[\tau]. Note that the term worst-case refers to the choice of the input set SS. Select all statement(s) that are correct for every sufficiently large nn.

📄 台大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊
本章題號 · 1–20 / 37