Number of distinct elements in a given range
This is a problem in which we have an integer array which contains some elements and our job is to find out number of distinct elements in a given range. We have solved this using three methods with the most efficient approach being a hashing technique with linear time complexity O(N).
Finding number of pairs with a certain XOR value
In this article, we are going to find the number of pairs in an unsorted array, whose XOR values matches with our target value (say K). Using our efficient approach (with Hash map), we can solve this in O(N) time complexity while the brute force approach takes O(N^2) time complexity
Hash Map / Hash table
Hash map (hash table, unordered map, dictionary, hash set) is a widely used efficient data structure that used to store data which can be searched in constant time O(1). This data structure is implemented over an array that maps keys to values that is it is a set of key value pairs.
Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity
HashMap in Java
In Java, HashMap is a Map based collection class that is used for storing Key and value pairs which is denoted as HashMap. It does not maintain order of elements, allows one null key, multiple null values, is not thread safe, default size is 16, default load factor is 0.75 JDK1.7, JDK1.8