# Implementing Hash Tables in C

**NOTE(s)**:
The article is in “draft” status. The content was originally written in 2017.

The intended audience for this article is undergrad students or seasoned developers who want to refresh their knowledge on the subject.

The reader should already be familiar with C (pointers, pointer functions, macros, memory management) and basic data structures knowledge (e.g., arrays, linked lists, and binary trees).

# Table of contents

- Table of contents
- Code
- Introduction
- Hash Functions
- Implementing hash tables
- References

# Code

If you don’t want to read the article, and you just want to jump directly into the code for:

- Separate Chaining:
`git clone git@github.com:nomemory/chained-hash-table-c.git`

- Open Addressing:
`git clone git@github.com:nomemory/open-adressing-hash-table-c.git`

The code needs to be compiled with the

`c99`

flag.

# Introduction

Outside the domain of computers, the word

hashmeans tochop/mixsomething.

In Computer Science, a *hash table* is a fundamental data structure that associates a **set of keys** with a **set of values**. Each pair `<key, value>`

is an entry in our **hash table**. Given a **key**, we can get the **value**. Not only that, but we can add and remove `<key, value>`

pairs whenever it is needed.

Not be confused with hash trees or hash lists.

In a way, a hash table share some similarities with the average “array”, so let’s look at the following code:

```
int arr[] = {100, 200, 300};
printf("%d\n", arr[1]);
```

If we were to run it, the output would be `200`

. As we write `arr[<index>]`

, we are *peeping* at the value associated with the given `<index>`

, and in our case, the value associated with `1`

is `200`

.

In this regard, a hash table can act very similar to an array, because it will allow us to map a **value** to a given **key**. But there’s a catch, compared to an array, the **key** can be *everything* - we are not limited to sorted numerical indexes.

Most modern computer programming languages have a hash table implementation in their standard libraries. The names can be different, but the results are the same.

For example in C++, we have something called `std::unorderd_map`

:

```
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> colors = {
/* associates to the key: */ {"RED", /* the value: */ "#FF0000"},
{"GREEN", "#00FF00"},
{"BLUE", "#0000FF"}
};
std::cout << colors["RED"] << std::endl;
}
// Output: #FF0000
```

In the Java world, there’s `HashMap`

:

```
import java.util.Map;
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
Map<String, String> colors = new HashMap<>();
colors.put("RED", "#FF0000");
colors.put("GREEN", "#00FF00");
colors.put("BLUE", "#0000FF");
System.out.println(colors.get("RED"));
}
}
// Output: #FF0000
```

Or in languages like python, support for hash tables is “built-in” in the language itself:

```
colors = {
"RED" : "#FF0000",
"GREEN" : "#00FF00",
"BLUE" :"#0000FF"
}
print(colors["RED"])
# Output: #FF0000
```

So regardless of the name (`unordered_map`

in C++, `HashMap`

in Java, or `dict`

in python), if we run all three code snippets, the result will be the same: `"#FF0000"`

.

Size doesn’t matter.

What is impressive about hash tables is they are very “efficient” in terms of (average) time complexities. Given a **key**, we can return the **value** associated with it in(almost) constant time, no matter how many pairs we have previously inserted. So they scale exceptionally well with size. In a way, for a **hash table** “size doesn’t matter”, as long as we keep things under control:

Think of it for a moment. For a binary tree, searching for an element is `O(logn)`

; if the trees grow, `n`

grows, so searching for an element takes more time. But No!, not for hash tables. As long as we know the key, we can have almost instant access to the stored value.

Operation | Average Time Complexity | Worst-case scenario |
---|---|---|

Getting a value |
`O(1)` |
`O(n)` |

Adding a new pair `<key, value>` |
`O(1)` |
`O(n)` |

Updating a pair `<key, value>` |
`O(1)` |
`O(n)` |

Removing a pair `<key, value>` |
`O(1)` |
`O(n)` |

This remarkable data structure is internally powered by clever mathematical functions: called **hash functions**. They are the “force” behind the fantastic properties of hash tables: the ability to scale even if the number of pairs increases.

At this point, it wouldn’t be wise to jump directly to the implementation of a hash table, so we will make a short mathematical detour into the wonderful world of **hash functions**. They are less scary than you would typically expect, well, at least on the surface.

# Hash Functions

In *English*, A **hash function** is a function that “chops” data of arbitrary size to data of fixed size.

From a mathematical perspective, A **hash function** is a function \(H : X \rightarrow [0, M)\), that takes an element in \(x \in X\) and associates to it a positive integer \(H(x) = m\), where \(m \in [0, M)\).

\(X\) can be bounded or an *un*-bounded set of values, while \(M\) is always a positive finite number \(0 < M < \infty\).

Let’s take a look at the following example:

In the above diagram `Paris`

, `Berlin`

, `Warsaw`

, `Bucharest`

, `Athens`

are all capitals that \(\in X\), where \(X\) is a set containing all European Capitals, so \(n(X) = 48\).

Our hashing function is \(H : X \rightarrow [0, 16)\), so that:

`H("Paris")`

returns`00`

;`H("Berlin)`

returns`01`

;`H("Warsaw)`

returns`04`

;`H("Bucharest)`

returns`03`

;`H("Athens")`

returns`04`

;

In total, there are around 48 countries in Europe, each with its capital. So the number of elements in \(X\) is 48, while \(M = 16\) so that the possible values are in the interval \([0, 1, 2, ... 16)\).

Because \(48>16\), no matter how we write \(H\), some European Capital Cities will share the same number \(m \in [0,1, ... 16)\).

For our hypothetical example, we can see that happening for `H("Warsaw) = H("Athens") = 4`

.

Whenever we have two elements \(x_{1}, x_{2} \in X\) so that \(H(x_{1}) = H(x_{2}) = m_{x}\), we say we have a **hash collision**.

In our example we can say that \(H\) has a **hash collision** for \(x_{1}=Warsaw\) and \(x_{2}=Athens\), because \(H(x_{1}) = H(x_{2}) = 4\).

**Hash Collisions** are not game-breaking per se, as long as the \(n(X) > M\) they might happen. But it’s important to understand that a *good* **hash function** creates fewer **hash collisions** than a *bad* one.

Basically the worst hash function we can write is a function that returns a constant value, so that \(H(x_{1}) = H(x_{2}) = ... = H(x_{n}) = c\), where \(n = n(X)\), and \(c \in [0, M)\). This is just another way of saying that every element \(x \in X\) will collide with the others.

Another way we can shoot ourselves in the foot is to pick a **hash function** that is not deterministic. When we call \(H(x)\) subsequently, it should render the same results without being in any way affected by external factors.

Cryptographic hash functionsare a special family ofhash functions. For security considerations, they exhibit an extra set of properties. The functions used inhash tableimplementations are significantly less pretentious.

Another essential aspect when picking the right **hash function** is to pick something that it’s not computationally intensive. Preferably it should be something close to `O(1)`

. **Hash tables** are using **hash functions** intensively, so we don’t want to complicate things too much.

Picking the proper hash function is a tedious job. It involves a lot of statistics, number theory, and empiricism, but generally speaking, when we look for a hash function, we should take into consideration the following requirements:

- It should have a reduced number of collisions;
- It should disperse the hashes uniformly in the \([0, M)\) interval;
- It should be fast to compute;

We can talk about “families” of hashing functions. On the one hand, you have **cryptographic hash functions** that are computationally complex and have to be resistant to preimage attacks (that’s a topic for another day). Then you have simpler **hash functions** that are suitable to be used to implement **hash tables**:

- Cryptographic hash functions;
- All-around / general functions used for
**hash table**implementations:- Division hashing;
- Bit shift hash functions
- Multiplicative hashing;

The advanced math behind **hash functions** eludes me. I am a simple engineer, no stranger to math, but not an expert. There are PHD papers on the subject, and for a select group of people, this is their actual job: finding better and faster ways of **hashing** stuff. So, in the next two paragraphs, I will try to keep things as simple as possible by avoiding making things more mathematical than needed.

## Division hashing

The simplest **hash function** that we can write the mod `%`

operation, and it’s called **division hashing**.

It works on positive numbers, so let’s suppose we can represent our initial input data \(x_{1}, x_{2}, ... x_{n} \in X \subset N\) as a non-negative integers.

Then, the formula for our hash function is \(H_{division}(x) = x \mod M\), where \(H_{division} : X \rightarrow [0, M)\). In English this means that the hash of a given value \(x\) is the remainder of \(x\) divided with M.

Writing this function in C is trivial:

```
uint32_t hashf_division(uint32_t x, uint32_t M) {
return x % M;
};
```

On the surface, `hashf_division()`

checks all the requirements for a good **hashing function**.

And it’s a good hashing function as long as the input data (\(x_{1}, x_{2}, ..., x_{n}\)) is guaranteed to be perfectly random, without obvious numerical patterns.

So let’s test how it behaves if we pick:

`M=4`

;`1000000`

uniformly distributed positive integers as input (\(X\))

Without writing any code, we would infer that all the input will be evenly distributed between 4 hash values: `0`

