Python is a broadly - used high-level, general-purpose programming language that was designed with the core focus on code readability, and the associated syntax that enables programmers to present their concepts using lesser code. New lines of code are used in Python to finish a command, whereas other programming languages often use parentheses or semicolons. Python depends on using whitespace and indentation to describe factors such as the scope of functions, loops, and classes. Other programming languages mostly use curly brackets for the same. Next, let us understand what a hash table is in python.
What Is a Hash Table?
A Hash Table in Python is nothing but a data structure where data is stored in an associative manner. In hash tables, data is stored in an array format, with every data value having an exclusive or unique index value. This type of storage offers quick access to data if the index of the data required is available.
Thus, the data structure provides easy and quick search and insertion irrespective of the data size. A Hash Table in Python utilizes an array as a medium of storage and uses the hash method to create an index where an element is to be searched from or needs to be inserted.
In other words, a Hash Table in Python is a data structure which stores data by using a pair of values and keys. Each data value is allocated an exclusive key that is created by using the hash functions. Then, to access its associated value the name of the key is used, thus making searching of data values a very fast and efficient process.
Hash Functions
With the huge increase in the quantity of data that is being processed by global and local data networks, computer scientists are looking out for ways to make the process of data access faster and make sure that data can be exchanged in a secure manner. Hash functions are a solution that programmers use along with other security technologies.
Hash means to cut, scramble, or chop something. This definition itself offers a clue as to what hash functions do to the data. Yes, hash functions scramble or chop data and then change it into a numerical value. Also, it does not matter how long the input is, the output is always the same length. Another term used for hash functions is message digest functions or hashing algorithms. Following are some hash functions examples:
- To prevent sensitive data, such as web analytics, passwords, and payment details.
- To encrypt information exchange between browsers and web servers, and create session IDs for data caching and internet applications.
- To find identical data through lookup functions.
- Adding a digital signature to an email.
Creating a Hash Table
Let us now come to how to create a Hash Table in Python.
To create a hash table, a chunk of memory needs to be blocked, in the same manner as while creating an array. Since what we need to do is create an index that is based on a key by using the hash function, the index generated needs to fit in the chunk of memory or buckets.
We require two checks while placing new data in the has table, which are:
- the hashed value of the key.
- how the value compares to other objects.
These checks are required while creating a Hash Table in Python because, when data is inserted, the key is hashed and masked so that it is converted to an efficient array or index. The mask ensures that the hash value that can take up the value of any integer fits within the number of buckets that are allocated.
So, if there are 8 blocks of memory assigned, then each block is considered as 1 byte and the total hash value is 28975, then the bucket at index is considered as 28975 and 0b111 = 7. However, if the hash table is increased to an extent that it requires around 512 blocks of memory, then the mask turns into 0b111111111 (the bucket is considered at an index 28975 and 0b11111111). The mask helps to constraint the index so that it can fit into the bucket.
|
Note: We recommend that users learn how to convert binary to decimal to understand how the index is generated by a mask and hash value. |
Now, once the index is found, you need to check if the index is empty
- If the index is empty, then move the value and key into the block.
- Case 1, if the index is not empty: The hash utilizes the inbuilt __cmp__ function to see if the value assigned at the index and value that is being inserted is the same when returned.
- Case 2, if the index is not empty: If the values that are present are different from the ones that are being inserted, then the hash table is under collision.
With this, you now know how to create a hash table in Python.
Writing Hash Function
Let us now look at how to create hash functions.
Division Method
If the size of the hash table is l and the indices to be found are those of key m, then the hash function is calculated as follows:
h(m) = m mod l
If hash size of the hash table is 10 and m=111 then h(m) = 111 mod 10 = 1, then the table size should never be in the powers of 2, as the binary form of the powers of 2, which is 2,4, 8 leads to 10, 100… and so on.
Multiplication Method
To find keys’ indices, the following hash function is followed:
h(m) = {l(A mod 1)}
where, 0<A<1 and
(mA mod 1) gives the fractional part mA, and {} calculates the floor value.
Universal Hashing
The hash function is selected in a haphazard manner, independent of keys.
Hash Collision Sample
class City(str):
def __hash__(self):
return ord(self[0])
# We generate a dictionary where the arbitrary values are allocated to cities
data = {
City("Venice"): 'Italy',
City("Manchester"): 'UK',
City("London"): 'UK',
City("Madrid"): 'Spain',
}
"""
hash("Madrid") = ord("M") & 0b111
= 66 & 0b111
= 0b1000010 & 0b111
= 0b010 = 2
hash("Venice") = ord("R") & 0b111
= 82 & 0b111
= 0b1010010 & 0b111
= 0b010 = 2
"""
Hash Table Implementation With Python Example
Now, let us view a very easy example that calculates a key’s hash value:
def hash_key( key, l):
return key % l
l = 7
print(f'The hash value for 3 is {hash_key(3,l)}')
print(f'The hash value for 2 is {hash_key(2,l)}')
print(f'The hash value for 9 is {hash_key(9,l)}')
print(f'The hash value for 11 is {hash_key(11,l)}')
print(f'The hash value for 7 is {hash_key(7,l)}')
Explanation:
- Describes a function which is hash_key that receives the parameters key and l.
- A simple modulus operation is used to calculate the hash value.
- Describes a variable l which is set to the value of 7. Thus, this is the hash table size.
- Prints the hash value of 3 after calculating it.
- Prints the hash value of 2 after calculating it.
- Prints the hash value of 9 after calculating it.
- Prints the hash value of 11 after calculating it.
- Prints the hash value of 7 after calculating it.
Following is the result after the code is executed:
3 is the hash value for 3
2 is the hash value for 2
2 is the hash value for 9
4 is the hash value for 11
0 is the hash value for 7
Real World Applications
Following are some of the real-world applications of a Hash Table in Python:
- Message Digest: A cryptographic hash function comprising a thread of digits generated by using a one-way hashing formula. Message digests are set up to prevent the details of a piece of media or data and to identify changes and modifications to any part of a message. For example, while storing a file in any open cloud space, one would want to protect the integrity of the file. This problem can be solved using the Message Digest.
- File System: Hashing is used for connecting the file name to the path of the file. Once a user interacts with the file system, the file name is visible. Also, the path to the file may be visible. However, to store the communication between the path and the file name and the physical position of the file on the disk, the system utilizes a map, and that map is usually executed as a hash table.
- Password Verification: When a user tries to enter a web service by using the login credentials, a hash value of the password is calculated on the client-side and sent to the server, which then checks if that hash value matches with the hash value of the stored password. Only if both the hash values match, does a user get authenticated.
- Pattern Matching: Hashing is also used to locate the patterns hidden in strings. One famous algorithm that utilizes hashing for locating a pattern in a string is the Rabin-Karp Algorithm. This pattern matching is also utilized to recognize plagiarism.
- Programming Language: In programming languages, data structures or built-in data types are available in the standard library which are based on hash tables.
Looking forward to becoming a Data Scientist? Check out the PG in Data Science and get certified today.
Conclusion
The key advantage that hash tables have over other data structures is efficiency and speediness. The time it takes to access an element is O(1), therefore lookups are executed quite fast. A Hash Table in Python is also specifically effective when most of the number of entries can be projected in advance. On the other hand, you can master the A-Z of python and scale up your career by enrolling in our Data Science Master’s Program. Start now!
