Hashing

TUTORIAL

1. Introduction To Hashing

2. Hash Tables

3. Hash Functions

4. Hashing Implementation Details

Hashing Implementation Details

C

C has nothing native for hashmap We need to write one ourselves.

C++ :

C++ has unordered_map which is implemented via hashing. We will discuss treemaps in C++ as well later, which in practice seem to behave faster in C++.

Declaration

    unordered_map<int, int> A; // declares an empty map. O(1)

Adding an key, value pair :

    A.insert(key, value); // O(1) time on average

Find the value for key = K:

    if (A.find(K) == A.end()) return null; //  means that K does not exist in A. 
    else return A[K];    // O(1) average case. Rare worst case O(n).

Size ( number of elements ) of the vector :

    A.size()  // O(1)

Erase from the map :

    if (A.find(K) != A.end()) A.erase(A.find(K));
     OR A.erase(K);

JAVA :

Now we come to one of the most popular data structures in Java, HashMap.

Declaration :

    HashMap<Integer, Integer> A = new HashMap<Integer, Integer>(); // declares an empty map.

Adding an key, value pair :

    A.put(key, value); // O(1) time on average

Find the value for key = K:

    A.get(K) // null if the key K is not present
    A.containsKey(K) tells if the key K is present. 
    // Both operations O(1) average time. O(n) rare worst case

Size ( number of elements ) of the vector :

    A.size()  // O(1)

Erase from the map :

    A.remove(K);

PYTHON

Python has dictionaries which serve the same purpose.

Declaration :

    A = {}

Adding an key, value pair :

    A[key] = value // O(1) average time. O(n) worst case

Find the value for key = K:

    A[K] // O(1) average, O(n) worst

Size ( number of elements ) of the vector :

    len(A) // O(1)

Erase from the map :

        del A[K] // O(1) average, O(n) worst