, `1`

, `2`

and `3`

. There are going to be collisions (as \(n(X)\) is 250000 bigger than `4`

), but theoretically, we can reduce them by increasing `M`

further down the road.

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define M_VAL 4
#define X_VAL 1000000
uint32_t hashf_division(uint32_t x, uint32_t M) {
return x % M;
};
int main(int argc, char* argv[]){
// initiate rand
srand(time(0));
unsigned int i, hash;
// buckets
int buckets[M_VAL];
for(i = 0; i < X_VAL; i++) {
hash = hashf_division(rand(), M_VAL);
buckets[hash]++;
}
for(i = 0; i < M_VAL; i++) {
printf("bucket[%u] has %u elements\n", i, buckets[i]);
}
}
```

If we run the above program, a possible output would be:

```
bucket[0] has 250146 elements
bucket[1] has 249361 elements
bucket[2] has 250509 elements
bucket[3] has 249984 elements
```

The results are OK:

- All input has been evenly distributed between the four values (buckets);
- The
`%`

operation is quite efficient (although it’s usually a number of times less efficient than multiplication); - Collisions are there, but they can be controlled by increasing the value
`M`

to accommodate the input size.

Multiplication and division take longer time. Integer multiplication takes 11 clock cycles on Pentium 4 processors, and 3 - 4 clock cycles on most other microprocessors. Integer division takes 40 - 80 clock cycles, depending on the microprocessor. Integer division is faster the smaller the integer size on AMD processors, but not on Intel processors. Details about instruction latencies are listed in manual 4: “Instruction tables”. Tips about how to speed up multiplications and divisions are given on page 146 and 147, respectively. (source)

We call the resulting hashes

buckets, and once we start implementing the actual hash table, this will make more sense.

But what happens if our (input) data is not that random after all. What if the data follows a particular obvious (or not so obvious) pattern? How is this pattern going to affect the distribution of computed hashes?

Let’s change this line:

```
hash = hashf_division(rand(), M_VAL);
```

To this:

```
hash = hashf_division(rand()&-2, M_VAL)
```

Now, all our *randomly generated* numbers will be even. If that’s not an obvious pattern, I don’t know what is.

Let’s see how our hashing function behaves in this scenario and how well the hashes are distributed:

```
bucket[0] has 500810 elements
bucket[1] has 0 elements
bucket[2] has 499190 elements
bucket[3] has 0 elements
```

We see that values `1`

and `3`

are never used, which is unfortunate, but an expected consequence of how the input is constructed. If all the input numbers are even, then their remainder is either `0`

or `2`

.

Mathematically we can prove there’s not a single \(x_{i} \in X \subset N\), for our function \(H_{division}(x)=x \mod 4\), where \(H : X \rightarrow [0, 4)\), so that \(H_{division}(x_{i})=1\) or \(H_{division}(x_{i})=3\).

So this means our function is not so good after all because it’s extremely sensitive to “input patterns”?

The answer is not that simple, but what’s for sure is that changing `M=4`

to `M=7`

will render different results.

This time, the output will be:

```
bucket[0] has 142227 elements
bucket[1] has 143056 elements
bucket[2] has 143592 elements
bucket[3] has 142721 elements
bucket[4] has 142722 elements
bucket[5] has 142662 elements
bucket[6] has 143020 elements
```

The results look promising again. The hash values are again “evenly” distributed, but all kinds of (subtle) problems can appear based on our choice of `M`

.

Normally, `M`

should be a prime number, and some prime numbers will work in practice better than others, e.g.:

To make the results even better, Donald Knuth, proposed an alternative solution, where \(H_{division}^{Knuth}(x) = x ( x + 3) \mod M\).

In practice, **division hashing** is not that commonly used. The reason is simple, even the results are satisfactory (especially when `M`

is chosen wisely), division and modulo operations are more “expensive” than addition or multiplication.

## Multiplicative hashing

A common (and practical) approach for generating relatively uniform hash values is called **multiplicative hashing**.

Similar to **division hashing**, the formula works for positive integers. So we assume that we have a mechanism that converts our input space to positive numbers only.

The following formula usually describes a **multiplicative hash** function:

\(H_{multip}(x) = \frac{M}{W} * (Ax \mod W)\), where \(H_{multip} : X \in N \rightarrow [0, M)\).

- \(A \in R_{*}^{+}\) is a constant;
- M is usually a power of
`2`

, so that \(M = 2^m\). - \(W = 2^w\), where \(w\) is the machine word size. In C we can look for the max value of an
`unsigned int`

in the header file`limits.h`

:`UINT_MAX`

. In this case`W=UINT_MAX+1`

.

So our function becomes:

\[H_{multip}(x) = \frac{2^m}{2^w} * (Ax \mod 2^w) = 2^{m-w} * (Ax \mod 2^w) = \frac{Ax \mod 2^w}{2^{w-m}}\]By the magic of bitwise operations, \(Ax \mod 2^w\) is just a way of getting the \(w\) low order bits of \(Ax\). Think of it for a second, `x % 2`

returns the last bit of x, `x % 4`

returns the last 2 bits of x, etc.

Dividing a number \(b\) by \(2^{w-m}\) actually means shifting right `w-m`

bits. So our method actually becomes:

If we were to write this in C:

```
uint32_t hashf_multip(uint32_t x, uint32_t p, uint32_t w, uint32_t m, uint32_t A) {
return (x * A) >> (w-m);
}
```

I won’t get into all the mathematical details, but a good choice for \(A\) is \(A=\phi * 2^w\), where \(w\) is the word machine word size, and \(\phi\) (phi) is the golden ratio.

\(\phi\), just like its more famous brother \(\pi\) (pi), is an irrational number, \(\phi \in Q{'}\), that is a solution to the equation: \(x^2-x-1=0 => \phi \approx 0.6180339887498948482045868343656\).

Depending on the word size, \(A\) can be computed as follows:

\(w\) | \(A=2^w * \phi \approx\) |
---|---|

16 | 40,503 |

32 | 2,654,435,769 |

64 | 11,400,714,819,323,198,485 |

When we pick \(A=\phi * 2^w\), our general **multiplicative hash function** is called a **Fibonacci hash function**.

Having this said, we can now simplify the signature of our C function. We don’t need `A`

, `m`

, `w`

anymore as input params because they can be `#defined`

as constants.

After the signature change, our function becomes:

```
#define hash_a (uint32_t) 2654435769
#define hash_w 32
#define hash_m 3
uint32_t hashf_multip(uint32_t x, uint32_t m) {
return (x * hash_a) >> (hash_w - m);
}
```

As it’s mentioned here, **Fibonacci Hashing** has one “small” issue. Poor diffusion happens as higher-value bits do not affect lower-value bits. In this regard, it can further be improved by shifting the span of retained higher bits and then `XOR`

ing them to the key before the actual **hash multiplication** happens:

```
#define hash_a (uint32_t) 2654435769
#define hash_w 32
#define hash_m 3
uint32_t hashf_multip2(uint32_t x, uint32_t m) {
x ^= x >> (hash_w - m);
return (x * hash_a) >> (hash_w - m);
}
```

With `hashf_multip2()`

, we achieve better diffusion with a price: more operations.

## Hashing strings

Converting non-numerical data to positive integers (`uint32_t`

) is quite simple. After all, everything is a sequence of bits.

In K&R Book (1st ed) a simple (and ineffective) hashing algorithm was proposed: *What if sum the numerical values of all characters from a string?*

```
uint32_t hashf_krlose(char *str) {
uint32_t hash = 0;
char c;
while((c=*str++)) {
hash+=c;
}
return hash;
}
```

Unfortunately, the output for `hashf_krlose`

will be “extremely” sensitive to input patterns. It’s easy to apply a little **Gematria** ourselves to create input that will repeatedly return identical hashes.

For example:

```
char* input[] = { "IJK", "HJL", "GJM", "FJN" };
uint32_t i;
for(i = 0; i < 4; i++) {
printf("%d\n", hashf_krlose(input[i]));
}
```

The hash values for `"IJK"`

, `"HJL"`

, `"GJM"`

, `"FJN"`

are all `222`

.

A proposal to improve the function is to replace `+=`

(summing) with `^=`

(XORing), so that `hash+=c`

becomes `hash^=c`

. But again, patterns that break our **hash function** are easy to create, so it doesn’t make a big practical difference.

The good news is that there’s a common type of **hash function** that works quite well with strings (`char*`

).

The *template* for those functions look like:

```
#define INIT <some_value>
#define MULTIP <some_value>
uint32_t hashf_generic(char* str) {
uint32_t hash = INIT;
char c;
while((c*=str++)) {
hash = MULTIP * hash + c;
}
return hash;
}
```

### djb2

If `INIT=5381`

and `MULT=33`

, the function is called **Bernstein hash djb2**, which dates 1991.

If you find better values, chances are your name will remain in the history books of Computer Science.

Implementing it in C is quite straight-forward:

