Programming Languages assignment VI
The hash-table is an important general-purpose data structure with constant- time access, insertion and retrieval on the average. The purpose of this exercise is to write a generic or template implementation of a hash-table, with a few basic container operations for it. A simple and effective implementation of a hash-table is as follows: we use an array of headers, of fixed size, and we use one large array to store the actual values that are held in the table. A header is an index into the storage array. Each entry in the storage array has a link to the next entry with the same hash code. The hash code of an object is used as an index into the array of headers. The table is parametrized by the type of the objects we store in it. In order to enter objects in the table, or search the table for a particular object, we need to have two operations defined on these objects: a) We need a function Hash, that takes an object and returns an integer. b) We need equality to be defined. The first part of the assignment is to write the template for this data structure, with a constructor, the operations Insert and Find, and an iterator class that iterates over the contents of the table. Insert enter an element into the table. If the element is already present, Insert is a noop. Find determines whether an element is present in the table. The Iterator has the usual operations (Init, Next, Done), and produces references to successive objects stored in the table, The easiest is to implement the iterator as an iterator over the storage array, but it is more interesting to have an iterator that delivers objects in order of their hash-code. In that case the iterator needs to record the current entry in the headers array, and the current object on the chain of objects with that particular hash-code. The second part of the assignment consists in testing your implementation with three types: integers, character strings, and the large integers of the previous assignments. a) For integers, their value (modulo the size of the headers table) is a convenient hash-code. b) For strings, a reasonable hash-code is obtained by doing arithmetic on successive bytes or words in the string. Adding up character values, or successive word values, is a reasonable choice. c) For large integers, some arithmetic combination of the words in the mantissa can be used. For your test program. generate 20 values of the proper type, insert them into the table, and use the iterator to print the contents of the table. You can create the input by hand. Make sure that there are some duplicates among those 20, so that the output contains fewer than 20 elements (to verify that Insert does not produce duplicates).