Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:
- In universities, each student is assigned a unique roll number that can be used to retrieve information about them.
- In libraries, each book is assigned a unique number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to etc.
In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hash table. The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is assigned a key (converted key). By using that key you can access the element in O(1) time. Using the key, the algorithm (hash function) computes an index that suggests where an entry can be found or inserted.
Hashing is implemented in two steps:
- An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table.
- The element is stored in the hash table where it can be quickly retrieved using hashed key.hash = hashfunc(key)
index = hash % array_size
•Hashing is a technique used for storing and retrieving keys in a rapid manner.
•In hashing, a string of characters are transformed into a usually shorter length value or key that represents the original string.
•Hashing is used to index and retrieve items in a database because it is faster to find item using shorter hashed key than to find it using the original value.
•Hashing can also be defined as a concept of distributing keys in an array called a hash table using a predetermined function called hash function.
•Hash table is a table (array) where we store the original string. Index of the table is the hashed key while the value is the original string.
•The size of hash table is usually several orders of magnitude lower than the total number of possible string, so several string might have a same hashed-key.
Picture above is a example of hash table.
A hash function is a mathematical function that converts a numerical input value into another compressed numerical value.
•There are many ways to hash a string into a key. The following are some of the important methods for constructing hash functions.
•Mid-square
•Division (most common)
•Folding
•Digit Extraction
•Rotating Hash
Mid Square
algorithm:
- Choose a seed value. This is an important step as for same seed value, the same sequence of random numbers is generated.
- Take the square of the seed value and update seed by a certain number of digits that occur in the square. Note: The larger is the number of digits, larger will be the randomness.
- Return the key.
source:
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/