```
#define INIT 5381
#define MULT 33
uint32_t hashf_djb2_m(char *str) {
uint32_t hash = INIT;
char c;
while((c=*str++)) {
hash = hash * MULT + c;
}
return hash;
}
```

If you look over the internet for **djb2**, you will find a different implementation that uses one clever, simple trick. The code would be:

```
#define INIT 5381
uint32_t hashf_djb2(char *str) {
uint32_t hash = INIT;
char c;
while((c=*str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
```

If we write `a << x`

, we are shifting `x`

bits of `a`

to the left. By the magic of bitwise operations, this is equivalent to multiplying `a * 2^x`

.

So, our expression `hash = ((hash << 5) + hash) + c`

is equivalent to `hash = (hash * 2^5) + hash + c`

, that is equivalent to `hash = hash * (2^5 + 1) + c`

, that is equivalent `hash = hash * 33 +c`

.

This is **not** just a fancy way of doing things. Historically speaking, most CPUs were performing bitshifts faster than multiplication or division. They still do.

In modern times, modern compilers can perform all kinds of optimizations, including this one. So it’s up to you to decide if making things harder to read is worth it. Again, some benchmarking is recommended.

### sdbm

If you search the internet for **sdbm** you won’t find a lot of details, except:

This algorithm was created for sdbm (a public-domain re-implementation of ndbm) database library. It was found to do well in scrambling bits, causing a better distribution of the keys and fewer splits. It also happens to be a good general hashing function with good distribution.

The function looks like this: z

```
uint32_t hashf_sdbm(char *str) {
uint32_t hash = 0;
char c;
while((c=*str++)) {
hash = c + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
```

## Reducing the number of collisions - Finalizers

After publishing the article draft on reddit/r/C_Programming, the community (u/skeeto) suggested the **hash functions** for strings can be improved even further with a simple trick: *finalizers*.

A common *finalizer* found in MurmurHash, looks like:

```
uint32_t ch_hash_fmix32(uint32_t h) {
h ^= h >> 16;
h *= 0x3243f6a9U;
h ^= h >> 16;
return h;
}
```

In practice, we can improve results generated by djb2, sdbm by applying `ch_hash_fmix32()`

on their output:

```
uint32_t final_hash = ch_hash_fmix32(hashf_sdbm("some string");
```

## More exploration

What we’ve discussed so far about **hash functions** only scratches the surface of a vast subject. There are hundreds of functions, some of them better than others. But, as Software Engineers, we need to be pragmatic, know about them, ponder over their pros and cons and, in the end, take things for granted. Most of the time, simple is better.

For high(er)-level programming languages (C++, C#, Java, python), the “hashing” problem is already sorted out at “language” or “standard library” level, so we rarely have to write (or copy-paste) a hash function by hand.

If you want to explore this topic more, I suggest you also take a look at the following articles:

- FNV Hash - a popular
**hash function**designed to be fast while maintaining a low collision rate; - SipHash
- Murmurhash - is a non-cryptographic hash function suitable for general hash-based lookup. Source code here.
- Zobrist Hashing - a
**hash function**used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. - chunk64 - a
**hash function**designed by Christopher Wellons - Integer hash function
- 4-byte Integer hashing

# Implementing hash tables

**Hash tables** are fundamental data structures that associate a set of keys with a set of values. Each `<key, value>`

pair is an entry in the table. Knowing the key, we can look for its corresponding value (*GET*). We can also add (*PUT*) or remove (*DEL*) `<key, value>`

entries just by knowing the key.

In a **hash table**, data is stored in an array (not surprisingly), where each pair `<key, value>`

has its own unique index (or *bucket*). Accessing the data becomes highly efficient as long as we know the *bucket*.

The *bucket* is always computed by applying a hash function over a key: \(hash_{function}(key) \rightarrow \text{bucket[<key, value>)]}\).

Depending on how we plan to tackle potential **hash collisions**, there are various ways to implement a **hash table**:

*Separate Chaining (using linked lists)*- Each
*bucket*references a**linked list**that contains*none*,*one*or more`<key, value`

> entries; - To add a new entry (
*PUT*) we compute the bucket (`hash(key)`

), and then we append the`<key, value`

> to the corresponding**linked list**. If the`key`

already exists, we just update the`value`

; - To identify an entry (
*GET*), we compute the*bucket*, traverse the corresponding**linked list**until we find the`key`

.

- Each
- Separate Chaining (dynamically growing array buckets)
- Each
*bucket*is an array that grows dynamically if needed;

- Each
- Separate Chaining (red black trees optimization)
- The
*buckets*are being transformed into a*red black tree*if the number of elements contained exceeds a certain threshold.

- The
*Open Addressing*- There are no
**linked lists**involved - there’s only one`<key, value>`

entry per bucket; - In case of collisions, we
*probe*the array to find another suitable*bucket*for our entry, and then we add the entry at this new-found*empty*location; - Various algorithms for “probing” exists; the simplest one is called
*linear probing*- in case of collision, we just jump to the next available*bucket*; - Deleting an existing entry is a complex operation.

- There are no

Each strategy has its PROs and CONs. For example, the creators of Java preferred to use *Separate Chaining* in their `HashMap`

implementation, while the creators of python went with *Open Addressing* for their `dict`

.

*Separate Chaining* is simpler to implement, and in case we have a high frequency **hash collisions**, performance degradation is more *graceful* - not as exacerbated as for *Open Addressing*.

*Open Addressing* is more complex to implement, but if we keep **hash collisions** at bay, it’s very *cache-friendly*.

## Separate Chaining (using Linked Lists)

To better understand how *Separate Chaining* works, let’s represent in a visual way a **hash table** that associates the capitals of Europe (the keys) to their corresponding countries (the values):

European Capital | European Country |
---|---|

“Paris” | “France” |

“Berlin” | “Germany” |

“Warsaw” | “Poland” |

“Bucharest” | “Romania” |

“Athens” | “Greece” |

Both keys and values are strings (`char*`

).

The first step is to reduce the keyspace to a numeric value to hash the keys further and associate them with buckets. For this, we can use something like djb2 to hash the string to a `uint32_t`

value. We already know that **djb** works well with string inputs.

This step is not “part” of the **hash table** itself. It’s impossible for a **hash table** to understand all data formats and reduce them to 32-bit unsigned integers(`uint32_t`

). In this regard, the *data* needs to come with its mechanisms for this. So except the keys are `uint32_t`

, additional **hash functions** should be provided to the **hash table** (for the *data*, by the *data*).

After the keys are “projected” to the `uint32_t`

space, we must map them to *buckets* (indices in our array). Another **hash function** will reduce the *key-space* further: from `uint32_t`

to `[0, M)`

, where `M`

is the total number of buckets. For simplicity, we can use **division hashing**, **multiplicative hashing**, or whatever hash function we think it’s good.

After the *bucket* is identified, we check if it’s empty (`NULL`

). If it’s `NULL`

, we create a new *linked list*, and add the pair `<key, value>`

to it. If it’s not empty, we append the entry to the existing structure.

### A generic implementation

Preferably, our **hash table** will be as *generic* as possible so that it can be re-used for various key/values combinations. We want to write code once and re-use it later. Writing a new **hash table** every time the key/value combination changes it’s not ideal.

The bad news, C is not exactly the most generic-friendly programming language there is.

The good news, C is flexible enough to make generic programming happen (with some effort) by:

- using
`void*`

to pass data around, - using
`#macros`

that generate*specialized*code after pre-processing (something similar to C++ templates).

I’ve recently found an interesting

genericdata structures library called STC; looking at the code can be pretty inspirational.

I am the camp that prefers `#macros`

over `void*`

, but **not** when it comes to writing tutorials. With `#macros`

, everything becomes messy fast, and the code is hard to debug and maintain. So, for this particular implementation, we will use `void*`

for passing/retrieving *generic data* to/from the **hash table**.

### The model

We start by defining the `struct`

(s) behind **hash tables**. The main structure (`ch_hash`

) will contain:

`capacity`

- the total number of available buckets;`size`

- the total number of elements;`buckets`

- a dynamic (expandable if needed) array of linked lists;- Structures to keep tracking of data-specific operations (e.g., a function that checks if two values are equal, etc.);

```
typedef struct ch_hash_s {
size_t capacity;
size_t size;
ch_node **buckets;
ch_key_ops key_ops;
ch_val_ops val_ops;
} ch_hash;
```

As we said, the *buckets* are composed of linked lists:**

```
typedef struct ch_node_s {
uint32_t hash;
void *key;
void *val;
struct ch_node_s *next;
} ch_node;
```

The `ch_node`

structure contains:

`uint32_t hash`

is not the actual bucket index, but it’s the hash of the data that is going inside the**hash table**. For example, if our keys are strings,`uint32_t hash`

is obtained by applying a**hashing function**that works for strings (e.g.: djb2). This is only computed once, and it’s (re)used whenever we need to ** rehash** our table;`key`

and`val`

of a`void*`

type. This gives us enough flexibility to store almost anything in the table.`struct ch_node_s *next`

which is a reference to the next node in the list.

The only thing left to explain are the two “unknown” members: `ch_hash->ch_key_ops`

