Go To Problems

☰

Level 5

Hashing

TUTORIAL

1. Introduction To Hashing

2. Key Terms In Hashing

3. Hashing Techniques

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

Welcome to Interviewbit, help us create the best experience for you!

Few details about your education

Few details about your education

Few details about your career...

You're all set!

Begin your success journey!

Welcome back!

Level 5

Hashing

Hashing Implementation Details

C

C++ :

Declaration

Adding an key, value pair :

Find the value for key = K:

Size ( number of elements ) of the vector :

Erase from the map :

JAVA :

Declaration :

Adding an key, value pair :

Find the value for key = K:

Size ( number of elements ) of the vector :

Erase from the map :

PYTHON

Declaration :

Adding an key, value pair :

Find the value for key = K:

Size ( number of elements ) of the vector :

Erase from the map :