Assignment 10 - Indexes

Summary

We are going to learn to create an index. In our example the index will be in the form of a sorted array with pointers to a List

Assignment

The first step of this assignment will be to create a List. You may use any List that you have already created. For the purposes of this assignment it does not matter if your list is a doubly linked list of a singly linked list. I recommend that if you created a good useful list in the previous lists assignment use this list.

Your list will be a little different in that it will have 2 content properties. I recommend calling them contentA and contentB.

The next step will be to fill the contentA and contentB list with actual content. ContentA will be filled with a random string or number. You may select a string of any length. ContentB will be filled with a Hash of ContentA. You may choose any simple hash function and apply it.

You can select from a list of Hash Function - see https://en.wikipedia.org/wiki/List_of_hash_functions , https://en.wikipedia.org/wiki/Hash_function - I would recommend a function that is 8 bits or more to avoid collisions. An incredibly good description of some hash function and their use is given at the Stack Overflow Article at http://stackoverflow.com/questions/14409466/simple-hash-functions 

You must document the name and source of your hash function in the comments of your code. This should be relatively easy once you implement your hash function. (Hint: Google simple Hash functions, you will find plenty)

ContentB = HashFunction(ContentA);   (note that some Hash function accept additional "seed" parameters)

Your List should contain 10 nodes. Use a loop to create it.

Once you have filled in all the ContentA and ContentB values you will create an object (similar to a Node) that contains (1) ContentB - the hashed value and (2) A pointer to the node it came from for each of the 10 nodes in the list. These objects will be placed into an array. This is your index.You will sort the array on these values (you may use the built-in array functions).

The final step is you should be able to ENTER a hashed value and click "Look Up". The system will find it in the array - and look up the original unhashed value and report it back to you. If the original value does not exist - it will report that.

Quizzes (Quiz Submission Instructions )

You quiz this week is the Miscellaneous quiz - http://quiz.geeksforgeeks.org/data-structure/misc-3/