Hash in C

 

Agenda

• Hash
• Hash Collision
• Rehashing
• Chaining
• Algorithm
• Application

Hash

Hash is most common used data structure in every day programming. If you are python developer every time you use dict or set, it internally uses hashing. In perl you call it as hash using {}. Or HashSet or HashMap in Java.

There are different ways to save data, for example in a variable, arrays, structures and so on. Hash is yet another way to save data. To say the most simple reason is if we have key and value pair we can use hash for quick save and retrieval.

There are three perquisites for hashing, given below:

• key
• value
• hash function
• Key: Unique data to store the value
• Value: Data which needs to be associated with the Key

Hash Function: Function used compute the hash code from the given key. The given hash code will be the index for us to save value. For each key the hash function is expected to give us unique hash code(index).

Fig 1: Explains each key goes through hash function and based on its output index values are saved.

Credits: https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

Hash Collision

Hash Collision is a flaw of the hash function which generates same hash code for two different keys.

Eg: We have two keys k1 and k2, when the h(k1) and h(k2) generates same hash code, how will the data stored and retrieved.

A good hash function is one that minimizes the collisions and spreads the records uniformly throughout the table.

There are two basic techniques to resolve this,  rehashing and chaining.

Rehashing

The simplest method to place the record in the next available position of the array. This techniques is also  called linear probing.

If array location h(key) is already occupied by a record. A general rehash(rh) function is called rh(h(key)). If it is already occupied then again rh(rh(h(key))) is called.

However it is possible for the rehash function to called in a loop indefinitely, even if there are many empty functions.

Chaining

Another method of resolving the hash clashes is called chaining. It involves keeping the distinct linked list for all the records whose keys hash to the particular value.

Below find the nice representation of chained hash table, credits to wikipedia.

Fig 2: A small phone book as hash table using chaining mechanism

Credits : https://en.wikipedia.org/wiki/Hash_table

Algorithm

• Create an array of structure
• Define a hash function to accept key as input and return the index. Note: There are several ways to define the hash function, we have chose the basic one.

• Search function
• Get the index by calling the hash function passing the key
• Validate if the index exists
• If exists loop through the index
• Match the given in each of the chain structure pointed to the index
• If found return the structure address pointer
• Else return NULL
• Insert function
• Call the Search function passing the key to determine whether the given key is already present
• If it is present, override with the new value
• Else create a new entry
• Return NULL if there is no memory for the new entry

Source code:

/* pointer array size */

#define HASHSIZE 101

/* structure to save the key and value */

struct nlist {

struct nlist *next; /* next entry in chain */

char *key; /* defined key */

char *value; /* replacement text which holds value */

}

/* pointer table to save list of structures */

static struct nlist *hashtab[HASHSIZE]

/* hash: form hash value for string s which is key */

unsigned hash(char *s) {

/* unsigned value ensures non negative */

unsigned hashval;

/* adds each character's value of the string to form scrambled combination of the previous ones */

for (hashval =0; *s != '\0'; s++) {

hashval = *s + 31 * hashval;

}

/* modulo ensures the index is within the array size */

return hashval % HASHSIZE

}

/* lookup: look for s in the hash table */

struct nlist *lookup(char *s) {

struct nlist *np;

for (np = hashtab[hash[(s)]; np != NULL; np = np->next) {

if(strcmp(s, np->key) == 0) {

return np;

}

}

/* key not found in hash table */

return NULL;

}

/* insert: add the key and value to the hash table */

struct nlist *insert(char *key, char *value) {

struct nlist *np;

unsigned hashval;

/* call the lookup function to validate if already key exists */

/* if not exists allocate the memory for the new structure */

if ((np = lookup(key)) == NULL) {

np = (struct nlist *) malloc(sizeof*np));

/* if unable to allocate memory for the structure */

/* or unable to copy key in the struct key */

/* return NULL as it no more memory could be allocated */

if (np == NULL || (np->key = strdup(key)) == NULL) {

return NULL;

}

/* get the index for the key, by calling the hash function */

hashval = hash(key);

/* point the newly created structure's next to the existing index value's struct */

np->next = hashtab[hashval];

/* point the current pointer to the head of the index */

/* so the newly created pointer will be pointed as first */

hashtab[hashval] = np;

} else {

/* if already the key is available, free up its value so we can override below */

free((void *) np->value);

}

/* save the value to the key's structure */

if((np->value = strdup(value)) == NULL) {

return NULL;

}

}

