Hash table using open-addressing with linear probing

Question

I've written a hash-table implementation. This is the first time I've written such code. The hash-table uses open-addressing with linear probing. The hash function is still subject to change as I found out some properties of it that make it particulary bad for my application.

Could you please review the code and tell me if there are any problems? You can find the code at GitHub.

Code

The code consists of a Makefile, a source file file ht.c and a header file ht.h. The file main.c is a simple test program that reports the amount of entries moved on average to fill in entries into a hashtable at least twice the size of the entries.

Makefile

OUT=main
OBJ=ht.o main.o

$(OUT): $(OBJ)

.PHONY: clean

clean:
    $(RM) $(OBJ) $(OUT)

ht.c

/* hash table */

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

#include "ht.h"

struct ht {
    int bits;
    uint32_t randoms[256];
    ht_value_t table[];
};

/* state for xorshift rng */
static uint32_t xstate = 0;

#define BITMASK(bits) ((bits) == 32 ? 0xffffffff : (1<<(bits))-1)
#define MODINC(bits,index) (((index)+1) & BITMASK(bits))

static void init_xorshift(void) {
    if (xstate == 0) xstate = time(NULL);
}

static uint32_t xorshift(void) {
  xstate ^= xstate << 13;
  xstate ^= xstate >> 17;
  xstate ^= xstate << 5;
  return xstate;
}

static uint32_t hash(ht_t *ht,ht_key_t key) {
    union { ht_key_t key; uint8_t bytes[8]; } ukey;
    int i;
    uint32_t accum = 0;

    ukey.key = key;
    for (i=0;i<8;i++) accum ^= ht->randoms[ukey.bytes[i]];

    return accum;
}

/* tweakable based on actual way to retrieve key */
static ht_key_t get_key(ht_value_t val) {
    return *val;
}

ht_t *ht_new(int bits) {
    ht_t *ht;
    int i,bitmask;

    if (bits < 0 || bits >= 32) return NULL;

    ht = malloc(sizeof*ht + (1<<bits)*sizeof*ht->table);

    ht->bits = bits;

    init_xorshift();

    /* initiate hash function */
    bitmask = BITMASK(bits);
    for (i=255;i>=0;i--) ht->randoms[i] = xorshift()&bitmask;

    memset(ht->table,0,1<<bits);

    return ht;
}

void ht_free(ht_t *ht) {
    free(ht);
}

int ht_put(ht_t *ht,ht_key_t key,ht_value_t value) {
    uint32_t index = hash(ht,key);
    ht_value_t tmp;
    int iters = 0;

    while (ht->table[index] != NULL && get_key(ht->table[index]) != key) {
        tmp = ht->table[index];
        ht->table[index] = value;
        index = MODINC(ht->bits,index);
        value = tmp;
        iters++;
    }

    ht->table[index] = value;

    return iters;
}

int ht_del(ht_t *ht,ht_key_t key) {
    uint32_t hkey = hash(ht,key), index, tindex;
    ht_key_t ckey;
    int iters = 0;

    for (index = hkey;;index = MODINC(ht->bits,index)) {
        if (ht->table[index] == NULL) return -1;
        ckey = get_key(ht->table[index]);
        if (hash(ht,ckey) != hkey) return -1;
        if (ckey == key) break;
    }

    ht->table[index] = NULL;

    while(ht->table[index]!=NULL&&hash(ht,get_key(ht->table[index]))==hkey){
        tindex = index;
        index = MODINC(ht->bits,index);
        ht->table[tindex] = ht->table[index];
        ht->table[index] = NULL;
        iters++;
    }

    return iters;
}

ht_value_t ht_get(ht_t *ht,ht_key_t key) {
    uint32_t hkey = hash(ht,key), index = hkey, ckey;

    while (ht->table[index] != NULL
      && hash(ht,ckey = get_key(ht->table[index])) == hkey) {
        if (ckey == key) return ht->table[index];
        index = MODINC(ht->bits,index);
    }

    return NULL;
}

ht.h

/* hash table */

#ifndef HT_H
#define HT_H

typedef struct ht ht_t;
typedef uint64_t ht_key_t;
typedef ht_key_t *ht_value_t;

ht_t *ht_new(int bits);
/* ht_put and ht_del return number of items moved or -1 if key
 * already exists (ht_put) / not found (ht_get).
 * ht_value_t must point to the same key we used at insertion */
int ht_put(ht_t*,ht_key_t,ht_value_t);
int ht_del(ht_t*,ht_key_t);
ht_value_t ht_get(ht_t*,ht_key_t);
void ht_free(ht_t*);

