Hash tables: the secret weapon that makes your code 1000 times faster

What is a hash table and why is it needed?

A hash table (or hash map) is a data structure that stores key-value pairs and provides very fast access to data. On average, search, insert, and delete operations are performed in O(1) — constant time. This means that regardless of whether 10 or 10 million elements are stored in the table, access to any of them will take approximately the same time.

A simple example from life:

const userAges = {
    "Alexey": 28,
    "Maria": 25,
    "Dmitry": 32
};

console.log(userAges["Maria"]); // 25 - instant access!

In most modern programming languages, hash tables are built-in: dict in Python, Map in JavaScript, HashMap in Java, map in Go.

How a hash table works

Under the hood, a hash table is a regular array. The magic happens thanks to hash functions, which converts a key (string, number, or object) into an array index.

Workflow:

1. Key hashing: The key (for example, "Alexey") is passed through a hash function that returns a number (for example, 42)

2. Calculating the index: The hash result is converted to an array index using the division remainder operation: index = hash % array.length

3. Saving the value: The value is stored in the array cell with this index

"Alexey" → hash("Alexey") → 1892374 → 1892374 % 10 → index 4 Array: [_, _, _, _, {key: "Alexey", value: 28}, _, _, _, _, _]

Hash functions: the heart of the system

A good hash function should have several properties:

• Determinism — the same key always gives the same hash

• Uniformity — hashes must be evenly distributed throughout the range of values

• Speed — hash calculation must be fast

• Minimizing collisions — different keys must give different hashes

Example of a simple hash function for strings:

function simpleHash(str, tableSize) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
    }
    return hash;
}

console.log(simpleHash("Alexey", 100)); // for example, 67
console.log(simpleHash("Maria", 100));   // for example, 23

In real systems, more complex functions are used, such as MurmurHash, CityHash, or cryptographic functions like SHA-256 (for special cases).

Collisions: when two keys want one place

Collision occurs when two different keys receive the same index after hashing. This is an inevitable problem because the number of possible keys is usually larger than the size of the array.

"Aleksey" → index 4 "Dmitry" → index 4 ← Collision!

Chaining method

The most popular way to resolve collisions. Each cell of the array stores not one value, but a list (chain) of all values with the same index.

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        const index = this._hash(key);
        
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // Checking if such a key already exists
        for (let item of this.table[index]) {
            if (item[0] === key) {
                item[1] = value; // Updating value
                return;
            }
        }
        
        // Adding a new key-value pair
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return undefined;
        
        for (let item of bucket) {
            if (item[0] === key) {
                return item[1];
            }
        }
        
        return undefined;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return false;
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        
        return false;
    }
}

// Use
const users = new HashTable();
users.set("Alexey", { age: 28, city: "Moscow" });
users.set("Maria", { age: 25, city: "St. Petersburg" });
users.set("Dmitry", { age: 32, city: "Novosibirsk" });

console.log(users.get("Maria")); // { age: 25, city: "St. Petersburg" }users.remove("Alexey");
console.log(users.get("Alexey")); // undefined

Open Addressing

Instead of creating chains, in case of a collision we look for another free cell in the array according to a certain algorithm:

Linear punching — check the following cells in a row: index, index+1, index+2...

class HashTableOpenAddressing {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
        this.count = 0;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        if (this.count / this.size > 0.7) {
            this._resize(); // Increase the size when filling >70%
        }

        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined && this.table[index].key !== key) {
            i++;
            index = (this._hash(key) + i) % this.size; // Linear punching
        }

        if (this.table[index] === undefined) {
            this.count++;
        }

        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            i++;
            index = (this._hash(key) + i) % this.size;
        }

        return undefined;
    }

    _resize() {
        const oldTable = this.table;
        this.size *= 2;
        this.table = new Array(this.size);
        this.count = 0;

        for (let item of oldTable) {
            if (item !== undefined) {
                this.set(item.key, item.value);
            }
        }
    }
}

Quadratic perforation — check: index, index+1², index+2², index+3²...

