Hashing and Hashtable, application of hashing, advantages of hashing, disadvantages of hashing

This presentation tells about hashing and hashtable

1. Hashing & hashtable

2. Hashing Hashing  is the process of converting a given key into another value. A  hash  function is used to generate the new value according to a mathematical algorithm. The result of a  hash  function is known as a  hash  value or simply, a  hash .

3. A good hash function uses a one-way hashing algorithm, or in other words, the hash cannot be converted back into the original key

4. Eg : if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

5. Collisions The two keys can generate the same hash. This phenomenon is known as a  collision .

6. Hash Table Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

7. Hash table

8. Applications Hashing provides constant time search, insert and delete operations on average. example problems : distinct elements, counting frequencies of items, finding duplicates Some of these applications are listed below: Message Digest Password Verification Data Structures(Programming Languages) Rabin-Karp Algortithm Linking File name and path together

9. Advantages Main advantage is synchronization. In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer softwares , particularly for associative arrays, database indexing and sets.

10. The main  advantage  of  hash tables  over other  table  is speed. This  advantage  is more apparent when the number of entries is large.

11. Disadvantages Hash collisions are practically unavoidable. when hashing a random subset of a large set of possible keys. Hash tables become quite inefficient when there are many collisions. Hash table does not allow null values

12. . The efficiency of mapping depends of the efficiency of the hash function used.