Hash Table and STL | Algorithms - Computer Science Engineering (CSE) PDF Download

Hash Table

• In a hash table, a value is stored by calling a hash function on a key.
• Values are not stored in sorted order.
• Additionally, since hash tables use the key to find the index that will store the value, an insert or lookup can be done in amortised O(1) time (assuming few collisions in the hash table).
• In a hash table, one must also handle potential collisions. This is often done by chaining, which means to create a linked list of all the values whose keys map to a particular index.

A hash table is traditionally implemented with an array of linked lists. When we want to insert a key/Value pair, we map the key to an index in the array using the hash function. The value is then inserted into the linked list at that position.

Note: The elements in the linked list at a particular index of the array do not have the same key. Rather, hash function(key) is the same for these values. Therefore, in order to retrieve the value for a specific key,we need to store in each node both the exact key and the value.

To summarize, a hash table will be implemented with an array of linked lists, where each node in the linked list holds two pieces of data: the value and the original key. In addition, we will want to note the following design criteria:

1. We want to use a good hash function to ensure that the keys are well distributed. If they are not well distributed, then we would get a lot of collision and the speed to find an element would decline.
2. No matter how good hash function is, we will still have collisions, so we need a method for handling them. this often means chaining via a linked list, but it’s not the only way.
3. We may also wish to implement methods to dynamically increase or decrease the hash table size depending on capacity. For example, when the ratio of the number of elements to the table size exceeds a certain threshold, we may wish to increase the hash table size. This would mean creating a new hash table and transferring the entries from the old table to the new table. Because this is an expensive operation, we want to be careful to not do it too often.

STL Map

The container map is an associative container included in the standard library of C++. The definition of this class is in the header file “map” of the namespace std.

It’s implemented as a self-balancing red-black tree. Probably the two most common self balancing trees are red-black tree and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing. While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the RB tree more efficient in this aspect of the re-balancing sage and one of the possible reasons that is more commonly used.

Differences between Hash table and STL map

1. Null Keys: STL Map allows one null key and multiple null values whereas hash table doesn’t allow any null key or value.
2. Thread synchronization: Map is generally preferred over hash table if thread synchronization is not needed. Hash table is synchronized.
3. Thread safe: STL Maps are not thread safe whereas Hashmaps are thread safe and can be shared with many threads.
4. Value Order: In STL map, values are stored in sorted order whereas in hash table values are not stored in sorted order
5. Searching Time: You can use STL Map or binary tree for smaller data( Although it takes O(log n) time, the number of inputs may be small enough to make this time negligible) and for large amount of data, hash table is preferred.

Advantages of BST over Hash Table

Hash Table supports following operations in Θ(1) time.

1. Search
2. Insert
3. Delete

The time complexity of above operations in a self-balancing Binary Search Tree (BST) (like Red-Black Tree, AVL Tree, Splay Tree, etc) is O(Logn).
So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advantages. Following are some important points in favor of BSTs.

1. We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
2. Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs. Like sorting, these operations are not a natural operation with Hash Tables.
3. BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
4. With Self-Balancing BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.