and `ch_hash->ch_val_ops`

:

```
typedef struct ch_key_ops_s {
uint32_t (*hash)(const void *data, void *arg);
void* (*cp)(const void *data, void *arg);
void (*free)(void *data, void *arg);
bool (*eq)(const void *data1, const void *data2, void *arg);
void *arg;
} ch_key_ops;
typedef struct ch_val_ops_s {
void* (*cp)(const void *data, void *arg);
void (*free)(void *data, void *arg);
bool (*eq)(const void *data1, const void *data2, void *arg);
void *arg;
} ch_val_ops;
```

The two types, `ch_key_ops`

and `ch_val_ops`

are simple structures (`struct`

) used to group functions specific to the data inserted in the **hash table**. As we previously stated, it’s impossible to think of all the possible combinations of keys/pairs and their types, so we let the user supply us with the truth.

In case the above code is confusing, please refer to the following article: Function pointers; it will explain to you in great detail how we can pass functions around through “pointers”.

It’s funny to think C had its first functional programing feature implemented decades before Java…

Think of `ch_key_ops`

and `ch_val_ops`

as *traits*, bits of logic that are external to the **hash table** itself, but by defining them, we are creating a simple contract between our structure and the data we are inserting:

Look, if you want to add a

`chr*`

as a`key`

in ourhash table, please tell us first how do you: compute its hash, copy it, and free the memory. Our table will do the heavy work for you, but first, we need to know this !?

As an example, the required functions for strings (`chr*`

) can be implemented like this:

```
//Finalizer
static uint32_t ch_hash_fmix32(uint32_t h) {
h ^= h >> 16;
h *= 0x3243f6a9U;
h ^= h >> 16;
return h;
}
// Returns the uint32_t hash value of a string computed using djb2
uint32_t ch_string_hash(const void *data, void *arg) {
//djb2
uint32_t hash = (const uint32_t) 5381;
const char *str = (const char*) data;
char c;
while((c=*str++)) {
hash = ((hash << 5) + hash) + c;
}
return ch_hash_fmix32(hash);
}
// Returns a copy of the *data string
void* ch_string_cp(const void *data, void *arg) {
const char *input = (const char*) data;
size_t input_length = strlen(input) + 1;
char *result;
result = malloc(sizeof(*result) * input_length);
if (NULL==result) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
strcpy(result, input);
return result;
}
// Check if two strings are equal
bool ch_string_eq(const void *data1, const void *data2, void *arg) {
const char *str1 = (const char*) data1;
const char *str2 = (const char*) data2;
return !(strcmp(str1, str2)) ? true : false;
}
// Free the memory associated with a string
void ch_string_free(void *data, void *arg) {
free(data);
}
```

As you can see, even if our methods are going to be used for strings (`chr*`

) we are forced to use `void*`

instead and cast data manually.

Sadly, `void*`

is not the `T`

we know from *C++ Templates* or *Java Generics*. No compile-time validations are performed. It’s up to us to use it accordingly.

And then, what it remains is two keep two instances around (one for keys and one for values):

```
ch_key_ops ch_key_ops_string = { ch_string_hash, ch_string_cp, ch_string_free, ch_string_eq, NULL};
ch_val_ops ch_val_ops_string = { ch_string_cp, ch_string_free, ch_string_eq, NULL};
```

Now let’s retake a look at the initial diagram and how are structures fit together with the visual representation:

### The interface

Our **hash table** (`ch_hash`

) will support and publicly expose the following functions (interface):

```
// Creates a new hash table
ch_hash *ch_hash_new(ch_key_ops k_ops, ch_val_ops v_ops);
// Free the memory associated with the hash (and all of its contents)
void ch_hash_free(ch_hash *hash);
// Gets the value coresponding to a key
// If the key is not found returns NULL
void* ch_hash_get(ch_hash *hash, const void *k);
// Checks if a key exists or not in the hash table
bool ch_hash_contains(ch_hash *hash, const void *k);
// Adds a <key, value> pair to the table
void ch_hash_put(ch_hash *hash, const void *k, const void *v);
// Prints the contents of the hash table
void ch_hash_print(ch_hash *hash, void (*print_key)(const void *k), void (*print_val)(const void *v));
// Get the total number of collisions
uint32_t ch_hash_numcol(ch_hash *hash);
```

As you might’ve noticed, there’s no function for deleting an entry. That’s intentionally left out as a proposed exercise.

Before implementing the enumerated methods, it’s good to clarify a few things that are not obvious from the interface itself.

Just for fun (best practices are fun!), our **hash table** will grow automatically if its `size`

reaches a certain threshold. So every time we insert a new element, we check if the threshold has been reached and if it’s time to increase the capacity (and the number of available buckets). A rehashing of everything will also be performed - old entries might go to new buckets.

In this regard let’s define the following constants (we can tweak their values later):

```
#define CH_HASH_CAPACITY_INIT (32)
#define CH_HASH_CAPACITY_MULT (2)
#define CH_HASH_GROWTH (1)
```

And then perform the following check each time we insert a new item:

```
// Grow if needed
if (hash->size > hash->capacity * CH_HASH_GROWTH) {
ch_hash_grow(hash);
// -> The function will perform a full rehashing to a new array of buckets
// of size [hash->capacity * CH_HASH_CAPACITY_MULT]
}
```

The `ch_hash_grow(ch_hash *hash)`

function it’s not defined as part of the interface; it’s `private`

. We won’t be exposing it to the header file.

Another function that’s not exposed in our (public) interface is: `ch_node* ch_hash_get_node(ch_hash*, const void*)`

. This one is used to check if a node exists or not. In case it exists, it retrieves the node. Otherwise, it returns `NULL`

.

The reason we have two functions for retrieving data is simple:

`void* ch_hash_get(ch_hash *hash, const void *k);`

(public)`ch_node* ch_hash_get_node(ch_hash *hash, const void *key)`

(private)

`ch_hash_get_node`

works on a structure (`ch_node`

) that is internal for our implementation, while `ch_hash_get`

will use `ch_hash_get_node`

to retrieve the actual value.

#### Creating/Destroying a **hash table**

`ch_hash_new`

is a constructor-like function that dynamically allocates memory for a new `ch_hash`

.

`ch_hash_free`

is a destructor-like function that `free`

s all the memory associated with a `ch_hash`

. `ch_hash_free`

goes even deeper and de-allocates memory for the internal *buckets* and all the existing entries.

The code for `ch_hash_new`

is:

```
ch_hash *ch_hash_new(ch_key_ops k_ops, ch_val_ops v_ops) {
ch_hash *hash;
hash = malloc(sizeof(*hash));
if(NULL == hash) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
hash->size = 0;
hash->capacity = CH_HASH_CAPACITY_INIT;
hash->key_ops = k_ops;
hash->val_ops = v_ops;
hash->buckets = malloc(hash->capacity * sizeof(*(hash->buckets)));
if (NULL == hash->buckets) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
for(int i = 0; i < hash->capacity; i++) {
// Initially all the buckets are NULL
// Memory will be allocated for them when needed
hash->buckets[i] = NULL;
}
return hash;
}
```

*Note*: using `exit(EXIT_FAILURE);`

is not ideal, and it’s not a good practice when you are writing libraries you want to share with the public. Basically, you are telling the program to **stop**, without giving it any chance to do some cleaning first. Don’t do this if you plan to make your own **hash table** library and share it with a larger audience.

The code for `ch_hash_free`

is:

```
void ch_hash_free(ch_hash *hash) {
ch_node *crt;
ch_node *next;
for(int i = 0; i < hash->capacity; ++i) {
// Free memory for each bucket
crt = hash->buckets[i];
while(NULL!=crt) {
next = crt->next;
// Free memory for key and value
hash->key_ops.free(crt->key, hash->key_ops.arg);
hash->val_ops.free(crt->val, hash->val_ops.arg);
// Free the node
free(crt);
crt = next;
}
}
// Free the buckets and the hash structure itself
free(hash->buckets);
free(hash);
}
```

In terms of what’s happening in `ch_hash_free`

, things are quite straightforward, except for those two lines:

```
hash->key_ops.free(crt->key, hash->key_ops.arg);
hash->val_ops.free(crt->val, hash->val_ops.arg);
```

Because the **hash table** doesn’t know what type of data it holds in the entries (`void*`

is not very explicit, isn’t it), it’s impossible to `free`

the memory correctly.

So in this regard, we use the `free`

functions referenced inside `key_ops`

(for keys) and `val_ops`

(for values).

#### Retrieving a value from the **hash table**

For the sake of simplicity, the function that translates the `uint32_t`

hash of the key to the `[0, hash->capacity)`

space is `%`

.

We will use **division hashing** in our implementation.

