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. (It is worth noting that when you create a List, you have full control over what properties your List has, so you can design these structures to meet your needs)

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 –

http://stackoverflow.com/questions/14409466/simple-hash-functions

Google Simple Hash functions,

I would recommend a function that is 8 bits or more to avoid collisions. 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.

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

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

Sample Node with Hashed values – You will make a linked list of these. You will not sort or modify the original list

Once you have filled in all the ContentA and ContentB values you will create an array which will be your index array.  This array will contain as its content the value from the original List (1) ContentB – the hashed value and (2) A pointer to the node from the original list. This means you will need to create an object that has these 2 properties to place into the array.  This is your index – indexing is used in databases to easily find values in a huge set of data. You will sort the array on these values (you may use the built-in array functions). Because the array contains objects with 2 properties – you will need to specify which property will be used to sort the array.  This can be done using a compareFunction ( see https://www.w3schools.com/jsref/jsref_sort.asp )

Here is code you can use to create your IndexNode to place into the array.

function IndexNode(_sourceNode) {

  this.source = _sourceNode;

  this.content = _sourceNode.contentB;

}

example of a compareFunction – this is a function you can put in the call to the built in sort function of the Array. It will define the comparison performed to determine the sort order. The function returns -1, 1, or 0 depending on whether a is less than b, greater than b, or equal to be respectively. Note that the following is taken from the “Try It” editor at https://www.w3schools.com/jsref/tryit.asp?filename=tryjsref_sort4

var fruits = ["Banana", "Orange", "Apple", "Mango"];

function myFunction() {

    fruits.sort(function(a,b){return (a<b?-1:(a>b?1:0))});&nbsp;

    document.getElementById("demo").innerHTML = fruits;

}

After you create the IndexNodes (there will be one for every Node in the original list) you can place them into an array or a list. You will then sort THIS list by the hash values.

Here is the sample input and output.

The output of Create List would look something like this (horizontal or vertical)

The output of the Adler 32 bit hash for the input values would be as shown

Each value of the Hash function maintains a pointer to the value that created it. You do this by simply having a specific pointer in your construction of the List when you created it (you could call the pointer source). The results of sorting the Hash list and then the output could look something like this.

You final output will be a print of the Sorted Array’s Hash values and the value of the content of the Source Node the Index Nodes point to.

This may be complex – but it is the basis of a lot of different indexing schemes. Please note that in this sample the Hash values are larger than the content – but in most cases the content will be VERY big and the hash values much smaller.

All COP3530 Assignments