Hashing It Out
HashMap
Few Methods used:-
· remove(key) — removes the key-value pair associated with a given key.
· containsKey(key) — checks if the HashMap contains a given key.
· containsValue(value) — checks if the HashMap contains a given value.
· keySet() — returns a set of all the keys in the HashMap.
· values() — returns a collection of all the values in the HashMap.
· entrySet() — returns a set of all the key-value pairs in the HashMap.
· size() — returns the number of key-value mappings in the HashMap.
· clear() — removes all of the mappings from the HashMap.
· isEmpty() — returns boolean
· putIfAbsent(key, value) — adds a key-value pair to the HashMap only if the key is not already present in the map.
· replace(key, oldValue, newValue) — replaces the value of a key-value pair with a new value only if the old value matches the specified value.
Technique of Hashing:-
1. Quadratic Probing:
Quadratic probing is a collision resolution technique used in open addressing hash tables.
How Quadratic Probing is done?
If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
This process is repeated for all the values of i until an empty slot is found.
Formula=> Next Index = (Hashed Index + c1 * i²) % Table Size
Where:
· Next Index is the index you want to probe next.
· Hashed Index is the original index where the key hashed to.
· c1 constant that is typically chosen to avoid clustering
· i is the iteration number, starting from 0
· Table Size is the size of the hash table.
2. Linear Probing:
open addressing hash tables. It searches for the next available slot by incrementing the current index linearly (by a fixed constant) until an empty slot is found.
3. Separate Chaining:
closed addressing hash tables. In this approach, each hash table slot contains a linked list, and when a collision occurs, the new key-value pair is simply added to the list at the hashed index.
Problem statements where hashmaps can be used?
- Counting frequency of elements —
Suppose you have an array of elements, and you want to count the occurrence of each element.
Eg:== int[] arr = { 1, 2, 4, 1, 3, 5, 4, 2 };
Approach
Using HashMap we can count how many times each element has occurred. Iterates over the arr array checks if the element is already present using the containsKey() method. If it is, then increments the count for that key by 1 using the put() method. If it is not, it adds the key to the HashMap with a count of 1.
2. Checking for duplicates-
Given an array of integers or strings, [2, 4, 6, 8, 4, 10, 2] . we can use a hashmap to check for duplicates.
Approach
· Create an empty hashmap.
· Loop through the elements of the array.
· For each element, check if it is present in the hashmap.
· If the element does not exist in the hashmap, add it as a key with value True.
· If the element already exists in the hashmap, then we have found a duplicate.
· Else not
3. Storing data-
If we need to store a large amount of data and access it quickly, then hashmaps are a good choice. We can use the keys to access the values, which can be anything from simple integers to complex objects.
4. Finding pairs with given sum-
Given an array of integers and a target sum, we can use a hashmap to find pairs of integers that add up to the target
Eg:= an array of integers: [2, 4, 6, 8, 10, 12]. We want to find all pairs of integers in the array that add up to a target sum of 10.
Approach
· Create an hashmap.
· Loop through the elements of the array.
· For each element target sum minus the current element.(assign a variable for this calculation) eg:= sub
· Check if the sub exists in the hashmap.
· If the sub exists in the hashmap, then we have found it. Return it using get() method.
· If no element adds up to target element then return empty integer array.
Best practices that you should follow while using hashmaps:
1. Choose the right key type — The key in a HashMap must be unique, use immutable types as keys
2. Handle collisions — In a HashMap, two keys can have the same hash code, which is called a collision.
3. Avoid using null keys — Null keys are allowed in a HashMap, but Avoid using null keys, they can lead to unexpected behaviour.
4. Use an appropriate load factor — The load factor determines the point at which the HashMap will resize itself. Choose a load factor that balances performance with memory usage.
The Application of Hashing:
1. Databases: Hashing is a useful technique for effectively indexing and searching big databases.
2.Cryptography: Message digests, which are used to confirm data integrity and guard against manipulation, are created using hash functions.
3.Caching: To store frequently requested data and enhance speed, caching systems employ hash tables.
4.Spell checking: Hashing is a technique used by spell checkers to find terms in dictionaries fast.
5.Network routing: To spread network traffic among several servers, load balancing and routing algorithms employ hashing.
Time Complexity: O(1)
Space Complexity: O(N)
HashSet
Methods used in Hashset
· add(element): adds an element to the set. If the element is already present it is not added again.
· remove(element): This method removes the specified element from the set if it is present.
· contains(element): This method returns true if the set contains the specified element, and false otherwise.
· size(): returns the number of elements in the set.
· containsAll(Collection<?> c): This method returns true if the set contains all the elements in the specified collection. (The <?> means that the collection can contain elements of any type.)
· clear(): removes all the elements from the set.
· isEmpty(): returns true if the set is empty, and false otherwise.
· iterator(): returns an iterator over the elements in the set.
· equals(Object o): This method compares the specified object with the set for equality. It returns true if the object is also a set, has the same size, and contains the same elements as the set.
· removeAll(Collection<?> c): removes all the elements from the set that are contained in the specified collection.
· retainAll(): modifies the current set to contain only the elements that are also in the specified set.
Problem Statement where Hashset can be used??
- Checking for common elements between two sets:
You can create two HashSet objects and use the retainAll() method to find the common elements between the two sets.
Approach
Eg:== set1: {1, 2, 3, 4} and set2: {3, 4, 5, 6}. We want to find the common elements between the two sets, which are {3, 4}.
1. We shall create hashset
2. use retainAll (set1 now contains only the common elements, which are {3, 4})
3. set1.retainAll(set2)
2. Storing a collection of user inputs:
You can create a HashSet to store the user inputs in order to ensure that there are no duplicates, and to make it easy to check if a particular input is already present in the collection.
3. Implementing a spell checker:
You can use a HashSet to store a dictionary of words, and then check if a given word is in the dictionary by using the contains() method. This can be useful for implementing a simple spell checker.
4. Finding the union or difference between two sets:
You can create two HashSet objects and use the addAll() method to find the union of the two sets, or the removeAll() method to find the difference between the two sets.
Best practices that you should follow while using hashmaps:
1. Specify the type of element : While declaring a HashSet, you should use generics to specify the type of elements the set will contain. For example, if you want to create a set of String objects HashSet<String>.
2. Override hashCode() and equals(): you should override the hashCode() and equals() methods to ensure that the elements are properly compared and hashed. Because hashCode() and equals() methods to determine if two objects are equal.
3. Use add() to insert elements:. If you try to insert a duplicate element, the HashSet will simply ignore it and return false.
4. Use contains():This method has constant time complexity and is very efficient.
5. Use remove(): Use the remove() method to remove an element from the HashSet. If the element is not present the method will simply return false.
6. Avoid modifying the set while iterating: you should not modify the set while iterating using a iterator. Doing so can cause a ConcurrentModificationException.
Time Complexity: add(), remove() and contains() operations cost constant O(1) time
Space Complexity: O(1) — it uses a constant amount of space when it iterates over the HashSet.
