Data Structures. Hash Tables

Basic information

This is a short expanded summary of the section about hash tables in the book Computer Science Guide by William Springer.

A hash table is an array where the index is determined by the stored element or its key.

The first component of a hash table is the hash function. It converts the element’s key (a string or number of fixed length) into an array index. Each key corresponds to a specific position in the table.

Some hashing algorithms:

• CRC32
• MD5
• SHA

Only one instance of each element is allowed.

In JavaScript, since 2015, Map() was introduced — a hash map. It provides key/value functionality. In a Map, keys can be of any type, not only strings or integers as in traditional hash tables.

However, Map objects cannot be directly converted to JSON.

Collision resolution

1) Chaining method

Each cell is treated as a collection of objects stored as a linked list (which must be traversed to find the correct value).

The size of a chained hash table is not limited, but performance decreases as more elements accumulate in a single bucket.

2) Open addressing

Nearby cells are checked until an empty one is found, and the value is placed there. In this case, the table has a fixed maximum size. Once all cells are filled, no new elements can be inserted..

Use cases

When to use

Hash tables are used when fast direct access to unsorted data by key is needed, and a fast hashing function exists for each object (and the objects themselves are not used as keys).

Examples:

• indexing large datasets (databases)
• authentication systems
• search systems
• caching
• implementation of unordered sets

When not to use

• when sorted order must be preserved
• when data is poorly distributed (many elements map to the same buckets)
• when frequent access to sequential blocks of data is required

JavaScript implementation

The way a hash table is organized depends on whether the priority is to minimize collisions (when multiple values end up in the same bucket) or to minimize memory usage.

The more memory allocated to the table, the lower the probability of collisions. If there are no collisions, inserting or retrieving an element takes O(1) time. However, if collisions occur, the worst-case time complexity for these operations is O(n).

The implementation example is taken from this article.

1// For the size of a hash table, prime numbers are often used (numbers that are divisible only by 1 and by themselves). It is believed that this results in fewer collisions.
2const hashTableSize = 32;
3
4class HashTable {
5	constructor() {
6		this.table = new Array(hashTableSize);
7	}
8
9	// Hash function
10	hashFunction(key) {
11		let hash = Array.from(key).reduce((sum, key) => {
12			//The charCodeAt() method returns the Unicode value of the character at the specified index (except for Unicode code points greater than 0x10000).
13			return sum + key.charCodeAt(0);
14		}, 0);
15		return hash % hashTableSize;
16	}
17
18	// Add a new key-value pair
19	set(key, value) {
20		// Calculate the hash for the key
21		let memoryLocation = this.hashFunction(key);
22		// If there is no list for this hash yet, create one
23		if (!this.table[memoryLocation]) {
24			this.table[memoryLocation] = [];
25		}
26
27		// Check whether the key has already been added
28		let node = this.table[memoryLocation].find((array) => array[0] === key);
29
30		if (node) {
31			node[1] = value; // Update the value for the key
32		} else {
33			this.table[memoryLocation].push([key, value]); // Add a new element to the end of the list
34		}
35	}
36
37	// Find a value by key
38	get(key) {
39		let memoryLocation = this.hashFunction(key);
40		if (!this.table[memoryLocation]) return null;
41
42		return this.table[memoryLocation].find((x) => x[0] === key)[1];
43	}
44}

This example demonstrates collision handling using the chaining method based on linked lists.