Introduction
Hi guys! Welcome you onboard to my first blog post here at https://hasithaabewardana.blogspot.com. Today we are going to look at one of the important data structures which are the "Hash Tables". The hash table uses key-value pairs to store data and it has a fast lookup, insert, and delete operations with the time complexity of O(1). The hash tables use a function called hash to generate a fixed-length key based on a given key.
Operations
Lookup (Time complexity: O(1))
Insert (Time complexity: O(1))
Delete (Time complexity: O(1))
Issues and limitations
If we pass the same key for the hash function, it will give the same hashed key, therefore, it may occur an issue called "Hash Collision". We can handle that collision using various techniques such as chaining with Linked Lists etc.
Implementation
Java-based implementation
Hash tables, also known as hash maps, are widely used in Java for various purposes due to their efficient key-value data storage and fast access time. Some common use cases of hash tables in Java are:
- Caching: Hash tables are commonly used for caching frequently accessed data. By storing computed or retrieved values in a hash table with keys as input parameters, you can quickly check if a value has been computed before and return it directly without re-computing it.
- Data Lookup: Hash tables are efficient for data lookup operations. For example, you can use a hash table to store data that needs to be retrieved quickly based on unique identifiers such as user IDs or product IDs.
- Counting and Frequency Analysis: Hash tables can be used to count occurrences of elements in a dataset. For example, you can use a hash table to count the frequency of words in a text document.
- Associative Arrays: In Java, hash tables are often used to implement associative arrays or dictionaries, where you can associate values with specific keys for easy retrieval.
- Symbol Tables: Hash tables are used in compiler design and symbol tables for quickly storing and retrieving identifiers in programming languages.
- Memoization: Hash tables can be used for memoization, a technique used to cache results of expensive function calls to avoid redundant calculations.
- Caching API Responses: In web development, hash tables can be used to cache API responses to avoid unnecessary network requests and improve the application's performance.
Overall, hash tables are valuable data structures in Java for handling scenarios that require fast lookup and retrieval of data based on keys. They are widely used in many applications and libraries to optimize data storage and retrieval operations.
Class KeyValuePair
package datastructures.nonlinear.hashtables;
public class KeyValuePair {
String key;
int value;
public KeyValuePair(String key, int value) {
this.key = key;
this.value = value;
}
}
Class HashTable
package datastructures.nonlinear.hashtables;
import java.util.LinkedList;
public class HashTable {
private final int size;
private final LinkedList<KeyValuePair>[] table;
public HashTable(int size) {
this.size = size;
this.table = new LinkedList[size];
}
private int hash(String key) {
int hash = 0;
for (int i = 0; i < key.length(); i++) {
hash = (hash + key.charAt(i)) % size;
}
return hash;
}
public void put(String key, int value) {
int index = hash(key);
if (table[index] == null) {
table[index] = new LinkedList<>();
}
for (KeyValuePair pair : table[index]) {
if (pair.key.equals(key)) {
pair.value = value;
return;
}
}
table[index].add(new KeyValuePair(key, value));
}
public int get(String key) {
int index = hash(key);
if (table[index] != null) {
for (KeyValuePair pair : table[index]) {
if (pair.key.equals(key)) {
return pair.value;
}
}
}
return -1; // Not found
}
}
Class HashTableDemo
package datastructures.nonlinear.hashtables;
public class HashTableDemo {
public static void demoHashTable() {
HashTable hashTable = new HashTable(10);
hashTable.put("apple", 10);
hashTable.put("banana", 20);
hashTable.put("orange", 15);
System.out.println(hashTable.get("apple")); // Output: 10
System.out.println(hashTable.get("banana")); // Output: 20
System.out.println(hashTable.get("orange")); // Output: 15
System.out.println(hashTable.get("grape")); // Output: -1 (Not found)
}
}
JavaScript-based implementation
JavaScript-specific hash table use cases are similar to the general hash table use cases but tailored to the specific nature of JavaScript and its use in web development. Some JavaScript-specific hash table use cases include:
- Object Literal (Plain Object): In JavaScript, objects can be used as hash tables. Object literals are commonly used to store and access data based on keys (property names). This is a fundamental use case of hash tables in JavaScript.
- Caching DOM Elements: Hash tables can be used to cache frequently accessed DOM elements in web development. Storing DOM elements with unique IDs as keys allows for quick access and manipulation of the DOM without redundant lookups.
- Event Handling and Event Delegation: Hash tables can be used to manage event listeners in JavaScript, where the event types are the keys, and the corresponding values are the event handler functions.
- URL Routing in Single-Page Applications (SPAs): In SPAs, hash tables can be used to implement client-side routing. The hash part of the URL (after the #) is used to map to different views or components in the application.
- Storing Data for State Management: Hash tables can be used in state management libraries like Redux or Vuex to store and retrieve application state efficiently.
- Caching API Responses in Local Storage: In web applications, hash tables can be used to cache API responses in local storage to avoid making unnecessary network requests on subsequent page visits.
- Implementing Hash Sets: Hash tables can be used to implement sets in JavaScript, providing an efficient way to check for the existence of an element in a collection.
- Implementing Hash Maps: Hash tables can be used to implement maps in JavaScript, where keys and values are associated, allowing for efficient key-value pair lookups.
- Implementing JavaScript Data Structures: Hash tables can be used to implement various JavaScript data structures like hash sets, hash maps, and symbol tables.
Overall, JavaScript-specific hash table use cases are centered around web development, DOM manipulation, event handling, and client-side state management. They leverage JavaScript's object literal as a hash table and are integral to building modern web applications with dynamic and interactive features.
Class HashTable
class HashTable {
// Constructor
constructor(size) {
this.data = new Array(size);
}
// Hash function
// O(1)
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
// Method to set values
// O(1)
set(key, value) {
let address = this._hash(key);
if (!this.data[address]) {
this.data[address] = [];
}
this.data[address].push([key, value]);
console.log(this.data);
}
// Method to get values
// O(1) for good hash functions
get(key) {
let address = this._hash(key);
const currentBucket = this.data[address];
if (currentBucket) {
for (let i = 0; i < currentBucket.length; i++) {
if (currentBucket[i][0] === key) {
console.log(currentBucket[i][1]);
}
}
}
return undefined;
}
// Get keys of the hash table
keys() {
const keysArray = [];
for (let i = 0; i < this.data.length; i++) {
if (this.data[i]) {
keysArray.push(this.data[i][0][0]);
}
}
console.log(keysArray);
}
// Keys without collision
keysWithoutCollision() {
if (!this.data.length) {
return undefined;
}
let result = [];
// loop through all the elements
for (let i = 0; i < this.data.length; i++) {
// if it's not an empty memory cell
if (this.data[i] && this.data[i].length) {
// but also loop through all the potential collisions
if (this.data.length > 1) {
for (let j = 0; j < this.data[i].length; j++) {
result.push(this.data[i][j][0]);
}
} else {
result.push(this.data[i][0]);
}
}
}
console.log(result);
}
}
const myHashTable = new HashTable(50);
myHashTable.set("grapes", 10000);
myHashTable.set("apples", 50);
myHashTable.get("grapes");
myHashTable.get("apples");
myHashTable.keys();
myHashTable.keysWithoutCollision();
Post a Comment