```
static ch_node* ch_hash_get_node(ch_hash *hash, const void *key) {
ch_node *result = NULL;
ch_node *crt = NULL;
uint32_t h;
size_t bucket_idx;
// We compute the hash of the key to check for it's existence
h = hash->key_ops.hash(key, hash->key_ops.arg);
// We use simple division hashing for determining the bucket
bucket_idx = h % hash->capacity;
crt = hash->buckets[bucket_idx];
while(NULL!=crt) {
// Iterated through the linked list found at the bucket
// to determine if the element is present or not
if (crt->hash == h && hash->key_ops.eq(crt->key, key, hash->val_ops.arg)) {
result = crt;
break;
}
crt = crt->next;
}
// If the while search performed in the while loop was successful,
// `result` contains the node
// otherwise it's NULL
return result;
}
```

`ch_hash_get`

is just a wrapper function built on top of `ch_hash_get_node`

. It has filtering purposes only: retrieving the value (`ch_node->val`

) instead of the internal `ch_node`

representation.

```
void* ch_hash_get(ch_hash *hash, const void *k) {
ch_node *result = NULL;
if (NULL!=(result=ch_hash_get_node(hash, k))) {
return result->val;
}
return NULL;
}
```

#### Adding an entry to the **hash table**

The `ch_hash_put`

method is responsible for adding new entries to the **hash table**.

```
void ch_hash_put(ch_hash *hash, const void *k, const void *v) {
ch_node *crt;
size_t bucket_idx;
crt = ch_hash_get_node(hash, k);
if (crt) {
// Key already exists
// We need to update the value
hash->val_ops.free(crt->val, hash->val_ops.arg);
crt->val = v ? hash->val_ops.cp(v, hash->val_ops.arg) : 0;
}
else {
// Key doesn't exist
// - We create a node
// - We add a node to the corresponding bucket
crt = malloc(sizeof(*crt));
if (NULL == crt) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
crt->hash = hash->key_ops.hash(k, hash->key_ops.arg);
crt->key = hash->key_ops.cp(k, hash->key_ops.arg);
crt->val = hash->val_ops.cp(v, hash->val_ops.arg);
// Simple division hashing to determine the bucket
bucket_idx = crt->hash % hash->capacity;
crt->next = hash->buckets[bucket_idx];
hash->buckets[bucket_idx] = crt;
// Element has been added successfully
hash->size++;
// Grow if needed
if (hash->size > hash->capacity * CH_HASH_GROWTH) {
ch_hash_grow(hash);
}
}
}
```

`ch_hash_grow`

is an internal method (not exposed in the public API) responsible for scaling up the number of buckets (`hash->buckets`

) based on the number of elements contained in the table (`hash->size`

).

`ch_hash_grow`

allocates memory for a new array `ch_node **new_buckets`

, and then rehashes all the elements from the *old* array (`hash->buckets`

) by projecting them in the *new buckets*.

In regards to this, 3 constants are being used:

```
#define CH_HASH_CAPACITY_INIT (32)
#define CH_HASH_CAPACITY_MULT (2)
#define CH_HASH_GROWTH (1)
```

`CH_HASH_CAPACITY_INIT`

is the initial size of the array (`hash->buckets`

).

`CH_HASH_CAPACITY_MULT`

is the growth multiplier: `hash->capacity *= CH_HASH_CAPACITY_MULT`

. Normally, it would’ve been better to grow to a bigger prime number (because of **division hashing**), but that would’ve been more complicated to implement in the code.

`CH_HASH_GROWTH`

is the load factor - a constant that influences the growth condition: `hash->size > hash->capacity * CH_HASH_GROWTH`

.

If allocating a new array (`new_buckets`

) fails, we will keep the old one - that’s a pragmatic decision to make - so, instead of crashing the program, we accept a potential drop in performance.

```
static void ch_hash_grow(ch_hash *hash) {
ch_node **new_buckets;
ch_node *crt;
size_t new_capacity;
size_t new_idx;
new_capacity = hash->capacity * CH_HASH_CAPACITY_MULT;
new_buckets = malloc(sizeof(*new_buckets) * new_capacity);
if (NULL==new_buckets) {
fprintf(stderr, "Cannot resize buckets array. Hash table won't be resized.\n");
return;
}
for(int i = 0; i < new_capacity; ++i) {
new_buckets[i] = NULL;
}
// Rehash
// For each bucket
for(int i = 0; i < hash->capacity; i++) {
// For each linked list
crt = hash->buckets[i];
while(NULL!=crt) {
// Finding the new bucket
new_idx = crt->hash % new_capacity;
ch_node *cur = crt;
crt = crt->next;
cur->next = new_buckets[new_idx];
new_buckets[new_idx] = cur;
}
}
hash->capacity = new_capacity;
// Free the old buckets
free(hash->buckets);
// Update with the new buckets
hash->buckets = new_buckets;
}
```

Because there’s no

`ch_hash_delete`

method, there’s no`ch_hash_shrink`

method.

#### Printing the contents of a **hash table**

And last but not least, `ch_hash_print`

is a util method that allows us to print the contents of our chained **hash table** to `stdout`

. Because we don’t know how the keys and values look like, we expect the user to supply us with the corresponding *printing functions*.

```
void ch_hash_print(ch_hash *hash, void (*print_key)(const void *k), void (*print_val)(const void *v)) {
ch_node *crt;
printf("Hash Capacity: %lu\n", hash->capacity);
printf("Hash Size: %lu\n", hash->size);
printf("Hash Buckets:\n");
for(int i = 0; i < hash->capacity; i++) {
crt = hash->buckets[i];
printf("\tbucket[%d]:\n", i);
while(NULL!=crt) {
printf("\t\thash=%" PRIu32 ", key=", crt->hash);
print_key(crt->key);
printf(", value=");
print_val(crt->val);
printf("\n");
crt=crt->next;
}
}
}
```

A possible implementation for the `print_key`

function:

```
void ch_string_print(const void *data) {
printf("%s", (const char*) data);
}
```

Calling `ch_hash_print`

is then as simple as: `ch_hash_print(htable, ch_hash_print)`

.

#### Calculating the number of collisions from the **hash table**

The function (`ch_hash_numcol`

) is quite simple to implement:

- We will create an internal function
`uint32_t ch_node_numcol(ch_node* node)`

that counts the number of collisions per*bucket*; - We sum the number of collisions per
*bucket*

The equivalent C code is:

```
static uint32_t ch_node_numcol(ch_node* node) {
uint32_t result = 0;
if (node) {
while(node->next!=NULL) {
result++;
node = node->next;
}
}
return result;
}
uint32_t ch_hash_numcol(ch_hash *hash) {
uint32_t result = 0;
for(int i = 0; i < hash->capacity; ++i) {
result += ch_node_numcol(hash->buckets[i]);
}
return result;
}
```

### Using the **hash table**

The code put together can be found here:

Using the **hash table** is quite trivial. Let’s take for example the following:

```
ch_hash *htable = ch_hash_new(ch_key_ops_string, ch_val_ops_string);
ch_hash_put(htable, "Paris", "France");
ch_hash_put(htable, "Berlin", "Germany");
ch_hash_put(htable, "Warsaw", "Poland");
ch_hash_put(htable, "Bucharest", "Romania");
ch_hash_put(htable, "Athens", "Greece");
printf("%s\n", (char*) ch_hash_get(htable, "Athens"));
printf("%s\n", (char*) ch_hash_get(htable ,"Bucharest"));
ch_hash_print(htable, ch_string_print, ch_string_print);
return 0;
```

The output will be:

```
Greece
Romania
Hash Capacity: 32
Hash Size: 5
Hash Buckets:
bucket[0]:
bucket[1]:
hash=2838988225, key=Berlin, value=Germany
bucket[2]:
bucket[3]:
bucket[4]:
hash=232639524, key=Paris, value=France
bucket[5]:
bucket[6]:
hash=2999025862, key=Bucharest, value=Romana
bucket[7]:
bucket[8]:
hash=2817274824, key=Athens, value=Greece
// ...
// and so on
```

## Separate Chaining (Dynamically growing array buckets)

The previous implementation is rather *naive*, so don’t judge it too harshly. I would be a little concerned if you will use it in practice.

The *elephant in the room* when it comes to **Linked Lists** is how unfriendly they are to caching. A **linked list** is suitable for inserting items (depending on the scenario). Still, they are not well equipped for current hardware architectures, especially when it comes to iteration and reading elements.

CPUs are usually looking to cache two things: the recently accessed memory, and then it tries to predict which memory will be used next. For **linked lists**, the data is not contiguous; nodes are somewhat scattered (also depends on the `malloc()`

implementation), so calling `node->next`

might be subject to cache misses.

So what if we plan to use a “self-expanding” array instead of a **linked list**. When I say self-expanding array, I am thinking something akin to C++’s `std::vector`

or Java’s `ArrayList`

.

The number of *cache misses* will decrease, but we will need to grow the array; `realloc`

is expensive.

This “optimization” will improve the read times, but it will increase (significantly) the writes.

Visually our new **hash table** will look like this:

### Writing a `vector`

-like structure for our buckets: `ch_vect`

#### The model

Implementing a `vector`

-like structure is straightforward. We will use the same approach as before to achieve *genericity* (is this a word?!) as before, but we will keep the interface and the model as simple as possible this time.

