HashTable.md

Hash Tables

• Hash Tables are data structures which store data in an associative manner.
• In a hash table, data is stored in an array format, where each data value has its own unique index value.
• Access of data becomes very fast if we know the index of the desired data.
• In a Hash table it stores information in two main components, i.e., key and value.
• The efficiency of mapping depends upon the efficiency of the hash function used for mapping.

Some important points about hash tables:

1. Values are not stored in a sorted order.
2. You mush account for potential collisions. This is usually done with a technique called chaining. Chaining means to create a linked list of values, the keys of which map to a certain index.

Hashing

• Hashing is one of the searching techniques that uses a constant time. The time complexity in hashing is O(1).

• Till now, we've read the two techniques for searching, i.e., linear search and binary search. The worst time complexity in linear search is O(n), and O(logn) in binary search.

• In both the searching techniques, the searching depends upon the number of elements but we want the technique that takes a constant time. So, hashing technique came that provides a constant time.

• In Hashing technique, the hash table and hash function are used. Using the hash function, we can calculate the address at which the value can be stored.

• The main idea behind hashing is to create (key/value) pairs. If the key is given, then the algorithm computes the index at which the value would be stored. It can be written as:

Index = hash(key)

Features of Hashtables

1. It is similar to HashMap, but is synchronized.
2. Hashtable stores key/value pair in hash table.
3. In Hashtable we specify an object that is used as a key, and the value we want to associate to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.
4. The initial default capacity of Hashtable class is 11 whereas loadFactor is 0.75.
5. HashMaps doesn’t provide any Enumeration, while Hashtable provides not fail-fast Enumeration.

Example

Let hash function H(x) = [11,12,13,14,15]
// it will be stored at positions {1,2,3,4,5}
// in the array or Hash table respectively.

Declaration

1. In c++

 unordered_map<int,int>mp;
 # map named as mp, an unordered map takes lesser time complexity than an ordered map.
for(int i=0;i<arr.size();i++){
    mp[arr[i]]++
}

In this way , map named mp stores the frequency of all elements in array.

2. In Java

Hashtable<Integer, String> hashtableName = new Hashtable<Integer, String>();
hashtableName.put(integer, string);

3. In Python, the Dictionary data types represent the implementation of hash tables. The Keys in the dictionary satisfy the following requirements.

• The keys of the dictionary are hashable i.e. the are generated by hashing function which generates unique result for each unique value supplied to the hash function.

• The order of data elements in a dictionary is not fixed.

Accessing Values in Dictionary To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value.

Example

Declaring a dictionary

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

Accessing the dictionary with its key

print("dict['Name']: ", dict['Name']) print("dict['Age']: ", dict['Age'])