Return to Revisions

1. Bugs

1. The algorithm in ht_del is 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.)

1. 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 also loop infinitely.

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.

3. 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.

1. 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.

1. 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.

2. 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:

2. 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.)

3. 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?

4. 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?)

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

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

7. 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.

8. 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.

9. 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.)

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

11. 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.

12. 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).

13. 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).

14. 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.

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