The Basics of Hashing
Hashing was created to address the problem of quickly locating or storing an object in a collection.
For example, if we have a list of 10,000 English words and want to see if a specific word is on the list, it will be inefficient to compare the word to each of the 10,000 things before we find a match. Even if the list of terms is lexicographically sorted, as in a dictionary, finding the word you're searching for will take some time.
Hashing is a technique for increasing efficiency by effectively narrowing the search at the start. Students also seek for the Hashing in Data Structure.
Hashing is a major improvement over DAT in terms of reducing space complexity.
To generate a hash value, a hashing algorithm is applied to a data item known as the hashing key. Hashing algorithms convert a large number of values (such as all possible strings or files) into a smaller number of values (such as a 128-bit number).
There are two main uses for hashing. Hashed values can be used to speed up data retrieval and to ensure that data is valid.
When we need to find one record among many in a file, we must search the file for the required record, which takes time that varies depending on the number of records. We can use the hash value as the “address” of the record and move directly to it if we can generate a hash for the record's key; this takes the same amount of time regardless of the number of records in the file.
A hash can be used to check the validity of data. This can be used to ensure that a file has been correctly transferred and that it has not been tampered with between the time I upload it and the time you download it. You can generate a hash value from the file you received and compare the hash values if I post both the file and the hash value I generated from it. If the hashing algorithm is a good cryptographic hash, it's highly unlikely that the file could have been slightly modified by accident or malice and still yield the same hash value.
To generate a list of hashing values To make a hashing table, we use a hashing algorithm.
Collisions
A collision occurs when two hash keys produce the same hash value. This creates a problem because we can't tell if data is in our hashing table because another piece of data might have the same hashing value.
Closed Hashing (Open Addressing)
When two hash keys produce the same hash value, the colliding keys are placed in the next available hash value.
Open Hashing (Closed Addressing)
When two hash keys produce the same hash value, we use a linked list to connect all the values that fit the hashing value together.
What are some of the advantages of hashing?
1. Comparing two files for equality is one of the most common uses of hashing. The determined hash values of these files would allow the owner to know whether they are different without having to open two document files and compare them word-for-word.
2. Hashing is often used in file recovery programs like SyncBack to check the integrity of a file after it has been moved from one location to another. A user should compare the hash values of both files to ensure that the transferred file is not corrupted. If they're the same, the transferred file is a duplicate of the original.
3. An encrypted file can be programmed to never alter the file size or the last update date and time in certain cases (for example, virtual drive container files). In such instances, it would be difficult to say whether two identical files are different or not at first sight, but the hash values would easily distinguish them if they were.
Mark Henry
