Hash Functions and Hash Tables

Question 1

What do they represent

Answer 1

Dynamic set of data

Question 2

Which three functions do they support?

Answer 2

1) Insert
2) Search
3) Delete

Question 3

What is the average runtime for their search operation?

Answer 3

O(1)

Question 4

What is a dictionary in the world of code?

Answer 4

Generic way to map keys to values

Question 5

What is a hash table

Answer 5

The implementation of a dictionary using a hash function

Question 6

What is closed addressing/open hasing?

Answer 6

Where each slot in the table refers to a chain of entries, and each entry stores one (key, value) pair

Question 7

What is open addressing/closed hasing?

Answer 7

Search for the next empty bucket within the hash table

Question 8

What is the code to allocate a hash table and setting it’s elements to NULL?

Answer 8

dict_t *make_dictionary(void) {
dict_t *hashtable = malloc(sizeof(dict_t) * TABLESIZE);
assert(hashtable != NULL);
for (int i = 0; i < TABLESIZE; i++) {
hashtable[i] = NULL;
}
return hashtable;
}

Question 9

What does the hash’s structure look like?

Answer 9

typedef struct entry {
char *key;
char *value; // value associated with the key
struct entry *next; // next entry in the linked list
} entry_t;

Question 10

What is the run time to look up a value?

Answer 10

O(n)

Question 11

What is the run time to look up a key?

Answer 11

O(1)

Question 12

What is the code to print the contents of a dictionary?

Answer 12

void print_dictionary(dict_t *dict)
{
for (int bucket_index = 0; bucket_index < TABLESIZE; bucket_index++) {
printf(“%d: “, bucket_index);
entry_t *current_entry = dict[bucket_index];
if (current_entry == NULL) {
printf(“NULL\n”);
} else {
while (current_entry != NULL) {
printf(“%s: %s”, current_entry->key, current_entry->value);
current_entry = current_entry->next;
if (current_entry != NULL) {
printf(“, “);
}
}
printf(“\n”);
}
}
}

Question 13

What is the code to be able to replace what is in a dictionary?

Answer 13

_Bool replace(dict_t *dict, char *key, char *value)
{
unsigned hash_index = hash(key);
entry_t *target_entry = search(dict[hash_index], key);
if (target_entry == NULL) {
return false;
} else {
free(target_entry->value);
target_entry->value = my_strdup(value);
assert(target_entry->value != NULL);
return true;
}
}

Question 14

What is the code to clear a dictionary?

Answer 14

void clear(dict_t *dict)
{
for (int bucket_index = 0; bucket_index < TABLESIZE; bucket_index++) {
entry_t *current_entry = dict[bucket_index];
while (current_entry != NULL) {
entry_t *entry_to_free = current_entry;
current_entry = current_entry->next;
free(entry_to_free->key);
free(entry_to_free->value);
free(entry_to_free);
}
dict[bucket_index] = NULL;
}
}