Data Structure. Q: (Multiple choice) For hashing by open addressing, we need to
ID: 3770475 • Letter: D
Question
Data Structure.
Q: (Multiple choice) For hashing by open addressing, we need to decide the table size m and some parameters so that the table can be fully utilized. What does that actually mean?
1. Allocate a table with size m equal to the number of elements stored.
2. Decide m and other parameters so that for any element, the initial m probe positions are distinct.
3. Decide m and other parameters to reduce the probability of collisions.
4. Decide m and other parameters so that no collision could happen.
Explanation / Answer
1. Allocate a table with size m equal to the number of elements stored.
Reason -> Suppose we are using a chained hash table with m buckets, and the number of elements in the hash table is n. Then the average number of elements per bucket is n/m, which is called the load factor of the hash table, denoted . When an element that is not in the hash table is searched for, the expected length of the linked list traversed is . Since there is always the initial (constant) cost of hashing, the cost of hash table operations with a good hash function is, on average, O(1 + ). If we can ensure that the load factor never exceeds some fixed value max, then all operations will be O(1 + max) = O(1). .Allocate the bucket array is just the right size for the number of elements that are being added to it. In general, however, it's hard to know ahead of time what this size will be, and in any case, the number of elements in the hash table may need to change over time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.