C program for hashing with chaining. In hashing there is a hash function that maps keys to some values. But these hashing function may lead to collision that is two or more keys are mapped to same value. Chain hashing avoids collision. The idea is to make each cell of hash table point to a linked list of records that have same hash function value. . dictionary.c. Computer Science 50. Problem Set 6. Implements a dictionary's functionality. Functions/definitions in this program are used in speller.c to help create a. spellchecker. Functions include load, unload, check, and size. Load runs. through a text file full of words and loads them into memory as a hash table. (dictionary).
This is a C Program to Implement a Hash Table using Singly Linked List.
A hash table is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots. This program will implement hash table where at each array index, we will create a Linked List, to prevent key collision. Key having same index will be stored in Linked List as it can store multiple data.
Problem Solution
1. Create an array of Linked List (i.e a hash table).
2. Take a key and a value to be stored in hash table as input.
3. Corresponding to the key, an index will be generated i.e every key is stored in a Linked List of a particular array index.
4. Using the generated index, extract the Linked List located in that array index.
5. In case of absence of a Linked List, create one and insert a data item(key and value) into it and increment the size of hash table.
6. In case the list already exists, search for the key (given as input) in the Linked List, and add the data item (key and value) at the end of list if key does not belong to the list and increment the size, otherwise update the value of given (and already present) key in the Linked List.
7. To display all the elements of hash table, Linked List at each index is extracted and elements(key and value) are read until we reach at its end.
8. To remove a key from hash table, we will first calculate its index and extract its Linked List, find the key in list and remove it if it is present.
9. Exit
2. Take a key and a value to be stored in hash table as input.
3. Corresponding to the key, an index will be generated i.e every key is stored in a Linked List of a particular array index.
4. Using the generated index, extract the Linked List located in that array index.
5. In case of absence of a Linked List, create one and insert a data item(key and value) into it and increment the size of hash table.
6. In case the list already exists, search for the key (given as input) in the Linked List, and add the data item (key and value) at the end of list if key does not belong to the list and increment the size, otherwise update the value of given (and already present) key in the Linked List.
7. To display all the elements of hash table, Linked List at each index is extracted and elements(key and value) are read until we reach at its end.
8. To remove a key from hash table, we will first calculate its index and extract its Linked List, find the key in list and remove it if it is present.
9. Exit
Here is the source code of the C Program to Implement a Hash Table chaining with Singly Linked List. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.
Program Explanation
1. Create a structure, node (Linked List item) with key and value as data and next as a pointer variable which points the structure element of node type.
2. Create another structure, arrayitem (for Linked List) with head having the address of first element of Linked List and tail having the address of last element of Linked List.
3. Now create an array of Linked List of some certain size (10, in this case).
4. A menu is displayed on the screen.
5. User must choose one option from four choices given in the menu.
6. 1st choice: Inserting item into hash table
(a) Take a key and a value as input.
(b) Calculate index as per the given key.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, check whether the key already present in it by finding the location of key using find() method which returns -1 if key is not present. In that case, we will create a data item and add it to the end of Linked List. If key is already present in the list, we will get its location index and extract the element using get_element() function and update its value.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, then create a data item and a Linked List and add the data item to it.
7. 2nd choice: Removing a key from hash table
(a) Take a key as input which needs to be removed.
(b) Calculate index as per the given key.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, find the location index of the key in Linked List using find() method which returns -1 if key not present. The key is removed using remove() method if it is present otherwise ‘Key not present’ message will get displayed.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, therefore no deletion is required.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment its size by 1.
(b) The size of the hash table can be determined either by size variable or size_of_hashtable() method.
2. Create another structure, arrayitem (for Linked List) with head having the address of first element of Linked List and tail having the address of last element of Linked List.
3. Now create an array of Linked List of some certain size (10, in this case).
4. A menu is displayed on the screen.
5. User must choose one option from four choices given in the menu.
6. 1st choice: Inserting item into hash table
(a) Take a key and a value as input.
(b) Calculate index as per the given key.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, check whether the key already present in it by finding the location of key using find() method which returns -1 if key is not present. In that case, we will create a data item and add it to the end of Linked List. If key is already present in the list, we will get its location index and extract the element using get_element() function and update its value.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, then create a data item and a Linked List and add the data item to it.
7. 2nd choice: Removing a key from hash table
(a) Take a key as input which needs to be removed.
(b) Calculate index as per the given key.
(c) Locate the Linked List at the calculated array index.
(d) If Linked List is present, find the location index of the key in Linked List using find() method which returns -1 if key not present. The key is removed using remove() method if it is present otherwise ‘Key not present’ message will get displayed.
(e) If there is no Linked List at that particular array index, which means the key is not present in hash table, therefore no deletion is required.
8. 3rd choice: Size of hash table
(a) Each time we add a new data item into the hash table, we increment its size by 1.
(b) The size of the hash table can be determined either by size variable or size_of_hashtable() method.
9. 4th choice: Display hash table
(a) Function display() runs for displaying hash table contents.
(b) Here a for loop runs from 0 to array_size-1 with i as iterator.
(c) The code inside loop consists of taking i as index and locating each Linked List at that index of array.
(d) As the content of each node of Linked List is displayed the next variable (pointer)
is used to proceed further until the end of list is reached.
(a) Function display() runs for displaying hash table contents.
(b) Here a for loop runs from 0 to array_size-1 with i as iterator.
(c) The code inside loop consists of taking i as index and locating each Linked List at that index of array.
(d) As the content of each node of Linked List is displayed the next variable (pointer)
is used to proceed further until the end of list is reached.
![C program to implement dictionary using hashing functions pdf C program to implement dictionary using hashing functions pdf](http://orion.lcg.ufrj.br/Dr.Dobbs/books/book3/160_b.gif)
Sanfoundry Global Education & Learning Series – 1000 C Programs.
« Prev Page - C Program to Implement Adjacency List
» Next Page - C Program to Implement Hash Tables with Quadratic Probing