In the previous chapter, we discussed the hierarchical tree data type, which is a non-linear data type, that stores data in a tree-like structure. In this chapter, we are going to discuss another non-linear data type, the hash table, which stores data based on a key. The following topics are discussed in this chapter:
To follow along with this chapter, including the source code, we require the following:
Suppose we want to store a collection of numbers, for instance, a phone number, and let's say we have approximately 1,000,000 numbers. In previous chapters, we also discussed several data structures, and here we can consider using one of them. We can use an array or a list, but we have to provide a million slots of data in the array. If we need to add some phone numbers again, we have to resize the array. Also, the operation of searching will be costly, since we have to use a linear search algorithm with time complexity O(N), where the time consumption will increase if we add data to the list. Indeed, we can use a binary search algorithm with O(log N) time complexity if we manage to sort the elements of the list containing the bunch of phone numbers; however, the insert operation will be costly, since we have to maintain the sorted list.
Another data structure we can choose is the balanced binary search tree. It can give us a moderate time complexity, since...
Separate chaining is a collision handling technique that will make each cell in the hash table point to a chaining node containing values with the same hash key. We are going to create an ADT named HashTable to handle the preceding phone number list. Since the phone number contains only numbers, it will be stored in the int data type, and the owner of the phone number name will be stored in the string data type. However, if the phone number we have are saved as 123-456-789 format, we need to remove the dash (-) character first.
The HashTable will be four basic operations and they are:
Insert() is used to insert a new pair<int, string> to the hash table. It passes an int as a key and a string as a value. It then finds a hash key for the inputted key. If the inputted key is found in the hash table, it will update the value of the key. If no key is found, it will append a new node to the linked list containing the inputted key and inputted value...As we discussed earlier at beginning of this chapter, an open addressing technique stores all elements in the hash table itself. A collision will not happen, since there is a calculation that will be performed if a collision is about to happen. Based on this calculation, we can have three types of open addressing technique—Linear probing, quadratic probing, and double hashing. The difference between the three is the formula for finding the next free space if the hash key of the given element has been occupied:
(HashFunction(key) + n) % TABLE_SIZE, then increase n from 0 until a free slot is found. Here is the explanation—If HashFunction(key) % TABLE_SIZE is occupied, then try (HashFunction(key) + 1) % TABLE_SIZE. If the slot is still occupied, try (HashFunction(key) + 2) % TABLE_SIZE. Repeat it by increasing n until a...In this chapter, we have discussed another non-linear data type called a hash table. Although a collision can happen to the hash table data type, we have learned how to handle it by using a separate chaining technique or open addressing technique. Regarding the open addressing technique, it has three different kinds of handling—linear probing, quadratic probing, and double hashing; however, they are relatively similar in terms of the implementation, except for the way in which we find the next free slot if the hash key we need to insert has been occupied.
In the next chapter, we are going to discuss common algorithm paradigms to design algorithms specifically for a certain purpose.
For further references, please visit these following links:
© 2018 Packt Publishing Limited All Rights Reserved
