Java HashMap implementation
The HashMap has an array of linked lists (buckets) to store key-value pairs.
The size variable keeps track of the number of key-value pairs in the HashMap.
The getBucketIndex method calculates the index in the array (buckets) where a key-value pair should be stored based on the hash code of the key.
The put method adds a key-value pair to the HashMap.
It first checks if the key already exists in the linked list. If yes, it updates the value; otherwise, it adds a new entry.
If the size exceeds 75% of the capacity, it triggers a resize operation to maintain efficiency.
The get method retrieves the value associated with a given key. It searches through the linked list in the corresponding bucket.
import java.util.LinkedList;
public class MyHashMap
{
private static final int DEFAULT_CAPACITY = 16;
private LinkedList>[] buckets;
private int size;
public MyHashMap() {
this(DEFAULT_CAPACITY);
}
public MyHashMap(int capacity) {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
size = 0;
}
private int getBucketIndex(K key) {
return key.hashCode() % buckets.length;
}
public void put(K key, V value) {
int index = getBucketIndex(key);
LinkedList> bucket = buckets[index];
// Check if key already exists, and update the value
for (Entry entry : bucket) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
// Key not found, add a new entry
bucket.add(new Entry<>(key, value));
size++;
// Resize if necessary
if ((double) size / buckets.length > 0.75) {
resize();
}
}
public V get(K key) {
int index = getBucketIndex(key);
LinkedList> bucket = buckets[index];
for (Entry entry : bucket) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null; // Key not found
}
public void remove(K key) {
int index = getBucketIndex(key);
LinkedList> bucket = buckets[index];
for (Entry entry : bucket) {
if (entry.key.equals(key)) {
bucket.remove(entry);
size--;
return;
}
}
}
private void resize() {
int newCapacity = buckets.length * 2;
LinkedList>[] newBuckets = new LinkedList[newCapacity];
for (int i = 0; i < newCapacity; i++) {
newBuckets[i] = new LinkedList<>();
}
for (LinkedList> bucket : buckets) {
for (Entry entry : bucket) {
int newIndex = entry.key.hashCode() % newCapacity;
newBuckets[newIndex].add(entry);
}
}
buckets = newBuckets;
}
public int size() {
return size;
}
private static class Entry {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap<>();
// Adding key-value pairs
myHashMap.put("One", 1);
myHashMap.put("Two", 2);
myHashMap.put("Three", 3);
// Accessing values
System.out.println("Value corresponding to key 'Two': " + myHashMap.get("Two"));
// Removing a key-value pair
myHashMap.remove("Two");
System.out.println("After removing key 'Two': " + myHashMap);
// Checking size
System.out.println("Size of HashMap: " + myHashMap.size());
}
}
Summary:This implementation uses separate chaining to handle collisions, and it includes a basic resizing
mechanism to maintain efficiency.
Java LinkedList Implementation
The Node class is a static inner class representing an element in the linked list.
It has a data field to store the value of the node and a next field to reference the next node in the list.
The constructor is used to initialize a node with a given data value.
The LinkedList class is the main class representing the linked list.
It has a private instance variable head, which points to the first node in the list.
The add method adds a new node with the given data to the end of the linked list.
If the list is empty (head == null), the new node becomes the head.
Otherwise, it traverses the list until it reaches the last node and appends the new node to the next
reference of the last node.
The remove method removes the first occurrence of a node with the specified data.
If the node to be removed is the head, it updates the head to the next node.
Otherwise, it traverses the list until it finds the node with the specified data and adjusts the next
reference to skip that node.
public class LinkedList {
private Node head;
private static class Node {
T data;
Node next;
Node(T data) {
this.data = data;
this.next = null;
}
}
public void add(T data) {
Node newNode = new Node<>(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void remove(T data) {
if (head == null) {
return;
}
if (head.data.equals(data)) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && !current.next.data.equals(data)) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList myList = new LinkedList<>();
myList.add(1);
myList.add(2);
myList.add(3);
System.out.println("Original Linked List:");
myList.printList();
myList.remove(2);
System.out.println("Linked List after removing 2:");
myList.printList();
}
}
Post a Comment