You have 2048MiB of main memory of which 548MiB are being us

You have 2048MiB of main memory of which 548MiB are being used by the operating system plus related programs such as those manipulating tables A and T below. You are asked to organize the remaining space to support a hash table where words are stored in a contiguous table which is an array A of characters delimited by a null character \\0. A hash table T will store a wordID along with a reference (pointer or index) p to A. That way a wordID will be associated with a specific word. The average length of a word is given as 7 characters stored in UNICODE A wordID and p can only be in multiples of two bytes (i.e. 2B, 4B thus 21bits or 24bits won\'t be an option) for efficiency. Organize T and A for maximum efficiency. In an efficient implementation answer the following questions by filling the data in the table that follows. Justify your answers and choices. Round to nearest million for n, m, T, A but make sure you don\'t exceed the amount of available memory (i.e. A + T should be accommodated easily by the available memory). Make sure that you fill the following table with data. N = How many words n cam the scheme support, m = how big would the hash table size m (number of entries) be, worded = how many bits for a wordID, p = how many bits for pointer p, T = how much space (bytes) will you scheme use for T, A = how much space (bytes) will you scheme use for A, and A+T = what is the total space $A+T$ used by your scheme?

Solution

A constant-time O(1) lookup on an average hash table would take to associate T with A and efficient space would only make it succumb to O(nlogn) space complexity.

Schema for this question corrresponds to hash table amd using associative arrays.

Now consider the questions:

Let the hash function wechoose distributes the wordId evenly over the table, so for each i, 0 i m 1, we have

| { k Key : h ( k) = i}| N / m .

I am taking 1 word=16b and 1 char=1B so 7 chars would yield to 56 b (bits) and ceil(3.5)=4 words.

We have remaining space 1500 MiB ( 2048-548 ) MiB. Moreover there are m^N functions in H, and hence it requires Nlogm bits to specify a function in H.

Given this information, all the answers couls be produced, as per user\'s environment consideration.