Note: Chaining mechanism is used above to avoid hash collisions

Application

Now that we have seen about hash and its implementation, lets see its common applications. 

In Cryptography hash functions are used to produce the hashed output from the input, which is impossible to reverse from output to input.

Password verification is another important usage of cryptography hash function. When you enter the password, from the client the password is hashed and sent to server. As the server already knows the hash of your password it can simply compare it. If there is an middleman attack your password is still unknown to the hacker.

Rabin Karp string search algorithm, uses hashing to find set of patterns in the string. And the real world application of it is to detect plagiarism.

Reference and Credits: 

K&R C Programming Language

Practical Cryptography for DevelopersHash Functions - Practical Cryptography for Developers

Original Blog Posted in OSFY

https://www.opensourceforu.com/2021/10/working-with-hash-in-c/

For further research and updates maintaining the blog here.

Memory Allocation Methods

Agenda

• Introduction

• First Fit

• Best Fit

• Worst Fit

• Conclusion

Introduction

    Each time when malloc (memory allocation) or free is called you get pointer to the allocated memory address or free it back for others to use. Dynamic memory management requires frequent memory allocation and freeing up the space. 

    How to manage the freed and used space. How do we know which address/slots to be used while the next malloc call.  To answer above questions, there are three methods which we can used for managing the memory.

    Let's discuss each method in detail. Below is the current state of one large block of 1024bytes. We will see how each method uses for allocation of memory.

0 1023

Address	0	250	550	700	900	950 - 1023
Allocation Details	Block 1 allocated Size = 250	Free 1 Size = 300	Block 2 allocated Size = 150	Free 2 Size = 200	Block 3 allocated Size = 50	Free 3 Size = 73

Note: In this blog we would see only first bit algorithm. Each of these methods have their own use cases. But in general First Fit method is usually preferred.

First Fit

In the First Fit method, the free list is traversed sequentially to find the first free block which can hold the requested size. 

Once we the block is found, one the below two operations are performed.

• If the size is equal to the requested amount, it is removed from the free list

• Else split into two parts. Here the first portion remains on the list and second is allocated.

  The reason of allocating the second part is the operations of updating the list could be avoided by just making change in size of the free node.

Lets now try to allocate 200, and see how the structure gets changed.

0 1023

Address	0	250	350	550	700	900	950 - 1023
Allocation Details	Block 1 allocated Size = 250	Free 1 Size = 100	Block 2 allocated (new) Size = 200	Block 3 allocated Size = 150	Free 2 Size = 200	Block 4 allocated Size = 50	Free 3 Size = 73

As you could see the memory is allocated in the second part, leaving the previous block pointing to the first part. Else if we would have used first part, we need to make change in the list by pointing the previous to the second part. 

Now lets see the algorithm:

p = freeblock; alloc = null;  // pointer to store the allocated size n's address q = null; // find the free node which can allocate the given size n while ( p != null && size(p) < n) { q = p;  // previous node p = next(p);  }  // if there is block large enough found if ( p != null ) { s = size(p); alloc = p + s – n; // alloc contains the address of the desired block // if the block size matches the requested size, remove the block from the free list if ( s == n) { // if the match is found in the first block update the pointer of freeblock to point the next of free block if ( q == null ) { freeblock = next(p); } else { next(q) = next(p); } } else { size(p) = s – n;  // adjust the size of the remaining free block } }

Best Fit

    In the Best Fit method, the smallest of the free block is choose whose size is greater than or equal to the requested size n. In this algorithm has to traverse the entire list to find the apt match.

