Last Updated on May 5, 2023 by Prepbytes
A hash function, in its simplest form, converts a significant number or text into a tiny integer that may be used as the index in the hash table. The pair has the form (key, value), where one may use some sort of "function" that converts keys into values to obtain a value for a given key. A hash function is a type of function that may be used to determine the key for a certain object. For instance, if i is the key for an array A and A[i] is the array, then we can look up A[i] to obtain the value.
What is Hashing in Data Structures?
In a data structure, slicing up a large quantity of data into smaller tables is known as hashing. It is a technique for separating one distinct item from a collection of connected ones and is sometimes referred to as the message digest function.
Searching for a certain object on a data map may be made more targeted via hashing. In this case, a hash code creates an index to store values. Because it expedites the process, hashing is used to index and retrieve data from databases; finding an item using a smaller hash key than just its original value is much easier.
The data are kept in an array format using hash tables. Each value in the array has a different index number. Hash tables employ a technique known as the hash technique to generate these unique index numbers for each value contained in an array format.
Some real-life examples of hashing in data structure include –
- In Libraries – There are countless books in a library. A unique number is given to each book by the librarian. The precise location of the books on the bookshelf may be found with the help of this distinguishing number.
- In Schools – For convenience, each student in a class is given a distinct roll number. Later, the school authority uses the special roll number to locate pertinent data about the specific student.
How Does Hashing Work in Data Structure?
Data structures employ the hashing technique to store and retrieve information from databases. Many data structures, including hash tables and hash trees, depend on it. Data is mapped to a distinct value, known as a hash code, by hashing. The data is subsequently placed in an array using the hash code as an index. The hash code is simply recalculated and used to index within the array to obtain the contents.
Additionally, it enables the storage of duplicate values without leading to collisions in the same structure. Hashing algorithms are commonly used to create hashes; they accept input and output a hash code. The fundamental idea behind all hashing algorithms is to convert data into a value that can be used as an index in an array. SHA-1, MD5 and Murmur Hash are a few of the well-known hashing methods.
In essence, hashing involves converting data into a hash code and storing it in a hash table. The hash code is used to seek the data in the hash table when it is necessary to retrieve it. Hash tables are frequently employed in caches and databases for rapid data search. The ability to store data of any form, including objects, texts, and numbers, is a major benefit of hashing. Additionally, hashing is effective when carried out correctly and is comparatively easy to implement. Hashing is hence commonly utilized in computer programming.
What is the Key in Hashing?
The raw data that must be hashed in a hash table is called the Hashing Key. The function that converts the hash key into the hash value is carried out by the hashing algorithm.
Hash Key = Key Value % Number of Slots in the Table
- Public key – Public keys, often known as "asymmetric" keys, are solely used for data encryption. The public key is an open key makes the method somewhat slower. Public keys are frequently used for online session security, bitcoin transfers, and cryptographic operations.
- Private key – Both encryption and decryption need the private key. Each party that sends or receives encrypted sensitive information shares a key. The private key is sometimes referred to as "symmetric" because both parties share it.
- SSH public key – SSH uses both a public and a private key. SSH is a set of keys that can be used to authenticate and decrypt a communication sent from a distance. Both the distant servers and the stakeholders have access to the public key.
What is Hash Function in Data Structure?
In hash functions, a key is converted into a hash key using a predetermined technique. A key can be used to create length-restricted data known as hash values. The original character sequence is still represented in the hash value even if it is often smaller than the original.
The receiver gets both the hash value and the digital signature after the transmission of the digital signature. The hash value produced by the receiver and the one obtained along with the message using the same hash technique is compared. If messages’ hash values perfectly match, they can be forwarded without any issues.
Some of the characteristics of the hash function are –
- There is no restriction on how long a message may be.
- The length of message digests is fixed when they are created.
- Hashes cannot be used to construct message digests since they are irreversible.
- Due to the fact that two distinct messages cannot produce the same hash value, the hash is collision-free.
Types of Hash Functions in Data Structure
Following hash functions are –
-
Division Method
The simplest and quickest way to create a hash value is through division. The value of k is split by M and used as obtained in this hash function.Formula
h(K) = k mod M (where k = key value and M = the size of the hash table) -
Mid Square Method
The following steps are required to calculate this hash method:- k*k, or square the value of k S.
- Subtract the middle r digits to get the hash value.
Formula
h(K) = h(k x k) (where k = key value ) -
Folding Method
This process consists of two phases.- The key-value k should be split into a certain number of components, such as k1, k2, k3,…, kn, each of which should have the same amount of digits, with the exception of the last component, which may have fewer digits than the other components.
- Add each element individually. The hash value is calculated without taking into account the final carry, if any.
Formula
k = k1, k2, k3, k4, ….., kn s = k1+ k2 + k3 + k4 +….+ kn h(K)= s (Where, s = addition of the parts of key k) -
Multiplication Method
The steps are as follows:- Determine a constant value. A, where (0, A, 1)
- Add A to the key value and multiply.
- Consider kA’s fractional portion.
- Multiply the outcome of the preceding step by M, the hash table’s size.
Formula
h(K) = floor (M (kA mod 1)) (Where, M = size of the hash table, k = key value and A = constant value)
Conclusion
Hashing offers a more flexible and safe way to retrieve data than any other data structure can. Hashing allows you to search through lists and arrays more rapidly, so you may use it to quickly locate the index of the desired item with a minimal number of operations. Since messages cannot be changed while being transmitted, hashing is essential for information security.
Since using a small hash key to find anything is faster than using the original value, hashing is primarily used for database recovery. Without opening or comparing them, it is also possible to discern the information if they are indistinguishable.
Frequently Asked Questions related to Hash Function in Data Structure
Q1. What is the hash function’s size?
Ans. Depending on the algorithm chosen, the hashing functions return a 128-bit, 160-bit, 256-bit, or 512-bit hash of the input data. A representation of the string value to be hashed in an expression.
Q2. How many different types of hashing exist?
Ans. The Secure Hash Algorithm-1 (SHA-1), and is two of the seven hash algorithms listed in FIPS 180-4. SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, and SHA-512/256 are among the hashing algorithms of the SHA-2 family.
Q3. Does a key exist for hash functions?
Ans. Hash functions work in a one-way fashion and do not require a key for basic operation. Due to the one-way process, it is not feasible to calculate the input from a certain output. Hash function applications start with Digital signature creation and validation
Q4. Is hashing symmetric or asymmetric?
Ans. Hashes like SHA-x are symmetric and unkeyed. Both symmetric (AES) and asymmetric (RSA) encryption are available. And there is symmetric authentication(MAC) and asymmetric authentication(RSA signatures). Many authentication schemes use hashes, but they aren’t hashes
Q5. Is a hash private key?
Ans. A private key is used to generate a hash value of the contents of the file being signed and transferred when using a digital signature. The recipient decrypts the signature using the signer’s public key and compares the decrypted hash value to the hash of the original file.