Each of our buckets will be a *vector*, with the following internal structure:

```
#define VECT_INIT_CAPACITY (1<<2)
#define VECT_GROWTH_MULTI (2)
typedef struct ch_vect_s {
size_t capacity;
size_t size;
void **array;
} ch_vect;
```

The `capacity`

is the actual memory allocated for the `ch_vect`

vector internal `ch_vect->array`

. This may, or may be not fully used.

The `size`

is the actual number of elements in the `ch_vect`

. It’s the exact length we use for iteration (`i<vect->size`

).

`VECT_INIT_CAPACITY`

represents the initial `capacity`

for the `ch_vect`

.

`VECT_GROWTH_MULTI`

is the multiplicator the `ch_vect->array`

. Whenever we are about to remain without space, we perform another allocation of size `VECT_GROWTH_MULTI * ch_vect->capacity`

.

The value of `VECT_GROWTH_MULTI`

is ideally a number in the `[1, 2]`

interval. For simplicity we’ve picked `2`

, but there’s a risk our `array`

will grow faster than it’s needed; doubling its `size`

every time might be an exaggeration.

#### The interface

When it comes to the interface, for simplicity, we will limit ourselves in implementing only the functions we are going to use:

```
ch_vect* ch_vect_new(size_t capacity);
ch_vect* ch_vect_new_default();
void ch_vect_free(ch_vect *vect);
void* ch_vect_get(ch_vect *vect, size_t idx);
void ch_vect_set(ch_vect *vect, size_t idx, void *data);
void ch_vect_append(ch_vect *vect, void *data);
```

`ch_vect_new`

is the constructor-like function. It accepts only a parameter which is the initial `ch_vect->capacity`

.

`ch_vect_newdefault`

would’ve been the overloaded `ch_vect_new`

method that uses `capacity=VECT_INIT_CAPACITY`

as the default param value. Unfortunately, C doesn’t support function overloading, so we had to give it another name.

`ch_vect_free`

is the destructor-like function. It only de-allocates the memory of the structure itself, but not for the data.

`ch_vect_get`

is used to access an item from the internal array (`ch_vect->array`

) at the specified index `idx`

.

`ch_vect_set`

is used to set the value of an item from the internal array (`ch_vect->array`

) at the specified index.

`ch_vect_append`

appends an element at the end of the `ch_vect->array`

. In case there’s not enough allocated space for it, it allocates a new array.

It’s important to understand there’s not a good idea to interact with `ch_vect->array`

directly. If you do this, `ch_vect->size`

won’t be updated, so growth is not guaranteed to work.

##### Allocating an de-allocating memory

The code is definitely standard for both the constructor and the destructor:

```
ch_vect* ch_vect_new(size_t capacity) {
ch_vect *result;
result = malloc(sizeof(*result));
if (NULL==result) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
result->capacity = capacity;
result->size = 0;
result->array = malloc(result->capacity * sizeof(*(result->array)));
if (NULL == result->array) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
return result;
}
ch_vect* ch_vect_new_default() {
return ch_vect_new(VECT_INIT_CAPACITY);
}
void ch_vect_free(ch_vect *vect) {
free(vect->array);
free(vect);
}
```

It’s a bad idea to call

`exit(EXIT_FAILURE)`

if you are building a library. You need to give the program a chance to recover from an error. So don’t do it in practice.

##### Reading and setting data

Again, there’s nothing fancy.

```
void* ch_vect_get(ch_vect *vect, size_t idx) {
if (idx >= vect->size) {
fprintf(stderr, "cannot get index %lu from vector.\n", idx);
exit(EXIT_FAILURE);
}
return vect->array[idx];
}
void ch_vect_set(ch_vect *vect, size_t idx, void *data) {
if (idx >= vect->size) {
fprintf(stderr, "cannot get index %lu from vector.\n", idx);
exit(EXIT_FAILURE);
}
vect->array[idx] = data;
}
```

##### Appending an element

Appending a new element to the `ch_vect`

should take into consideration the following:

- It actual
`size`

of the vector is equal or becomes bigger than the`capacity`

we need to:- Compute a
`new_capacity`

;- Before computing it, take care of potential overflows;

- Allocate a new array
`new_array`

with`new_capacity`

; - Copy all elements from the old array
`ch_vect->array`

to the new array`new_array`

; - Free the memory associated with the old array
`ch_vect->array`

; - Update the
`ch_vect->array`

so it points to the`new_array`

.

- Compute a

The equivalent code for what has been described above is the following:

```
void ch_vect_append(ch_vect *vect, void *data) {
if (!(vect->size < vect->capacity)) {
// Check for a potential overflow
uint64_t tmp = (uint64_t) VECT_GROWTH_MULTI * (uint64_t) vect->capacity;
if (tmp > SIZE_MAX) {
fprintf(stderr, "size overflow\n");
exit(EXIT_FAILURE);
}
size_t new_capacity = (size_t) tmp;
void *new_array = malloc(new_capacity * sizeof(*(vect->array)));
if (NULL==new_array) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
memcpy(new_array, vect->array, vect->size * sizeof(*(vect->array)));
free(vect->array);
vect->array = new_array;
vect->capacity = new_capacity;
}
vect->array[vect->size] = data;
vect->size++;
}
```

`SIZE_MAX`

is a C99 macro that describes the maximum possible value for a `size_t`

type.

### Updating the existing `ch_hash`

structure to use `ch_vect`

for buckets

Our initial `ch_hash`

structure from the previous chapter Separate Chaining (using Linked Lists), and its associated interface won’t suffer a lot of changes.

We will simply create another version, and to make a distinction between the two we will name it: `ch_hashv`

(with `v`

from `v`

ector at the end):

```
typedef struct ch_hashv_s {
size_t capacity;
size_t size;
ch_vect **buckets;
ch_key_ops key_ops;
ch_val_ops val_ops;
} ch_hashv;
// VERSUS
typedef struct ch_hash_s {
size_t capacity;
size_t size;
ch_node **buckets;
ch_key_ops key_ops;
ch_val_ops val_ops;
} ch_hash;
```

As you can see, only the type of the `buckets`

changes: `ch_node **buckets`

vs. `ch_vect **buckets`

.

The interface will remain identical as well.

For the actual methods, we are going to keep 90% of the code from the previous implementation. But, instead of using a `while`

loop for iterating through the **linked list**, a `for`

loop will be used for iterating through the **dynamically-expanding array** (`ch_vect`

).

In case you are curious about the changes and the implementation of `ch_hashv`

, you can take a look at the code directly on github:

## Separate Chaining (Red Black Trees optimization)

From a practical perspective, the `ch_hashv`

improves the read times for the **hash table** because it reduces the number of *cache misses* introduced by our use of **linked lists**.

But from a theoretical perspective searching in a bucket is still `O(N)`

, where `N`

is the number of elements in the bucket. So, how can we improve the reads further (`ch_hash_get()`

)?

In this regard, we can introduce another optimization:

- We can measure the number of colliding elements inserted in a bucket;
- If this number increases, after a certain threshold, we can “morph” our bucket into a red-black tree.

Without getting into many details, **red-black trees** are binary search trees are self-balancing themselves during the insertion and deletion of new elements. This means that searching performance doesn’t degrade, and it will remain in logarithmic bounds.

This is the route the creators of Java took when `HashMap`

was implemented.

## Open Addressing

Compared to **Separate Chaining**, a **hash table** implemented with **Open Adressing** stores only one element per bucket. We handle collisions by inserting the colliding pairs to unused slots in the *bucket* array.

Finding unused locations in the *bucket* array is achieved through a probing algorithm that determines what the is second (or the *nth*) most *natural* index if the previous ones are occupied.

The most accessible probing algorithm is called **linear probing**. In case of collision, we iterate over each bucket (starting with the first bucket computed), until we find an empty slot to make the insertion.

To avoid probing for new slots in excess, we need to keep the load factor of the **hash table** at a satisfactory level, and the hash function should have remarkable diffusion properties. If the load factor (defined as `size/capacity`

) reaches a certain threshold, we increase the buckets and perform full-rehashing.

If we fail to increase the number of buckets, clusters of adjacent elements will form. ** Clustering** diminishes the performance of both read and insert operations because we will need to iterate more over more buckets to obtain the correct value.

For example, python’s `dict`

implementation uses a more advanced variant of **Open Adressing**.

Compared to the **Separate Chaining** approach, cache misses are reduced because we operate on a single contiguous block of memory (the array of buckets). And, as long as we use a decent **hash function**, and the load factor is low, it can lead to superior performance, especially for read operations.

To better understand let’s take a look at the following diagram:

We want to insert `<key, value>`

pairs with the keys (`char*`

) from the set: [`"A"`

, `"B"`

, `"C"`

, etc.]:

- First, we insert
`"A"`

. The corresponding bucket for`"A"`

(after we compute the hash) is`0`

; - Then we insert
`"B"`

. The corresponding bucket for`"B"`

is`0`

. But`0`

is occupied by`"A"`

. So, by applying**linear probing**we go to the next index, which`1`

, and it’s free. So`"B"`

