Hashing in Competitive Programming for Java Programmers
Java has HashMaps with a hashing function which is applied to the key to calculate the index of the bucket in order to store and retrieve any key-value pair. The Capacity of HashMap is the number of buckets in it. Initially, the capacity of HashMap is 16. As the number of elements in the HashMap increases, the capacity gets increased. This is handled with the help of Load Factor. The load factor is the measure that decides when to increase the capacity of the Map. The default load factor is 75% of the capacity.
HashMap stores and retrieves entries in constant time O(1). However, the problem arises when the number of items is increased, and the number of buckets is fixed, which can increase the time complexity from O(1) to O(N). This can be solved by increasing the number of buckets and redistributing the items across all the buckets. In this way, we’ll be able to keep a constant number of items in each bucket and maintain the time complexity of O(1). With a lower load factor, there will be more free buckets and, hence, fewer chances of a collision. This will help us to achieve better performance for our Map. Hence, we need to keep the load factor low to achieve low time complexity.
Note: A higher value of load factor decreases the space overhead but increases the lookup cost.
Prior to Java 8, HashMap in Java used a LinkedList to store map entries when collisions occurred. This could lead to worst-case performance of O(n), which is not ideal. Java 8 and later versions addressed this issue by using a balanced tree, also known as a red-black tree, to store collided entries. This improves the worst-case performance of HashMap to O(log n), which is a significant improvement.
The TREEIFY_THRESHOLD constant determines when HashMap switches from using a LinkedList to a balanced tree. The current value of this constant is 8, meaning that if there are more than 8 elements in the same bucket, HashMap will use a tree to store them. This ensures that the LinkedList is not used for excessively large buckets, preventing performance degradation.
Java also offers a data structure as TreeMap which is used to store unique elements in a sorted order. Java.util.TreeMap uses a red-black tree in the background which makes sure that there are no duplicates. Additionally, it also maintains the elements in a sorted order. It takes the time complexity of log(N) to insert, delete or retrieve elements from TreeMap.
How to handle collision attacks?
Java handles collisions in its HashMap implementation without requiring users to create custom hash functions. The HashMap class in Java uses a combination of techniques to handle collisions and ensure efficient key-value storage. The key approach is employing separate chaining, which means that each bucket in the hash table is implemented as a linked list. When a collision occurs (i.e., multiple keys hash to the same bucket), the corresponding entries are stored in the linked list associated with that bucket.
Below is an example of Hashing in Competitive Programming for Java:
#include <iostream>
#include <unordered_map>
int main() {
// Create a new unordered_map object
std::unordered_map<std::string, int> myMap;
// Add some key-value pairs to the unordered_map
myMap["apple"] = 1;
myMap["banana"] = 2;
myMap["cherry"] = 3;
// Print the unordered_map
std::cout << "Original unordered_map: ";
for (const auto& pair : myMap) {
std::cout << "{" << pair.first << ": " << pair.second << "} ";
}
std::cout << std::endl;
// Get the value associated with the key "banana"
int value = myMap["banana"];
// Print the value
std::cout << "Value of key 'banana': " << value << std::endl;
// Remove the key-value pair associated with the key "cherry"
myMap.erase("cherry");
// Print the unordered_map again
std::cout << "Updated unordered_map: ";
for (const auto& pair : myMap) {
std::cout << "{" << pair.first << ": " << pair.second << "} ";
}
std::cout << std::endl;
return 0;
}
// code is contributed by utkarsh
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// Create a new HashMap object
HashMap<String, Integer> myMap = new HashMap<String, Integer>();
// Add some key-value pairs to the HashMap
myMap.put("apple", 1);
myMap.put("banana", 2);
myMap.put("cherry", 3);
// Print the HashMap
System.out.println("Original HashMap: " + myMap);
// Get the value associated with the key "banana"
int value = myMap.get("banana");
// Print the value
System.out.println("Value of key 'banana': " + value);
// Remove the key-value pair associated with the key "cherry"
myMap.remove("cherry");
// Print the HashMap again
System.out.println("Updated HashMap: " + myMap);
}
}
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// Create a new Dictionary object
Dictionary<string, int> myMap = new Dictionary<string, int>();
// Add some key-value pairs to the Dictionary
myMap["apple"] = 1;
myMap["banana"] = 2;
myMap["cherry"] = 3;
// Print the Dictionary
Console.Write("Original Dictionary: ");
foreach (var pair in myMap)
{
Console.Write("{" + pair.Key + ": " + pair.Value + "} ");
}
Console.WriteLine();
// Get the value associated with the key "banana"
int value = myMap["banana"];
// Print the value
Console.WriteLine("Value of key 'banana': " + value);
// Remove the key-value pair associated with the key "cherry"
myMap.Remove("cherry");
// Print the Dictionary again
Console.Write("Updated Dictionary: ");
foreach (var pair in myMap)
{
Console.Write("{" + pair.Key + ": " + pair.Value + "} ");
}
Console.WriteLine();
}
}
// Create a new Map object
let myMap = new Map();
// Add some key-value pairs to the Map
myMap.set("apple", 1);
myMap.set("banana", 2);
myMap.set("cherry", 3);
// Print the Map
console.log("Original Map:");
for (let [key, value] of myMap) {
console.log(`{${key}: ${value}}`);
}
// Get the value associated with the key "banana"
let value = myMap.get("banana");
// Print the value
console.log("Value of key 'banana':", value);
// Remove the key-value pair associated with the key "cherry"
myMap.delete("cherry");
// Print the Map again
console.log("Updated Map:");
for (let [key, value] of myMap) {
console.log(`{${key}: ${value}}`);
}
# Create a new dictionary
my_dict = {}
# Add some key-value pairs to the dictionary
my_dict["apple"] = 1
my_dict["banana"] = 2
my_dict["cherry"] = 3
# Print the dictionary
print("Original dictionary:", my_dict)
# Get the value associated with the key "banana"
value = my_dict["banana"]
# Print the value
print("Value of key 'banana':", value)
# Remove the key-value pair associated with the key "cherry"
my_dict.pop("cherry", None)
# Print the dictionary again
print("Updated dictionary:", my_dict)
#this code is contributed by Kishan
Output
Original unordered_map: {cherry: 3} {banana: 2} {apple: 1}
Value of key 'banana': 2
Updated unordered_map: {banana: 2} {apple: 1}
Hashing in Competitive Programming
Hashing is a fundamental technique in competitive programming that is used to efficiently manipulate and process large amounts of data. Data Structures like Hash Maps and Hash Sets use hashing techniques to provide faster insertion, deletion and retrieval of values.
Table of Content
- What is Hashing?
- Why use Hashing in Competitive Programming?
- Advantages of Hashing
- Disadvantages of Hashing
- Common Hash Functions and Collision Handling Techniques
- Use Cases of Hashing in Competitive Programming
- Hashing in Competitive Programming for C++ Programmers
- Hashing in Competitive Programming for Java Programmers
- Hashing in Competitive Programming for Python Programmers
- Practice Problems on Hashing for Competitive Programming