Data Structures, Algorithms, & Applications in C++
Chapter 10, Exercise 37

(a)

Different chains must have different head nodes because the head node of every nonempty chain must point to a different next node.

(b)

The key field of a head node cannot be made to serve any useful purpose. Therefore, there is no point in setting it to any particular value.

(d)

When we use only a common tail node, the space penalty is for just one node. We expect a considerable saving in the run time because the loop conditionals are simplified. Therefore, the use of a common tail is recommended. The number of head nodes required equals the number of buckets. Since hash tables are typically used with a low loading density, the total number of elements (i.e., the value of size) is typically a small constant times the number of buckets, say up to ten times the number of buckets. In this case the space overhead of the head nodes is 10% or more. For applications that are not space/memory constrained, we might as well use the available space and reap the small savings in run time and programming complexity that the use of head nodes provides. For space constrained applications, the use of head nodes is not recommended; head nodes afford very little run time reduction and very little program simplification.