is now inserted at bucket`1`

; - Then we insert
`"C"`

. The corresponding bucket for`"C"`

is`0`

. But`0`

is occupied by`"A"`

, the next bucket,`1`

is occupied by`"B"`

, so we end-up inserting`"C"`

to ` 2`.

Let’s look further; what is happening for `"D"`

, `"E"`

, `"F"`

, `"G"`

, `"H"`

is the beginning of a *not* so lovely cluster of elements: areas in the array of buckets where intertwined elements are grouped together.

Having intertwined groups leads to decreased performance. Think of it, for reading the value associated with `"G"`

we have to iterate over an area that is naturally associated with bucket number `7`

(eg., `"F"`

).

Clustering usually happens for two reasons:

- The load factor (size/capacity) is close to
`1`

, and we need to allocate more empty buckets to increase the*spacing*between elements; - The hash function doesn’t have good diffusion properties, and it’s biased towards specific buckets.

Reducing Clustering can also be achieved by changing **linear probing** to another algorithm to identify the next good bucket (e.g., **quadratic probing**).

### Tombstones

Compared to **Separate Chaining**, deleting elements in a **hash table** that uses **Open Addressing**, is relatively more challenging to implement.

After a delete operation occurs, we cannot simply empty the bucket (associate `NULL`

with it). If we do that, we might break a sequence of entries and unjustly isolate some. The separated entries will become unreachable for the following read operations. They become reachable only if the previous *sequence* is somehow *restored* through a *lucky* insertion.

One solution would be to rehash everything after each delete. But think of it for a moment; this means to allocate a new array of buckets, calculate the new index (bucket) for each element, and then free the memory associated with the old and *broken* array. It’s a costly and unacceptable endeavor, especially when there are better alternatives.

One alternative for avoiding full rehashing is to introduce the notion of **tombstones**. Each time a delete operation occurs, instead of emptying the bucket, we put a sentinel value, metaphorically called **a tombstone**.

The tombstone will behave differently based on the operation.

If we want to perform a `read`

operation or another `delete`

, the **tombstone** will act just like an actual entry; probing will ignore it and continue further. This way, the rest of the entries are not isolated from the others.

If we want to perform a `put`

(insert) operation, the **tombstone** will act as a very inviting empty slot.

A high density of **tombstones** will increase the load factor, just like the actual entries do, so an intelligent **hash table** implementation needs to consider this.

There are ways of avoiding **tombstones** altogether, and if you are interested to read about this, check this article. But, for simplicity and academic purposes, our **hash table** will use **tombstones**.

### A generic implementation

If you want to jump directly into the code, without reading the explanation,s you can clone the following repo:

```
git clone git@github.com:nomemory/open-adressing-hash-table-c.git
```

Similar to the implementations for **Separate Chaining**, we will use the `void*`

pointer to achieve some sort of genericity.

#### The model

For the model layer, we will keep almost the same structures as before.

```
typedef struct oa_key_ops_s {
uint32_t (*hash)(const void *data, void *arg);
void* (*cp)(const void *data, void *arg);
void (*free)(void *data, void *arg);
bool (*eq)(const void *data1, const void *data2, void *arg);
void *arg;
} oa_key_ops;
typedef struct oa_val_ops_s {
void* (*cp)(const void *data, void *arg);
void (*free)(void *data, void *arg);
bool (*eq)(const void *data1, const void *data2, void *arg);
void *arg;
} oa_val_ops;
```

`oa_key_ops_s`

and `oa_val_ops_s`

are collections of functions that are related to the data kept inside the keys and values.

```
typedef struct oa_pair_s {
uint32_t hash;
void *key;
void *val;
} oa_pair;
```

The `oa_pair_s`

is the structure corresponding to the actual `<key, value>`

entry.

```
typedef struct oa_hash_s {
size_t capacity;
size_t size;
oa_pair **buckets;
void (*probing_fct)(struct oa_hash_s *htable, size_t *from_idx);
oa_key_ops key_ops;
oa_val_ops val_ops;
} oa_hash;
```

`oa_hash_s`

is the actual structure behind our **hash table** implementation:

`capacity`

- the number of buckets;`size`

- the number of elements (gets incremented each time we add a new element, and decremented when a removal is performed);`buckets`

- the actual references to our`oa_pairs`

;`probing_fct`

- the probing algorithm (eg., linear probing);`key_ops`

- key related operations;`val_ops`

- value related operations;

`probing_fct`

is a *pointer function* that allows our users to choose the algorithm for probing.

For example, for linear probing, we can come with something like this:

```
static inline void oa_hash_lp_idx(oa_hash *htable, size_t *idx) {
(*idx)++;
if ((*idx)==htable->capacity) {
(*idx) = 0;
}
}
```

`oa_hash_lp_idx`

is a simple function that increments the index (`idx`

). If we reach the end of the *bucket array* we simply start again.

We can also write a function for **quadratic probing** later and pass it to the **hash table**. It’s good to offer some flexibility, after all.

A few constants are also defined:

```
#define OA_HASH_LOAD_FACTOR (0.75)
#define OA_HASH_GROWTH_FACTOR (1<<2)
#define OA_HASH_INIT_CAPACITY (1<<12)
```

`OA_HASH_LOAD_FACTOR`

- The maximum accepted load factor.`OA_HASH_GROWTH_FACTOR`

- The growth factor.`OA_HASH_INIT_CAPACITY`

- The initial capacity (nuber of buckets for the**hash table**).

#### The interface

The interface is again relatively straightforward:

```
// Creating anew hash table
oa_hash* oa_hash_new(oa_key_ops key_ops, oa_val_ops val_ops, void (*probing_fct)(struct oa_hash_s *htable, size_t *from_idx));
oa_hash* oa_hash_new_lp(oa_key_ops key_ops, oa_val_ops val_ops);
// Destructor like method for destroying the hashtable
void oa_hash_free(oa_hash *htable);
// Adding, Reading, Deleting entries
void oa_hash_put(oa_hash *htable, const void *key, const void *val);
void *oa_hash_get(oa_hash *htable, const void *key);
void oa_hash_delete(oa_hash *htable, const void *key);
void oa_hash_print(oa_hash *htable, void (*print_key)(const void *k), void (*print_val)(const void *v));
// Pair related
oa_pair *oa_pair_new(uint32_t hash, const void *key, const void *val);
// String operations
uint32_t oa_string_hash(const void *data, void *arg);
void* oa_string_cp(const void *data, void *arg);
bool oa_string_eq(const void *data1, const void *data2, void *arg);
void oa_string_free(void *data, void *arg);
void oa_string_print(const void *data);
```

##### Creating/Destroying a **hash table**

It’s always a good practice to start writing constructor-like and destructor-like functions for `oa_hash`

structure.

`oa_hash_new`

is the constructor-like function for dynamically allocating an`oa_hash`

function on the heap;`oa_hash_free`

is a destructor-like function that frees the memory associated with`oa_hash`

and its elements.

```
oa_hash* oa_hash_new(
oa_key_ops key_ops,
oa_val_ops val_ops,
void (*probing_fct)(struct oa_hash_s *htable, size_t *from_idx))
{
oa_hash *htable;
htable = malloc(sizeof(*htable));
if (NULL==htable) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
htable->size = 0;
htable->capacity = OA_HASH_INIT_CAPACITY;
htable->val_ops = val_ops;
htable->key_ops = key_ops;
htable->probing_fct = probing_fct;
htable->buckets = malloc(sizeof(*(htable->buckets)) * htable->capacity);
if (NULL==htable->buckets) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
for(int i = 0; i < htable->capacity; i++) {
htable->buckets[i] = NULL;
}
return htable;
}
```

In practice, it’s not a good idea to free the memory associated with the pairs, but for simplicity our implementation frees the memory:

```
void oa_hash_free(oa_hash *htable) {
for(int i = 0; i < htable->capacity; i++) {
if (NULL!=htable->buckets[i]) {
htable->key_ops.free(htable->buckets[i]->key, htable->key_ops.arg);
htable->val_ops.free(htable->buckets[i]->val, htable->val_ops.arg);
}
free(htable->buckets[i]);
}
free(htable->buckets);
free(htable);
}
```

Given the fact we are going to use **linear probing** for our implementation we can *overload* the allocator to use the previously defined algorithm for **linear probing**:

```
oa_hash* oa_hash_new_lp(oa_key_ops key_ops, oa_val_ops val_ops) {
return oa_hash_new(key_ops, val_ops, oa_hash_lp_idx);
}
```

##### Modeling Tombstones

We will need a way to model **tombstones** for our **hash table**. In this regard we will call a tombstone a non-`NULL`

`oa_pair`

element with `oa_pair->hash=0`

, `oa_pair->key=NULL`

and `oa_pair->val=NULL`

.

Then we write a function that checks if a certain bucket is a **tombstone**:

```
inline static bool oa_hash_is_tombstone(oa_hash *htable, size_t idx) {
if (NULL==htable->buckets[idx]) {
return false;
}
if (NULL==htable->buckets[idx]->key &&
NULL==htable->buckets[idx]->val &&
0 == htable->buckets[idx]->key) {
return true;
}
return false;
}
```

