Suppose that Rachel is making a program that will monitor products in a warehous
ID: 3802006 • Letter: S
Question
Suppose that Rachel is making a program that will monitor products in a warehouse. There are about 10,000 different products in this warehouse, and they are always changing. The products can be sorted with their unique product key; which is their primary key. She will need to have fast insertion, and find times, for the products. She will not delete products except in rare occasions. The time to find a product in her program is more important because she will only have to insert many of the items on the first loading of the program. What would be the best data structure to use to hold all of her products? And write your reasoning behind choosing this data structure.Explanation / Answer
If the product keys were integers in the range 0 to 100000, we could store the key/value pairs in an array, A, of 100000 elements. The key/value pair with key K would be stored in A[K]. The key takes us directly to the location of the key/value pair. The problem is that there are usually far too many different possible keys for us to be able to use an array with one location for each possible key. For example, if the key can be any value of type int, then we would need an array with over four billion locations -- quite a waste of space if we are only going to store, say, a few thousand items! If the key can be a string of any length, then the number of possible keys is infinite, and using an array with one location for each possible key is simply impossible.
In order to tacke this problem we will use HashTable. Hash tables store their data in an array, and the array index where a key is stored is based on the key. The index is not equal to the key, but it is computed from the key. The array index for a key is called the hash code for that key. A function that computes a hash code, given a key, is called a hash function. To find a key in a hash table, you just have to compute the hash code of the key and go directly to the array location given by that hash code.
Hence,
insertioin and seraching time both for a hash table is O(1).
therefore hash table is best choice.