Double hashing — we use the second hash function to calculate the step.

Performance and complexity

Load Factor = number of elements / array size

At load factor > 0.7, it is usually performed rehashing — creating a new larger array and moving all elements.

Real use cases

1. Caching results

class Cache {
    constructor() {
        this.cache = new Map();
    }

    async fetchUser(userId) {
        // Checking cache
        if (this.cache.has(userId)) {
            console.log('Received from cache');
            return this.cache.get(userId);
        }

        // Loading data
        const user = await api.getUser(userId);
        
        // Saving to cache
        this.cache.set(userId, user);
        
        return user;
    }
}

2. Counting the frequency of elements

function countWords(text) {
    const wordCount = new Map();
    const words = text.toLowerCase().split(/\s+/);

    for (let word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "JavaScript is a programming language JavaScript is popular";
console.log(countWords(text));
// Map { 'javascript' => 2, 'this' => 1, 'language' => 1, ... }... }

3. Search for duplicates

function hasDuplicates(arr) {
    const seen = new Set();
    
    for (let item of arr) {
        if (seen.has(item)) {
            return true;
        }
        seen.add(item);
    }
    
    return false;
}

console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

4. Indexing in databases

Databases use hash indexes to quickly search for records by key:

-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);

-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';

5. Unique user identifiers

class Session {
    constructor() {
        this.sessions = new Map();
    }

    createSession(userId) {
        const sessionId = this.generateSessionId();
        this.sessions.set(sessionId, {
            userId,
            createdAt: Date.now(),
            data: {}
        });
        return sessionId;
    }

    getSession(sessionId) {
        return this.sessions.get(sessionId);
    }

    destroySession(sessionId) {
        this.sessions.delete(sessionId);
    }

    generateSessionId() {
        return Math.random().toString(36).substring(2);
    }
}

6. Routing in web frameworks

class Router {
    constructor() {
        this.routes = new Map();
    }

    addRoute(path, handler) {
        this.routes.set(path, handler);
    }

    handleRequest(path) {
        const handler = this.routes.get(path);
        
        if (handler) {
            return handler();
        }
        
        return 'Not Found';
    }
}

const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');

console.log(router.handleRequest('/home')); // Home Page - O(1)!

7. Anagrams and grouping of lines

function groupAnagrams(words) {
    const groups = new Map();

    for (let word of words) {
        // Sorting letters as a key
        const key = word.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Map vs Object in JavaScript: which one to choose?

JavaScript offers two ways to work with hash tables:

Object:

const obj = {};
obj.name = "Alexey";
obj['age'] = 28;

Map:

const map = new Map();
map.set('name', 'Alexey');
map.set('age', 28);

When to use Map:

• Keys are not strings (objects, numbers, functions)

• Iteration is required in the order of addition

• Frequent additions/deletions of elements

• You need to know the exact number of elements (map.size)

When to use Object:

• Keys are always strings

• You need JSON.stringify/parse

• Simple configuration structure

Practical advice

1. Choose the right initial size

// If you know that there will be ~1000 items
const map = new Map(); // Default small size
// vs
const users = new HashTable(2000); // Avoid rehashing

2. Be careful with objects like keys

const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };

map.set(key1, 'value1');
console.log(map.get(key2)); // undefined! Different objects

3. Clean up unused data

// Use WeakMap for automatic cleaning
const cache = new WeakMap();
let user = { name: 'Alexey' };

cache.set(user, 'some data');
user = null; // Data will be automatically deleted from WeakMap

Conclusion

Hash tables are a fundamental data structure that is used everywhere: from databases to web frameworks, from compilers to search engines. Understanding their structure, ways to resolve collisions and performance makes you a more effective developer.

In Codice we analyze not only hash tables, but also dozens of other important topics for developers: from the basics to advanced techniques. Our courses include practical tasks and real cases from the industry.

Join our Telegram channel — here you will find a friendly community of developers, useful materials every week, analysis of interesting tasks and answers to questions.

Let's grow together! 🚀