#endif /* HT_H */

main.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>

#include "ht.h"

int main(int argc,char *argv[]) {
    int count, i, bits=0;
    int misses = 0;
    ht_key_t *values;

    srandom(time(NULL));

    if (argc != 2 || sscanf(argv[1],"%d",&count) != 1) return EXIT_FAILURE;

    for (i=count;i;bits++)i>>=1;
    ht_t *ht = ht_new(bits);

    values = malloc(count*sizeof*values);

    for (i=count;i>0;i--) {
        values[i] = random();
        misses += ht_put(ht,values[i],values+i);
    }

    printf("%.2f\n",misses/(float)count);
    return EXIT_SUCCESS;
}

Answer 1

1. Bugs

1. The algorithm in ht_get is incorrect:

   while (ht->table[index] != NULL
     && hash(ht,ckey = get_key(ht->table[index])) == hkey) {
       if (ckey == key) return ht->table[index];
       index = MODINC(ht->bits,index);
   }
   

   You are assuming here that if you find a key with a different hash in your probe sequence, then this means that the key you are looking for is not there. But that's not right. Try the following test program:

   #include <stdint.h>
   #include <stdio.h>
   #include "ht.h"
   #define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
   int main(int argc, char *argv[]) {
       uint64_t k[] = {0x12345671, 0x11223344, 0x22334411, 0x33441122};
       ht_t *ht = ht_new(2);
       for (size_t i = 0; i < ARRAY_LENGTH(k); ++i) {
           ht_put(ht, k[i], &k[i]);
       }
       printf("%p\n", ht_get(ht, k[0]));
       return 0;
   }
   

   You'll need to run it a few times (because of the randomization in your hash function), but I find that about half the time this prints 0x0 because k[0] failed to be found in the hash table (even though it must be there since it was the first key that was added).

2. The algorithm in ht_del is also incorrect. As Knuth writes, "Many computer programmers have great faith in algorithms, and they are surprised to find that the obvious way to delete records from a hash table doesn't work." (The Art of Computer Programming Vol. III, p. 533.)

   First, here:

   for (index = hkey;;index = MODINC(ht->bits,index)) {
       if (ht->table[index] == NULL) return -1;
       ckey = get_key(ht->table[index]);
       if (hash(ht,ckey) != hkey) return -1; /* <-- UH-OH */
       if (ckey == key) break;
   }
   

   On the indicated line you conclude that key can't be in the table because you've found a key with a different hash in your probe sequence. But this isn't right: there might very well be keys with different hashes interleaved in the same probe sequence (this is particularly likely in your case because you use the same probe sequence for every key).

   Second, after deleting the key you continue with the probe sequence, shifting the keys along so that there are no gaps. But this is wrong: if any of those keys have different hashes to key, then moving them can cause them not to be findable any more.

   If you want to get this right, Knuth gives an algorithm (pp. 533–4) for deletion in a open hash table with linear probing, but since linear probing is itself not a particularly good idea (see 2.3 below), it's better to do what most open hash table implementations do, which is to mark a key as deleted by putting a placeholder (some constant KEY_DELETED) in its place. (Combined with automatic growing and rehashing; see 2.4 below.)

3. If the table gets full, then ht_put will go into an infinite loop.

   Also, if the table is full, and if all the keys have the same hash, then ht_get and ht_del will go into infinite loops.

   It's best to avoid all these problems by automatically growing and rehashing before the table gets full. See 2.4 below.

2. Other important issues

1. It's not easy to choose a good general-purpose hash function, so it's a bad sign that you are trying to invent your own. It would be much better to choose a well-known and well-tested function, for example from Wikipedia's list of hash functions. For general data, Bernstein's hash is simple and fast; and for integers there's Knuth's multiplicative hash.

   In particular, the hash function you have chosen has a couple of undesirable properties:

   1. A byte makes the same contribution to the hash wherever it appears in the key, so that all permutations of a sequence of bytes have the same hash. For example, 0x11223344 has the same hash as 0x44332211 and 0x22441133.

   2. Pairs of bytes in the key with the same value do not contribute to the hash (because their hashes cancel). So 0x1212 has the same hash as 0x3434 and 0x5656, not to mention 0x0000 and many other keys.