Let's now try to allocate 200, and see how the structure gets changed.

0 1023

Address	0	250	550	700	900	950 - 1023
Allocation Details	Block 1 allocated Size = 250	Free 1 Size = 300	Block 2 allocated Size = 150	Block 3 allocated (new) Size = 200	Block 4 allocated Size = 50	Free 2 Size = 73

    As you could see the memory Free 1 was ignored, Free 2 was updated to Block 3. Also now the Free 1 is pointing to Free 3 (now changed to Free 2). As the requested size matches the allocated size and its removed from the free pointer list.

Worst Fit

    In the Worst Fit method, the algorithm always allocates the portion of the largest free block in memory. The logic behind this method that by using a small number of very large blocks repeatedly to satisfy the majority of the requests, many of the moderately sized blocks will be left unfragmented.

Let's now try to allocate 200, and see how the structure gets changed.

0 1023

Address	0	250	350	550	700	900	950 - 1023
Allocation Details	Block 1 allocated Size = 250	Free 1 Size = 100	Block 2 allocated (new) Size = 200	Block 3 allocated Size = 150	Free 2 Size = 200	Block 4 allocated Size = 50	Free 3 Size = 73

As Free 1 hold the maximum of 300, the memory is allocated there. Lets try to allocate 100, though we have first Free size with 100 it will still allocate in Free 2 which is the maximum now.

Conclusion

Each method has its own patterns. Let's see it with example.

First Fit is best case

In the below scenario only First Fit was able to serve all the requests. 

Request	Blocks remaining using
	First Fit	Best Fit	Worst Fit
Initially	110, 54	110, 54	110, 54
25	85, 54	110, 29	85, 54
70	15, 54	40, 29	15, 54
50	15, 4	Cannot be full filled	15, 4
14	1, 4		1, 4
1	0, 4		1, 3
4	0, 0		Cannot be full filled

Notes: Let's try to understand how the First Fit serves best.

• Here we have 110 in block 1 and 54 in block 2, initially
• Now comes the request of 25 to allocate, lets see if we try to allocate in each method:
• First Fit after allocation 85, 54
• Best Fit after allocation 110, 29
• Worst Fit after allocation 85, 54
• Next we want to allocate 70, 
• First Fit after allocation 15, 54
• Best Fit after allocation 40, 29
• Worst Fit after allocation 15, 54
• Next we want to allocate 50,
• First Fit after allocation 15, 4
• In Best Fit we cannot allocate
• Worst Fit after allocation 15, 4
• So now repeating the requests, we could see of the First Fit is able to serve all the requests whereas in other even though there is space it cannot allocate.

Best Fit is best case

In the below scenario only Best Fit was able to serve all the requests. 

Request	Blocks remaining using
	First Fit	Best Fit	Worst Fit
Initially	110, 54	110, 54	110, 54
50	60, 54	110, 4	60, 54
100	Cannot be full filled	10, 4	Cannot be full filled

Worst Fit is best case

In the below scenario only Worst Fit was able to serve all the requests. 

Request	Blocks remaining using
	First Fit	Best Fit	Worst Fit
Initially	200, 300, 100	200, 300, 100	200, 300, 100
150	50, 300, 100	50, 300, 100	200, 150, 100
100	50, 200, 100	50, 300, 0	100, 150, 100
125	50, 75, 100	50, 175, 0	100, 50, 100
100	50, 75, 0	50, 75, 0	0, 50, 100
100	Cannot be full filled	Cannot be full filled	0, 50, 0

As said, each have their own patterns. Though first fit method is generally preferred.

References and Credits

https://www.codingninjas.com/blog/2021/09/04/memory-management-techniques-in-operating-system/

Data Structures using C and C++ by Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbanum 

Original Blog Posted in OSFY

https://www.opensourceforu.com/2021/10/memory-allocation-methods-an-overview/

For further research and updates maintaining the blog here.