Lecture Data Structures: Lesson 43 provide students with knowledge about hashing animation; applications of hashing; compilers use hash tables to keep track of declared variables (symbol table); entire dictionary can be hashed and words checked in constant time; . | Lecture Data Structures Dr. Sohail Aslam Recap Collision Strategies in Hashing Linear Probing Quadratic Probing Linked List chaining Hashing Animation Let s see the hashing animation. We will see linear probing quadratic probing and link list chaining in it. This is an example of how do we solve collision. We have an array shown in four different columns. The size of the array is 100 and the index is from 0 to 99. Each element of the array has two locations so we can store 200 elements in it. When we have first collision the program will use the 2nd part of the array location. When there is a 2nd collision the data is stored using the linear probing. At the top right corner we have hash function x and its definition is mod 100 . That is when a number is passed to it it will take mod with 100 and return the result which is used as index of the array. In this example we are using numbers only and not dealing with the characters. We also have a statistical table on the right side. This program will generate 100 random numbers and using the hash function it will store these in the array. The numbers will be stored in the array at different locations. In the bottom left we have hashing algorithms. We have chosen the linear probing. Now the program will try to solve this problem using the linear probing. Press the run button to start it. It is selecting the numbers randomly dividing it by 100 and the remainder is the hash value which is used as array index. Here we have number 506. It is divided by 100 and the remainder is 6. It means that this number will be stored at the sixth array location. Similarly we have a number 206 now its remainder is also 6. As location 6 is already occupied so we will store 206 at the 2nd part of the location 6. Now we have the number 806. Its remainder is also 6. As both the parts of location 6 are occupied. Using the linear probing we will store it in the next array location . 7. If we have another number having the remainder as
