29 February 2012

Hash tables with 2 keys

Let's say you have a structure, which has an identifier (a string), an index (a number), and various data. I tried to find a good solution to create a hash table in which I would be able to search for an element after its identifier or its number. This is what I came up with:
typedef struct {
    char* identifier;
    int index;
    void* data;
} my_type_t;
So obviously, when we're adding the element to the table, we calculate the hash value of the identifier.
int hash = hash_function(my_struct->identifier);
Next, we generate the index based on the hash value. We simply keep an incremented value in each hash table slot, multiply it by the hash table size and add the hash value, and then simply add the structure to the list.
my_struct->index = (hash_table[hash]->add_structure_to_list(my_struct, hash_table[hash]);
hash_table[hash]->current_index += 1;
Now, when we want to search for an element in the hash table we do the following:
In order to look after an identifier:
int hash = hash_function(identifier);
for (element=hash_table[hash]->head;element;element=element->next) {
    if (!strcmp(element->identifier, identifier)) {
        return element;
    }
}
In order to look after an index we simply do a modulo operation. The value resulted is exactly the hash value that was generated when the element was added to the list, and will be the same as the hash value calculated by the function if applied to the identifier of the element.
int hash = index % hash_size;
for (element=hash_table[hash]->head;element;element=element->next) {
    if (element->index == index) return element;
}

No comments:

Post a Comment