And another function that puts a tombstone at given bucket index every time we delete an element:

```
inline static void oa_hash_put_tombstone(oa_hash *htable, size_t idx) {
if (NULL != htable->buckets[idx]) {
htable->buckets[idx]->hash = 0;
htable->buckets[idx]->key = NULL;
htable->buckets[idx]->val = NULL;
}
}
```

##### Growing the bucket capacity if needed

Let’s define a metric to track down the load on the *buckets*: `load_factor=size/capacity`

. If the load factor is bigger than `0.75`

, our **hash table** performance might drop.

In this regard, we will define a function `oa_hash_should_grow`

that will check after each addition if we need to grow the **hash table**.

```
#define OA_HASH_LOAD_FACTOR (0.75)
inline static bool oa_hash_should_grow(oa_hash *htable) {
return (htable->size / htable->capacity) > OA_HASH_LOAD_FACTOR;
}
```

We will continue by writing the growth method `oa_hash_grow`

. This method will:

- check if the new bucket capacity doesn’t overflow;
- allocate a new memory zone for the new buckets;
- perform a complete rehash of all the elements (skipping any potential tombstone).
- free the memory associated with the old buckets.

```
inline static void oa_hash_grow(oa_hash *htable) {
uint32_t old_capacity;
oa_pair **old_buckets;
oa_pair *crt_pair;
// Check if the new bucket capacity doesn't overflow;
uint64_t new_capacity_64 = (uint64_t) htable->capacity * OA_HASH_GROWTH_FACTOR;
if (new_capacity_64 > SIZE_MAX) {
fprintf(stderr, "re-size overflow in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
old_capacity = htable->capacity;
old_buckets = htable->buckets;
// Allocate a new memory zone for the new buckets;
htable->capacity = (uint32_t) new_capacity_64;
htable->size = 0;
htable->buckets = malloc(htable->capacity * sizeof(*(htable->buckets)));
if (NULL == htable->buckets) {
fprintf(stderr,"malloc() failed in file %s at line # %d", __FILE__,__LINE__);
exit(EXIT_FAILURE);
}
for(int i = 0; i < htable->capacity; i++) {
htable->buckets[i] = NULL;
};
// Perform a complete rehash of all the elements (skipping any potential tombstone).
for(size_t i = 0; i < old_capacity; i++) {
crt_pair = old_buckets[i];
if (NULL!=crt_pair && !oa_hash_is_tombstone(htable, i)) {
oa_hash_put(htable, crt_pair->key, crt_pair->val);
htable->key_ops.free(crt_pair->key, htable->key_ops.arg);
htable->val_ops.free(crt_pair->val, htable->val_ops.arg);
free(crt_pair);
}
}
// Free the memory associated with the old buckets.
free(old_buckets);
}
```

##### Getting the correct index

The next step is to implement a function that retrieves the bucket where we perform `oa_hash_get`

, `oa_hash_put`

or `oa_hash_delete`

operations.

```
static size_t oa_hash_getidx(oa_hash *htable, size_t idx, uint32_t hash_val, const void *key, enum oa_ret_ops op) {
do {
if (op==PUT && oa_hash_is_tombstone(htable, idx)) {
break;
}
if (htable->buckets[idx]->hash == hash_val &&
htable->key_ops.eq(key, htable->buckets[idx]->key, htable->key_ops.arg)) {
break;
}
htable->probing_fct(htable, &idx);
} while(NULL!=htable->buckets[idx]);
return idx;
}
```

The input params of the function are:

`htable`

- this represents the**hash table**where we operate;`idx`

- this is the starting index from where we will start probing (using`htable->probing_fct`

, the**pointer function**supplied at construction-time);`hash_val`

- the`hash`

of the value we are searching;`key`

- the`key`

for which we are operating;`op`

- the operation. For example, if we`PUT`

an element, tombstones won’t be ignored, but if we use this function tp`GET`

or`DELETE`

elements, tombstones will act just as normal elements.

`idx`

, or the starting index is usually obtained like this:

```
uint32_t hash_val = htable->key_ops.hash(key, htable->key_ops.arg);
size_t idx = hash_val % htable->capacity;
```

`idx`

is the *natural* choice for each entry, but in the case of **hash collisions**, we need to find another free index. Here’s where the `oa_hash_getidx`

functions come into play. It returns the most natural choice starting from `idx`

.

##### Adding an element to the **hash table**

The steps to add (`oa_hash_put`

) an element inside the **hash table** are the following:

- We grow the
**hash table**if necesary; - We check if there is an empty bucket to insert the element;
- If it’s not empty, we probe for another suitable bucket;
- We insert the element;

```
void oa_hash_put(oa_hash *htable, const void *key, const void *val) {
if (oa_hash_should_grow(htable)) {
oa_hash_grow(htable);
}
uint32_t hash_val = htable->key_ops.hash(key, htable->key_ops.arg);
size_t idx = hash_val % htable->capacity;
if (NULL==htable->buckets[idx]) {
// Key doesn't exist & we add it anew
htable->buckets[idx] = oa_pair_new(
hash_val,
htable->key_ops.cp(key, htable->key_ops.arg),
htable->val_ops.cp(val, htable->val_ops.arg)
);
} else {
// // Probing for the next good index
idx = oa_hash_getidx(htable, idx, hash_val, key, PUT);
if (NULL==htable->buckets[idx]) {
htable->buckets[idx] = oa_pair_new(
hash_val,
htable->key_ops.cp(key, htable->key_ops.arg),
htable->val_ops.cp(val, htable->val_ops.arg)
);
} else {
// Update the existing value
// Free the old values
htable->val_ops.free(htable->buckets[idx]->val, htable->val_ops.arg);
htable->key_ops.free(htable->buckets[idx]->key, htable->key_ops.arg);
// Update the new values
htable->buckets[idx]->val = htable->val_ops.cp(val, htable->val_ops.arg);
htable->buckets[idx]->key = htable->val_ops.cp(key, htable->key_ops.arg);
htable->buckets[idx]->hash = hash_val;
}
}
htable->size++;
}
```

##### Removing an element from the **hash table**

The steps to remove (`oa_hash_delete`

) an element from the **hash table** are the following:

- We check if the bucket is empty. If it is, we simply return;
- If the bucket is not empty we check if the element should be removed or not;
- If it’s not the good element, it means we need to probe to find it.
- We free the memory associated with the element;

```
void oa_hash_delete(oa_hash *htable, const void *key) {
uint32_t hash_val = htable->key_ops.hash(key, htable->key_ops.arg);
size_t idx = hash_val % htable->capacity;
if (NULL==htable->buckets[idx]) {
return;
}
idx = oa_hash_getidx(htable, idx, hash_val, key, DELETE);
if (NULL==htable->buckets[idx]) {
return;
}
htable->val_ops.free(htable->buckets[idx]->val, htable->val_ops.arg);
htable->key_ops.free(htable->buckets[idx]->key, htable->key_ops.arg);
oa_hash_put_tombstone(htable, idx);
}
```

##### Retrieving an element from the **hash table**

Retrieving an element is again a straight-forward function to implement:

```
void *oa_hash_get(oa_hash *htable, const void *key) {
uint32_t hash_val = htable->key_ops.hash(key, htable->key_ops.arg);
size_t idx = hash_val % htable->capacity;
if (NULL==htable->buckets[idx]) {
return NULL;
}
idx = oa_hash_getidx(htable, idx, hash_val, key, GET);
return (NULL==htable->buckets[idx]) ?
NULL : htable->buckets[idx]->val;
}
```

#### Putting all together

```
int main(int argc, char *argv[]) {
oa_hash *h = oa_hash_new(oa_key_ops_string, oa_val_ops_string, oa_hash_lp_idx);
oa_hash_put(h, "Bucharest", "Romania");
oa_hash_put(h, "Sofia", "Bulgaria");
printf("%s\n", oa_hash_get(h, "Bucharest"));
printf("%s\n", oa_hash_get(h, "Sofia"));
return 0;
}
```

If you want to read more about **Open Addressing** techniques, checkout my new blog post. The code is in Java, but hey, if you can read C, Java should be easier to grasp.

# References

- Hash Functions and Hash Tables, Breno Helfstein Moura
- Crafting Interpreters - Hash Tables, Robert Nystrom
- Hash functions
- CS240 – Lecture Notes: Hashing
- Hash Functions: An Empirical Comparison
- CSci 335 Software Design and Analysis - Chapter 5 Hashing and Hash Tables, Steward Weiss
- CSE 241 Algorithms and Data Structures - Chosing hash functions
- Integer hash functions, Thomas Wang
- Notes on Data Structures and Programming Techniques, James Aspnes
- The FNV Non-Cryptographic Hash Algorithm
- Hash Tables - Open Addressing vs Chaining;
- Optimizing software in C++, Agner Fog
- Why did the designers of Java preferred chaining over open addressing
- Deletion from hash tables without tombstones
- Traits

## Comments