Data Structure

In many computer applications, it is often necessary to store a collection of key-value pairs. For example, consider a digital movie catalog. In this case, keys are movie names and values are their corresponding movie descriptions. Users of the application look up movie names and expect the program to fetch their corresponding descriptions quickly. Administrators can insert, erase and update movie descriptions, and they want to execute these operations quickly as well. In general, any data structure that stores a collection of key-value pairs is called an associative array. It implements the following interface:

allocate (size);

put (key, value);

get (key, values_array);

erase (key);

deallocate ();

The allocate command initializes a hash table of a given size. The put command stores a new key value pair in the associative array. The get command retrieves all key-value pairs with a matching key and stores their values in values_array. The erase command removes all key-value pairs with a matching key. The deallocate command frees all memory taken up by the hash table.

An associative array can be implemented in many different ways, and the implementation determines the time it takes the three different commands (i.e., put, get and erase) to execute. In this project, you will implement an associative array as a hash table. Relative to other data structures that can be used to implement an associative array (e.g., sorted array, linked list, etc.), the distinguishing characteristic of a hash table is that the time to put, get and erase a key-value pair does not increase asymptotically with respect to the number of key-value pairs inserted so far, i.e., their runtime is constant.

Programming Language. For your implementation, you will be using the java programming language.

Your data will be digital movie catalog.

Read data from a text file that contains the movie name and its description in each line.

(Supplement the question is included in the picture)

Implementation Details. A node of the linked list should be implemented as an object. This object contains one key-value entry as well as a pointer to the next node in the linked list. In Figure bellow (as an example), each slot in the array contains only a pointer to the first node in each linked list. Alternatively, you may also make each slot in the array be the first node of the linked list (meaning that each slot in the array contains one or more key-value pairs belonging to the given slot). This latter design would have better performance as it reduces random access. For the terminal node in the linked list, the pointer is set to NULL. When a new key-value pair is inserted into a linked list, a new node should be allocated using a new command, and the pointer of the terminal node should be set to point at the new node. Thus, a new node becomes the new terminal node. You may want to set the size of the array to be the first prime after the multiple of the expected data size to reduce the chance of collisions taking place. Note: instead of numbers uses a string, and use the best hash function for this case. News Ves KNN Good Luck