dict Algorithm
The dict algorithm is a data structure and lookup algorithm often used in computer programming languages, such as Python, to organize and manage key-value pairs in an efficient way. The dict algorithm, short for "dictionary," is based on the concept of a hash table and is designed to facilitate fast access to values based on their unique keys. In a dictionary, each key is associated with a value or set of values, and the algorithm allows users to retrieve these values quickly by searching with the corresponding key. The underlying data structure of a dictionary is an array, where each element of the array is a bucket that can store multiple key-value pairs. The dict algorithm uses a hash function to map each key to a specific bucket in the array, enabling rapid access to the associated value.
One of the main strengths of the dict algorithm is its ability to perform lookups, insertions, and deletions in constant time, on average. This is achieved by using a hash function that distributes the keys uniformly across the array, minimizing the number of collisions and thus reducing the time it takes to search for a particular key. In the case of collisions, where multiple keys map to the same bucket, the dict algorithm typically employs techniques like chaining (using linked lists to store colliding key-value pairs) or open addressing (probing for the next available slot in the array) to resolve the conflicts. To maintain efficient performance as the dictionary grows, the dict algorithm may also employ dynamic resizing, where the size of the underlying array is increased and the key-value pairs are rehashed to distribute them evenly across the new array. Overall, the dict algorithm provides a highly efficient and versatile data structure for organizing and accessing information based on unique keys.
#include <stdio.h>
#include <stdlib.h>
#include "dict.h"
/* simple constructor */
Dictionary * create_dict(void)
{
Dictionary * p_dic = malloc(sizeof (Dictionary));
if (p_dic)
{
p_dic->number_of_elements = 0;
/* initializes the elemens of the array with NULL-pointer */
for (int i = 0; i < MAXELEMENTS; i++)
{
p_dic->elements[i] = NULL;
}
return p_dic;
}
else
{
printf("unable to create a dictionary\n");
return NULL;
}
}
/*
utility function
sdbm hash algorithm
returns a hashcode for the given string 's'
*/
int get_hash(char s[])
{
unsigned int hash_code = 0;
/* iterates over string at each character */
for (int counter = 0; s[counter]!='\0'; counter++)
{
/* actual computing of the hash code */
hash_code = s[counter] + (hash_code << 6) + (hash_code << 16) - hash_code;
}
/* % modulo is for fitting the index in array. */
return hash_code % MAXELEMENTS;
}
int add_item_label(Dictionary * dic,char label[],void * item)
{
unsigned int index = get_hash(label);
/* make sure index is fitting */
if (index < MAXELEMENTS)
{
dic->elements[index] = item;
return 0;
}
/* error case */
return -1;
}
int add_item_index(Dictionary * dic , int index, void * item)
{
/* make sure whether this place is already given */
if (!dic->elements[index])
{
dic->elements[index] = item;
return 0;
}
/* error case */
return -1;
}
void * get_element_label(Dictionary * dict, char s[])
{
int index = get_hash(s);
if (dict->elements[index])
{
return dict->elements[index];
}
printf("None entry at given label\n");
return NULL;
}
void * get_element_index(Dictionary * dict, int index)
{
if (index >= 0 && index < MAXELEMENTS)
{
return dict->elements[index];
}
printf("index out of bounds!\n");
return NULL;
}
void destroy(Dictionary * dict)
{
free(dict);
}