2. You base the hash function on a pseudo-random sequence seeded by the current time. Varying the hash function like this has an important downside: it makes the code harder to test because the behaviour changes from run to run. So why are you doing this?

   I can only guess that you are doing this because you want your hash table to be robust against the collision attack. But if so, your remedy won't be effective, because:

   1. Your choice of hash function makes it trivial to construct large numbers of colliding keys (see above) regardless of the seed;

   2. time only has resolution in seconds, so it is likely that an attacker will be able to guess or reconstruct your seed value;

   3. 32 bits of randomness are well within the scope of a brute force search in any case.

   If you really need to be robust against the collision attack you need a robust hash function, a secure source of randomness, and substantially more than 32 bits of randomness. See section 5 of Crosby & Wallach.

3. Linear probing is well known to be bad. Knuth writes, "Experience with linear probing shows that the algorithm works fine until the table begins to get full; but eventually the process slows down, with long drawn-out searches becoming increasingly frequent." (The Art of Computer Programming, vol. III, p. 527).

   To avoid this, you should use a different probe sequence for each key. See Knuth pp. 528–531.

4. Your hash table is fixed in size, so it's going to perform worse and worse as it gets full. In a few applications, this might not matter because you know how big your hash table is going to be at the start. But for most applications you don't know this, and so it's important to be able to grow and rehash the table automatically when it gets full enough that its performance degrdes significantly.

5. When you get a collision in ht_put, you store the new value at the location and move the old value to the next location in the probe sequence (possibly shifting a whole sequence of keys along as you go).

   If you have a reason for this, you ought to explain it. I suppose it makes the newly inserted value quicker to retrieve, but (a) this seems likely to be bad for cache performance (it unnecessarily dirties all the locations visited by the probe sequence); and (b) if you are getting lots of collisions, it's better to grow the table (see 2.4 above) than to mess about like this.

3. Minor issues

1. There are very few comments. Someone reading the code would like to know explanations for your design decisions. Here are a few questions I would have liked to be answered by appropriate comments:

   1. What is the role of bits in the hash table structure? (Answer: the table size is always a power of two, and bits gives the logarithm of the size.)

   2. What is the role of randoms in the hash table structure? (Answer: some of them are exclusive-ored to make the hash.) But why does each hash table need its own set?

   3. What is the purpose of seeding the random array from the clock? (Possible answer: because you don't want the hash function to be computable by an attacker?)

   4. Why is xstate a global variable? Why does each hash table need to have a different sequence of pseudo-random numbers?

   5. Why do you generate the pseudo-random numbers in reverse order?

2. There are a few poorly chosen names. Generally it's best to pick a name for a function that describes the purpose of the function. For example, although MODINC does compute a modulus and an increment, that's pretty useless thing to know. What you actually use it for is to generate the probe sequence. So a better name would something like NEXT_INDEX.

3. What are you planning to use this hash table for? It appears to implement a set of unsigned integers (that is, there are unsigned integer keys, but no values). This is fine if that's what you need, but it's not really very general.

4. Each hash table structure stores 1024 bytes of pseudo-random data in addition to the table. This will create a lot of space overhead in applications that use many small tables. (For example, some dynamic programming languages, notably Python, represent objects as a hash table mapping attribute name to attribute value. It would be disastrous to have 1 KiB of overhead on every object.)

5. There are some mysterious integer constants in the code whose purpose would be clearer if you explicitly showed how you computed them.

   1. Why 256?

      uint32_t randoms[256];
      

      This needs one entry for each possible value of a byte, so #include <limits.h> and write 1 << CHAR_BIT.

   2. Why 8?

      union { ht_key_t key; uint8_t bytes[8]; } ukey;
      

      This needs to be the size of key in bytes, so write sizeof(ht_key_t).

   3. Why 8 here?

      for (i=0;i<8;i++) accum ^= ht->randoms[ukey.bytes[i]];
      

      This needs to be the number of elements in ukey.bytes, so I suggest defining a macro:

      #define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
      

      and then writing ARRAY_LENGTH(ukey.bytes).

   4. Why 255 here?

      for (i=255;i>=0;i--) ht->randoms[i] = xorshift()&bitmask;
      

      This needs to be the number of elements in ht->randoms, less 1, so write ARRAY_LENGTH(ht->randoms) - 1.

6. Since ht.h depends on stdint.h (for the definition of uint64_t), it ought to include it.

7. You represent an index into the hash table with a uint32_t. This restricts your hash table to 2³² entries, even on 64-bit platforms, and means that you need an ugly special case in the BITMASK macro. Why not use size_t for the index into the hash table and drop the special case? A similar remark applies to the hash values: there's no particular reason to restrict these to 32 bits either.