Return to Answer

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.

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.

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.

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.

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

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

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.

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

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

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.