Hash maps :

Following the course Google data & algorithms

Maps and Doctionaries

Arrays: allow us to store elements of the same type in memory. It is possible to access each element just by indicating its index. When creating the array we need to specify its size.

Linked list: This data structure can grow, since each component contains a value and a pointer to the next value

The draw back of having a dynamic size with linked lists is that we lose random access of elements. To find an element it is necessary to go through all the linked list. The worst case scenario is o(n) which isn't efficient.

Hash tables : this data structure is adapted for insert, delete and lookup opertations :

A hash table data structure has a key and value. The key is hashed through a consistent hash function. By consistant, I mean that it will always return the same result for the same input key. The hash function indicates where in the hash table the element is. For example the hash function bellow puts elements in the hash table according to their alphabetical order

Since we already know where each element should be according to its hashed key, we only need to lookup a single part of the table.

• The complexity of inserting an element in a hashmap is : o(1)
• The complexity of searching an element in a hashmap is : o(n)

##collisions

If we have another element is the hashmap that the hash function locates in the asme place as an already existing element, a collision happens.

A soltion is to use separate chaining.The hash table is a list of pointers to linked lists.

In worst case scenario we would have a maximum of o(n/k). This represents a significant improvment compared to o(n).

Difference between a hashSet and HashMap

HashSet uses HashMap for its implementation. Objects inserted in hashSets are actually hashMap keys with a value of a dummy object. HashSet:

• implements the Set interface allow on one null value and no duplicate values
• we can't access an element in a hashSet directly we need to iterate every time as there is no get function
• You can directly add an element to the hashet with the method add(). THIS METHOD RETURNS TRUE IF THE ELEMENT DOESN'T EXIST IN THE HASHSET AND FALSE IF IT DOES

HashMap:

• contains a pair of key values and values can be accessed directly through their key
• HashMap can contain duplicate values but not keys

Both HashMap and HashSet can't have a non primitive type in the key they take Integer not int

Iterating over a Hashmap

There are two main ways to iterate over a hashmap :

    for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
        System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");
    }

Or Set entrySet = hashmap.entrySet(); Iterator it = entrySet.iterator(); System.out.println("HashMap Key-Value Pairs : "); while(it.hasNext()){ Map.Entry me = (Map.Entry)it.next(); System.out.println("Key is: "+me.getKey() + " & " + " value is: "+me.getValue()); }

The me.getValue is of type Object, it is necessary to cast it to the used Type

Put syntax :

hashMap.put(*key*, *value*);

hashMaps are not ordered when we iterate over them the order is not kept !!

to check if a hashmap contains a key :

Hash_Map.containsKey(key_element)

to get an element :

Hash_Map.get(Object key_element)

Examples of the usage of hashmaps in real life

The use of Hash maps can be very tricky. For example to groupe anagrams (exercise and answer available) I had to use the sorted string as a key to group the words It is way easier than using an array