1. hash(word)
Purpose: Convert a string into a bucket index (0 to N-1)
unsigned int hash(const char *word) {
unsigned int sum = 0;
for (int i = 0; word[i] != '\0'; i++) {
sum += tolower(word[i]);
}
return sum % N;
}
This sums ASCII values of lowercase letters and uses modulo to ensure the result fits within 0 to N-1. This is a simple hash function - more sophisticated ones use prime numbers, polynomial rolling, or cryptographic methods.
2. load(file)
Purpose: Read data from a file and populate the hash table
Steps:
- Open the file for reading
- Read each string/word with fscanf or fgets
- Allocate memory for a new node (check for NULL!)
- Copy the string into node with strcpy
- Hash the string to get bucket index
- Insert node at head of bucket's linked list (update pointers)
- Increment item count
3. check(key)
Purpose: Verify if a key exists in the hash table
bool check(const char *word) {
unsigned int index = hash(word);
for (node *cur = table[index]; cur != NULL; cur = cur->next) {
if (strcasecmp(word, cur->word) == 0) return true;
}
return false;
}
Hash the key to find its bucket, then search only that bucket's linked list using string comparison. This is O(1) average case, O(n) worst case if all items hash to the same bucket.
4. size()
Purpose: Return count of items in the hash table
unsigned int size(void) {
return word_count;
}
Returns in O(1) time because we maintain a counter during insertions in load().
5. unload()
Purpose: Free all allocated memory
bool unload(void) {
for (int i = 0; i < N; i++) {
node *cur = table[i];
while (cur) {
node *tmp = cur;
cur = cur->next;
free(tmp);
}
}
return true;
}
Critical: Use a temp pointer! Once you free(cur), you can't access cur->next anymore.