View Forum Topic

Forums
CS312
Please Help! ** Q11-25T Questions **

Author	Message
G190852562 Posts: 162	Posted 14:47 Dec 08, 2014 \| 4. Which hash table implementation strategy is feasible for load factors larger than 1? Both chaining and open addressing Neither chaining nor open addressing Only chaining Only open addressing I definitely forgot what was chaining and open addressing. Can someone give me a recap? 5. Roughgarden demonstrated that every hash function has a pathological data set, i.e., a data set that causes the hash table to slow down to such an extent that it is no longer usable. Typically a pathological data set is one for which each element in the data set maps to the same bucket—or at least many elements of the data set map to the same bucket. How is this problem usually countered? Since cryptographic hash functions do not have pathological data sets, use a cryptographic hash function. Use a family of hash functions. Build a hash function by taking the sum of the hash values of functions in the family and then taking the mod of that sum with respect to the number of buckets to get the hash value. Use a family of hash functions. Switch from one hash function in the family to another at random times during program execution. Use a family of hash functions. Select a hash function at random from the family at the start of program execution. What was a hash function?
vsluong4 Posts: 87	Posted 20:48 Dec 08, 2014 \| 4) Open addressing is usually implemented as an array of objects. Chaining is typically implemented as an array of linked lists. Open addressing: [Apple, Ant, Apricot, ...., Boy, Ball,....] Chaining: [Apple/Ant/Apricot/.../Boy/Ball/..., , , , ] In opening addressing, each index in the array gets at most 1 object. If you get a conflict at insertion, you find the next available open slot, either through sequential scan, rehashing, multiple hashing, ...., etc. In chaining, the first index could potentially have all of your objects. 5) A hash function is a function that maps an object to a corresponding index. The precise definition is more general, but not too important for our purposes.

Author

Message

G190852562

Posts: 162

Posted 14:47 Dec 08, 2014 |

4. Which hash table implementation strategy is feasible for load factors larger than 1?

Both chaining and open addressing
Neither chaining nor open addressing
Only chaining
Only open addressing

I definitely forgot what was chaining and open addressing. Can someone give me a recap?

5. Roughgarden demonstrated that every hash function has a pathological data set, i.e., a data set that causes the hash table to slow down to such an extent that it is no longer usable. Typically a pathological data set is one for which each element in the data set maps to the same bucket—or at least many elements of the data set map to the same bucket. How is this problem usually countered?

Since cryptographic hash functions do not have pathological data sets, use a cryptographic hash function.
Use a family of hash functions. Build a hash function by taking the sum of the hash values of functions in the family and then taking the mod of that sum with respect to the number of buckets to get the hash value.
Use a family of hash functions. Switch from one hash function in the family to another at random times during program execution.
Use a family of hash functions. Select a hash function at random from the family at the start of program execution.

What was a hash function?

vsluong4

Posts: 87

Posted 20:48 Dec 08, 2014 |

4) Open addressing is usually implemented as an array of objects. Chaining is typically implemented as an array of linked lists.

Open addressing: [Apple, Ant, Apricot, ...., Boy, Ball,....]

Chaining: [Apple/Ant/Apricot/.../Boy/Ball/..., , , , ]

In opening addressing, each index in the array gets at most 1 object. If you get a conflict at insertion, you find the next available open slot, either through sequential scan, rehashing, multiple hashing, ...., etc.

In chaining, the first index could potentially have all of your objects.

5) A hash function is a function that maps an object to a corresponding index. The precise definition is more general, but not too important for our purposes.