Scribd
Importer
6 vues19 pages

DSA Module-5 Part-B

Le document traite des structures de données, en particulier du hachage, qui permet d'effectuer des recherches en temps constant O(1) en utilisant une fonction de hachage pour mapper des clés à des indices dans une table de hachage. Il aborde également les techniques de résolution de collisions, telles que le probing linéaire, et présente différentes méthodes de hachage, y compris la méthode de division, la méthode du carré central et la méthode de multiplication. Enfin, il souligne l'importance d'une bonne fonction de hachage pour minimiser les collisions et optimiser le stockage des données.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
6 vues19 pages

DSA Module-5 Part-B

Le document traite des structures de données, en particulier du hachage, qui permet d'effectuer des recherches en temps constant O(1) en utilisant une fonction de hachage pour mapper des clés à des indices dans une table de hachage. Il aborde également les techniques de résolution de collisions, telles que le probing linéaire, et présente différentes méthodes de hachage, y compris la méthode de division, la méthode du carré central et la méthode de multiplication. Enfin, il souligne l'importance d'une bonne fonction de hachage pour minimiser les collisions et optimiser le stockage des données.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Lecture Notes Data Structures and Applications [BCS304] Hashing Linear search and binary search are the two well known searching techniques. In both the techniques the data to be searched for goes through several comparisons. For example, in linear search the data to be searched for is compared with elements starting from first to last one by one until the key is found or the search is unsuccessful. Similarly in binary search the data to be searched for is compared with the middle element, if it is less than the middle element, then searching is continued in the first half else search is continued in the second half. The search time for both techniques depends on the number of elements. However, if we need a search technique to perform the search operation in O(1) time, then we need to use hashing. The objective of hashing is to minimize the comparisons, The basic idea is not to search for the correct position of data with comparisons but to compute the position / index of data within the hash table using the hash function Consider a scenario for storing data about 100 employee records, where each record is uniquely identified by the field Emp_ID. If the Emp_ID is in the range of 0 to 99, then to store the records, Emp_ID itself can be used as "index" to store the records. This is as shown in the following figure. Key Array of Employees’ Records Key0 —» [0] | Employee record with Emp_ID 0 Key 1 —> [1] | Employee record with Emp_1D 1 Key 2 —> [2] | Employee record with Emp_1D 2 Employee record with Emp_ID 98 Employee record with Emp_ID 99 An employee record for a particular Emp_ID can be easily accessed because index = Emp_ID. However, this would not be practically feasible Assume that the company uses a five digit Emp_ID. In this case the Emp_ID values range from 00000 to 99999. If we use the technique describe above, then an array of size 100000 is required to store 100 employee records. This is as shown below. Key Array of Employees’ Records Key 00000 —> [0] _| Employee record with Emp_1D 00000 Employee record with Emp_ID n Key 99998 —> [99998] | Employee record with Emp_ID 99998 Key 99909 —> [99999] | Employes record with Emp_ID 90999 Module 5 1 Lecture Notes Data Structures and Applications [BCS304] Whether we use a 2-digit Emp_ID (primary key) or a S-digit key, the number of employees is limited in this case to 100 and hence it would be impractical to use so much of storage space for storing 100 employee records. Another alternative to reduce the array size is to use the last 2-digits of the primary key (Emp_ID) to get the index of the array Example: The employee with Emp_ID 59349 will be stored in the element of the array with index 49. The employee with Emp_ID 12345 will be stored in the element of the array with index 45. In this method the employee record is not stored according to the value of key (Emp_ID), instead, the S-digit key is converted to 2-digit index The function which is used to convert the key to index is called hash function and the array which stores the records is called hash table. Hashing is the process of indexing the data so that sorting, searching, inserting and deleting data becomes fast. ‘Now, if we need to store an employee record with Emp_ID 23749, then index = 49. However, an employee record with Emp_ID 59349 would have been already stored at index = 49. This results in collision, Dr. Mahesh G Professor Hash Table Dept of CSE, BMSIT & M Itis a data structure in which keys are mapped to array positions by a hash function. Example: The key 23749 is mapped to the array position 49 using the hash function 23749 % 1000. Ina hash table, an element with key ‘k'is stored at index hk). The hash function ‘his used to calculate the index at which the element with key 'k’ will be stored. The following shows the relationship between keys and the hash table index. 0 4 | NULL 2 3 4 | NULL 5 | NULL 6 | NULL it 8 [NULL 9 Note: 1) Keys K2 and K6 point to the same memory location, resulting in collision 2) Keys KS and K7 also point to the same memory location, and hence collide. Module 5 2 Lecture Notes Data Structures and Applications [BCS304] Hash Function A hash function is a mathematical formula which when applied to a key, produces an integer which can be used as index for the key in the hash table Properties / Characteristics of Good Hash Function 1) Low cost - The function must be very easy and quick to compute. 2) Determinism - The function must produce the same hash value for a given input value. 3) Uniformity - The function must as far as possible, uniformly distribute the keys so that, there are minimum number of collisions. Dr. Mahesh G Different Types of Hash Functions fe rcanin 1) Division Method Choose a number 'm' larger than the number of keys 'n’. The hash function divides 'k' by 'm' and uses the remainder. It is defined by H(k) = k mod m H(k) is the hash index generated for key 'k’ and is the remainder when k is divided by m. Example: Consider the keys to be stored in the hash table to be 64, 52, 79, 36. Then using the division method the keys are stored as shown below. Choose a number m = 10 H(64) = 64 % 10 // 64 to be placed at address 4 H(52) = 52% 10=2 // 52 to be placed at address 2 H(79) = 79 % 10=9 // 79 to be placed at address 9 H(36) = 36 % 10=6 1/36 to be placed at address 6 0 1 2 3 4 5 6 a 8 9 32 64 36 79 2) Mid Square Method Step 1: Square the value of the key ie, find k? Step 2: Extract the middle '’ digits of 7 In this method the key to be stored 'k’ is squared and the hash function is defined by H(k) = mid part of k? Note: H(k) must be obtained by deleting digits from both ends of k?and the same position of K? must be used for all keys Example: Consider the data to be stored in the hash table to be 3111, 2345. Then using the mid square method data is stored as shown below. 3111? = 9678321 2345? = 5499025 Assuming the size of the hash table to be 1000, the middle 3 digits can be taken as hash address H(111) = 783 1/3111 to be placed at address 783 H(2345) = 990 // 2345 to be placed at address 990 Module 5 3 Lecture Notes Data Structures and Applications [BCS304] Assuming the size of the hash table to be 100, the fourth and fifth digits counting from the right can be taken as hash address HG111)=78 // 3111 to be placed at address 78 H(2345) = 99 1/ 2345 to be placed at address 99 plication Method : Choose a constant 'A’ such that 0 | 2 >{K x Ke} [st = 3 >{Kol 1K x | \ 4 NULL \ Vd IK] fk] K- 5 [NULL Actual keys $ ne ax (W) —| => IM @_ [NULL ——>1 9 —>[Ke] [Kx Example: Insert the keys 7, 24, 18, 52, 36, $4, 11, and 23 in a chained hash table of 9 memory locations. Use H(k) = k mod m In this case, m=9. Initially, the hash table can be given as ae Step 1 key =7 Step2 —key= 24 7 =24 SN h(k) = 7 mod 9 h(k) = 24 mod 9 1_[ NULL! aU oo 4 aH Create a linked list for location 7 and | Create a linked list for location 6 SIN) | store the key value 7 in it as its only | and store the key value 24 in it as S| NULL} node, its only node. 6_| NULL| 7_[ NULL] 0_ [NUL o_ NULL] [NULL] 1_[NULL Dr. Mahesh G J_ {NULL 2_ [NULL asso 2_ [NULL] 3—TNULL Dept of CSE, BM 3_[NULL| 4 {NULL 4_ [NULL 5_ [NULL 5_[NULL| 6 [NULL 6 7 =—>71xX) 7 [NUL 8_ [NUL] Module 5 13 Lecture Notes Data Structures and Applications [BCS304] Step3 key= 18 h(k)= 18 nod 9 = 0 Create a linked list for location 0 and store the key value 18 in it as its only node. Step4 — key= 52 h(k) =52mod 9 =7 Insert 52 at the end of the linked list of location, 7. 0 4x) 0 > fe) 1_|NULL 4_[ NULL| 2 (NULL 2_[ NULL! 3_(NULL 3_[NULL| 4_|NULL 4_[ NULL| [NULL | NULL| 6 => qx] 6 Bax 7 => 71x) 7 ti 7] + > B21X] 8_|NULL _| NULL| Step 5: Key = 36 Step 6: key= 54 h(k)= 36 mod 9 = 0 Insert 36 at the end of the linked list of location 0. h(k) = 54 mod 9 = 0 Insert $4 at the end of the linked list of location 0. h(k)= 11 mod 9 = 2 Create a linked list for location 2 and store the key value 11 in it as its only node, oT >i s>sls NULL =u [NULL NULL NULL =->(2a]x) So INULL 00|~Jo]on| a }o>]no| | 0 4 [x] 0 48) {36 }>{54] x) 1 [NULL 4_ {NULL 2_|NULL 2_ [NULL 3_ NULL 3__ [NULL 4_ NULL 4_ [NULL 5_NULL [NULL 6 —|>-Balx 6 > 2a]x 7 +7 S21 Xx} 7 7 52] x] [NULL (NULL Step7: key- 1 Step 8: key= 23 h(k) = 23 mod 9=5 Create a linked list for location 5 and store the key value 23 in it as its only node. 0 => lS->-eS>- x) 4 |NULL 2 sk 3 [NULL 4 |NULL 5 E 13] X 6 24] x 7 7 [52] x. 8 [NULL Pros and Cons ¥ The main advantage of using a chained hash table is that it remains effective even when the number of key values to be stored is much higher than the number of Module 5 14 Lecture Notes Data Structures and Applications [BCS304] locations in the hash table. However, with the increase in the number of keys to be stored, the performance of a chained hash table does degrade gradually Y The other advantage of using chaining for collision resolution is that its performance, unlike quadratic probing, does not degrade when the table is more than half full. This technique is absolutely free from clustering problems and thus provides an efficient mechanism to handle collisions. Y Chained hash tables inherit the disadvantages of linked lists, 1. To store a key value, the space overhead of the next pointer in each entry can be significant 2. Traversing a linked list has poor cache performance, making the processor cache ineffective Pros and Cons of Hashing Y No extra space is required to store the index as in the case of other data structures. ¥- Hash table provides fast data access and has an added advantage of rapid updates, Y Inserting and retrieving data values usually lacks locality and sequential retrieval by key. This makes insertion and retrieval of data values even more random Y Choosing an effective hash function is more of an art than a science. It is not uncommon to create a poor hash function Applications of Hashing Hash tables are widely used in situations where enormous amounts of data have to be accessed to quickly search and retrieve information. Example: 1) Hashing is used for database indexing, 2) Hashing technique is used to implement compiler symbol tables in C++. 3) Hashing is also widely used for Internet search engines Dr. Mahesh G Real World Applications of Hashing ee et oF C 1) CD Databases Y Itis desirable to have a world-wide CD database so that when users put their disk in the CD player, they get a full table of contents on their own computer’s screen Y These tables are not stored on the disks themselves, rather this information is downloaded from the database. Y Basically, a big number is created from the track lengths, also known as a ‘signature’ This signature is used to identify a particular CD. The signature is a value obtained by hashing 2) Drivers Licenses / Insurance Cards Y The driver's license numbers or insurance card numbers are created using hashing, from data items that never change: date of birth, name, etc. 3) Sparse Matrix ¥ A sparse matrix is a two-dimensional array in which most of the entries contain a 0 ¥- Using a 2D array to store this would waste a lot of memory. Y The non zero elements of the sparse matrix can be stored in a 1D array using hashing, Module 5 15 Lecture Notes Data Structures and Applications [BCS304] n n |» hix} 0 Table 1 in = t 2 i 2 Dr. Mahesh G kl Profesor — Dat of CE BNITTR ML . . ¥ From the coordinates for every non zero element (ij), we can determine the index by using a hash function k = H(ij), for some function H. ile Signatures ¥ File signatures provide a compact means of identifying files ¥ We use a function, h{x], the file signature, which is a property of the file Y Although we can store files by name, signatures provide a compact identity to files ¥ Since a signature depends on the contents of a file, if any change is made to the file, then the signature will change. In this way, the signature of a file can be used as a quick verification to see if anyone has altered the file, or if it has lost a bit during transmission 5) Game Boards ¥ In the game board for tic-tac-toe or chess, a position in a game may be stored using a hash function. 6) Graphics ¥ In graphics, a central problem is the storage of objects in a scene or view. For this, we organize our data by hashing. Hashing can be used to make a grid of appropriate size, an ordinary vertical-horizontal grid Y A grid is nothing but a 2D array, and there is a one-to-one correspondence when we move from a 2D array toa ID array VY We store the grid as a ID array as we did in the case of sparse mat Module 5 16 Lecture Notes Data Structures and Applications [BCS304] Hashing example program for collision resolution and searching using linear probing #include #define MAXADDR 100 struct employee { int empid; _// 4-digit key to determine employee records uniquely int age; char name[20]; yht[MAXADDR], int hash(int key) _// Hash function to convert 4-digit key to 2-digi { index (hash address) int index; index ey % MAXADDR; return (index ); 3 a main() Dr. Mahesh G Profesor, inti, choice, count, key, age, index; |} ep orest wsir et char name[20]; count = 0; /Mnitialize all the empid in hash table ht to -1 for( i=0; ic MAXADDR; i++) hi{[Link] v for(;;) printf("1. Insert Record 2. Search Record [Link]\n"), printi("Enter your choice\n"), scanf("%d", &choice); switeh(choice) { case 1: if(count = = MAXADDR) t printf("No Space Available\n"); } else { Module 5 7 Lecture Notes Module 5 Data Structures and Applications [BCS304] printf("Enter the 4-digit unique key for employee\n"); scanf("%d", &key); printf("Enter the Employee name\n"); gets(name); printf” scanf(" inter the age\n"); id", Kage), index = hash(key), if{ ht{index].empid = = -1) / Found free location (No Collision) { ht{index].empid = key; strepy(ht[index].name, name), ht[index].age = age, count = count + 1; break; else // Collision Resolution (Linear Probing) for( i=1; i MAXADDR; i++ ) Dr. Mahesh G Professor, Dept of CSE, BMSIT & MI } break; { index = ( hash(key) + i) % MAXADDR; if( hifindex].empid = = -1) // Found free location t htfindex].empid = key; strepy(htfindex].name, name); htfindex].age = age; count = count + 1; break; } 3 case 2: printf("Enter the 4-digit unique key of employee to search\n"), scant("%d", &key); index = hash(key); if{ ht{index].empid ~~ key) // Found Successfully { printf{"Successful Search\n"); printf("Name = %s\n", ht[index].name), printf("Age = %d\n", hifindex].age); 18 Lecture Notes Data Structures and Applications [BCS304] break; } else if{ ht{index].empid = =-1 ) // Found Vacant Position { printf("Unsuccessful Search\n"), printi("Key not found\n"), break; } else // Search using Linear Probing { for( i=1; i MAXADDR; i++) { index = ( hash(key) + i) % MAXADDR; if{ ht{index].empid = = key) // Found Successfully { printi{" Successful Search\n"), printi("Name = %s\n", hifindex] name), printi("Age = %d\n", hifindex].age); Dr. Mahesh G break: Dept. of C T&M. } . else if( ht{index].empid 1) // Found Vacant Position { printi(" Unsuccessful Search\n"), printf("Key not found\n"); break; } } 3 printi(" Unsuccessful Search\n"), printi("Key not found\n"), break, default: Exit (0); Module 5 19

Vous aimerez peut-être aussi