Both hash tables and red-black trees can be used to implement symbol tables. Whi

Question

Both hash tables and red-black trees can be used to implement symbol tables. Which one should you choose? Match the requirement on the left to the implementation on the right You write code for an auto-pilot. It is very important that all symbol table look-ups execute in the specified time [Choose] You write code for a game that uses a lot of animation. Speed is your first concern when selecting a symbol table implementation [Choose] Prof. Sedgewick introduced two ways to implement a hash table: separate chaining and linear probing. These methods have different advantages and disadvantages. Select typically has better cache performance Select is less sensitive to designed hash functions

Explanation / Answer

Q3:
a.Red Black Tree
b.Hash table

Discussion:
The HashTable is the most suitable algorithm to use, as it is simply generating a hash of your key object and using that to access the target data - it is O(1). The others are O(N) (Linked Lists of size N - you have to iterate through the list one at a time, an average of N/2 times) and O(log N)

Q4: a.Linear probing typically has better cache performance.
b.Separate chaining is less sensitive to poorly designed has functions.

Discussion:
Advantage of the probing method is that the values all will be in the same array. This makes copy-on-write very easy by just copying only the array. If we can be assured the original is not modified by way of class invariant then a taking a snapshot is O(1) and can be done without locking.
Separate chaining (each bucket is a pointer to a linked list of values) has the disadvantage that you end up searching a linked list with all cache-related issues at hand.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.