CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 4 of 7 · 2 min read

Hash table

Think of it this way. A mail room has 1,024 pigeonholes. A letter goes to the hole given by a number worked out from its address, so a search looks in one hole, not in all. If one clerk may be in the room at a time, the room is safe and slow. The analogy stops in one place: pigeonholes are fixed in size, and the chains here grow with the number of keys.

In plain words: A hash table keeps keys in an array of buckets. A function maps a key to a bucket number (here, the key modulo 1,024). Each bucket holds a linked list of the keys that map to it, so an insert or lookup examines one list. This design is chaining.

A thread-safe (concurrent) table makes its operations safe to call from several threads at once. The simplest way is one mutex around every operation (the coarse locking of page 3). The test: the total work is 200,000 inserts and 200,000 lookups of distinct keys, split among the threads, so that every thread works on keys of its own (no logical conflicts), in a table of 1,024 buckets:

void insert(long k) {
    struct node *n = malloc(sizeof *n);  n->key = k;
    pthread_mutex_lock(&table_lock);                    /* one lock for the whole table */
    n->next = bucket[k % BUCKETS];  bucket[k % BUCKETS] = n;
    pthread_mutex_unlock(&table_lock);
}

The correctness check: after every run, the table held exactly 200,000 keys and every lookup found its key. The times (median of 3 runs):

Threads One lock (seconds)
1 0.538
2 1.467
4 0.966

With two threads, the same total work took 2.7 times as long as with one thread. Every operation holds the one lock while it walks a list of about 195 nodes, so the threads wait for each other all the time, and the lock itself is passed between processors with system calls. This is the extreme case of the counter result: more threads, less speed.

Concurrent data structure

A concurrent data structure is a data structure whose operations may be called by several threads at the same time and still leave it in a consistent state, usually by means of locks or atomic operations inside the operations.

Example: a hash table whose insert and lookup each lock a mutex is a concurrent data structure with coarse-grained locking.

Check yourself: 1. How many buckets does a lookup examine? 2. Why was the two-thread run slower than the one-thread run? 3. What did the check after each run prove?