One of those interesting yet tricky to translate to code concepts. Yup, another data structure. But hash tables are actually really cool and efficient to store data of any type (char, int, double..etc.) what is a hash table?Hash tables are another type of data structure, used to store, manipulate and search data (of any type) in a table format. It is used mainly because of its O(1) time complexity to store and access data. (very efficient and time effective) A hash table can have n number of elements, so it can basically be any number. In this case, I chose 5, just to start things easy, but it can also be 100, or 50, 60..etc. So basically the whole idea of a hash table is to store the given data (in this case ints) in every row of the table. In order to decide where to store which number, we derive a hash function. So what is a hash function? How do we decide which one to use? hash functionSo how would you derive your hash function to figure out where to place the keys (a fancy word for data values)? You can basically choose any hash function that works best. For instance, the hash function h(x) = x, basically maps the key to the index with the same value as key. So in that case this would look like: Obviously, there is a problem that arises with this hash function. You would need to allocate numerous spaces in the table, depending on the largest value in your given key data. For instance, if the largest value in the key data is a 23, then you would need to allocate 24 spaces (ranging from 0-23) in your hash table. This will lead to a lot of memory usage, and wasted memory usage for the slots that don't have keys in them. Ok, so then we need to figure out a hash function where you use up less memory but at the same time store the key values efficiently. We can use the modulus (%) function to help us. So, in our 5 slots example, we can set the hash function to be h(x) = x % n, where n is the number of slots, so it would be h(x) = x % 5. So it takes the key, does mod 5 to it, and places the key to the index that matches the result. So if we do 16 % 5 = 1, we get 1 and we place it at index 1. Ok, cool. So this works, and its efficient too since you are using less space for a certain number of elements. But what if I wanted to add another element, such as 33? So first, lets use the hash function on 33. 33 % 5 = 3. So we place it at index 3.....but WAIT. There is already a number at index 3. 23. This is known as collision. When we try to place a number to an index that is already taken by some other number. So how would we tackle such collision? What do we do now? the solution...chainingWhen we encounter such collision, we need to use an effective way to store both of those numbers at index 3 (23 and 33). So we use chaining. This time when creating the hash table, we create an array of pointers. When we insert an element into the hash table, we use the hash function to go the corresponding index, and then make new node so that the pointer in that index points to the node. So, gradually, as more elements are added, we basically make a linked list at every index. See how nice that looks? This is much more of an organized yet effective way of storing data. You basically use linked lists (another data structure which links one node - or piece of data - to another node until the last one points to NULL) inside of a table of pointers. You can easily access the element by implementing the hash function first, going to the index, and then finding the element. Now lets go to the hard part: converting all of this to C code.
1 Comment
2/28/2024 07:25:50 am
Cloud computing refers to the delivery of computing services, including storage, processing power, and software, over the internet. It allows users to access resources on-demand, without the need for physical hardware or infrastructure. Cloud computing offers scalability, flexibility, and cost-effectiveness, enabling businesses to efficiently manage their IT resources. Users can store data, run applications, and access services from remote servers maintained by cloud providers. This technology has revolutionized how organizations deploy and manage their computing resources in today's digital landscape.
Reply
Leave a Reply. |
Archives
March 2021
Topics
All
|