The goal is for you to think about hashing.
1) Thinking about dynamic tree and hashing techniques for databases, how would they compare in terms of speed and what they can accomplish? It says speed and not complexity because you should discuss the expected and practical speed. This can and should involve formulas and discussion but should also include practical considerations of speed and the formulas shown. This is similar to what we did in class.
2) The load factor in hashing is generally kept small so the expected number of items at any hash location is small if the hash function effectively spreads out the entries. In the hashing you learned in data structures and algorithms, the hash table/array is increased in size to reduce the load factor when it gets too large. This requires rehashing all entries. Extensible and linear hashing both avoid having to rehash all the entries. Why is this important? How does each technique accomplish this?
3) When working with an array in memory you cannot, in general, make the array larger. Instead you must create a larger array and then copy the items from the smaller array into the larger array. Both extensible and linear hashing increase the size of the table (more buckets) when needed but they do not necessarily need to copy all the existing buckets at that time. Explain how storing items in an array is different than storing them as buckets on a disk so this is possible.
4) Why does linear hashing have overflow buckets but extensible hashing does not (ignore issues with duplicates)? Why do you generally not get long chains of overflow buckets in linear hashing but you can in static hashing?
You may (and are even encouraged) to work in groups of up to three (3) students. You only need to turn in one solution for each group unless there is a problem. Place all group members names on the solution. All members of the group must know the details and reasoning of the solution. If only some members worked on and understand a particular problem solution then this should be noted on what you turn in by giving the name(s) of the people who accomplished the work for that problem.
There is an assignment link on Moodle. Turn in a file with your answers. It can be in any reasonable format (PDF, RTF, MS Word, Open Office, ....).