PSET5 Speller遇Segmentation Fault，求指针排查及MurmurHash实现指导

Let's tackle your two main issues step by step: first squashing that segmentation fault, then adding a robust MurmurHash implementation to replace your current hash function.

1. Fixing the Segmentation Fault #

Looking through your code, there are two clear culprits causing the segfault:

a. Invalid Null Pointer Access in check() #

In your check function, after the while loop finishes (when temp is NULL), you have this extra check:

if (temp->next == NULL && strcasecmp(temp->word, new_word) == 0) {
    return true;
}

When the loop exits, temp is already NULL, so accessing temp->next or temp->word will try to read memory at address 0—boom, segfault. This check is redundant anyway: the while loop already iterates through every node in the linked list. If the word wasn't found during the loop, it's not present. Remove this block entirely.

b. Unhandled Empty Buckets in unload() #

In your unload function, you immediately try to access cursor->next without checking if cursor is NULL first. If a bucket in your hash table is empty (no nodes), table[i] will be NULL, so cursor will be NULL, and cursor->next will trigger a segfault.

Update the unload function to handle empty buckets:

bool unload(void) {
    // Loop through each bucket in the hash table
    for(int i = 0; i < N; i++) {
        node *cursor = table[i];
        // Only process if the bucket isn't empty
        while(cursor != NULL) {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

This revised loop safely skips empty buckets and frees all nodes in non-empty ones without dereferencing null pointers.

c. Redundant Hash Modulo Check #

Your current hash function already applies % N on every iteration, so the line if( n > N) n = n % N; in both check and load is redundant (and since n is an unsigned int, it can't be negative, but the modulo in the hash function ensures it's already within 0 to N-1). You can remove these lines to clean up the code.

2. Implementing MurmurHash2 #

MurmurHash is a fast, non-cryptographic hash function that produces much better distribution than your current polynomial rolling hash, which will reduce collisions and speed up your speller. Here's a tailored implementation for your speller program (using MurmurHash2, which is simple and effective for strings):

// Hashes word to a number using MurmurHash2
unsigned int hash(const char *word) {
    const unsigned int seed = 0x9747b28c; // Arbitrary seed value
    unsigned int h = seed;
    const unsigned char *data = (const unsigned char *)word;
    unsigned int len = strlen(word);

    // Mix 4 bytes at a time for speed
    while (len >= 4) {
        unsigned int k = *(unsigned int *)data;
        k *= 0x5bd1e995;
        k ^= k >> 24;
        k *= 0x5bd1e995;
        h *= 0x5bd1e995;
        h ^= k;
        data += 4;
        len -= 4;
    }

    // Handle remaining bytes for shorter strings
    switch(len) {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0];
                h *= 0x5bd1e995;
    };

    // Final mixing steps to ensure all input bits affect the output
    h ^= h >> 13;
    h *= 0x5bd1e995;
    h ^= h >> 15;

    // Map hash to our bucket range
    return h % N;
}

This implementation:

• Uses a standard, arbitrary seed (you can adjust this if needed)
• Processes 4 bytes at a time for optimal speed
• Handles leftover bytes for short strings
• Applies final mixing to avoid biased hash distributions
• Ends with % N to fit the hash value into your bucket count

Final Notes #

After making these changes, recompile your program and run it with Valgrind again—the segfault should be gone, and your hash table will have far fewer collisions, making the speller faster and more efficient.

内容的提问来源于stack exchange，提问作者Megapunk