Python Hash Table / ஹாஷ் அட்டவணை
A Hash Table is a data structure designed to be fast to work with.
ஹாஷ் அட்டவணை என்பது வேகமாக வேலை செய்யும் வகையில் வடிவமைக்கப்பட்ட ஒரு தரவு அமைப்பு.
The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.
சில நேரங்களில் வரிசைகள் அல்லது இணைக்கப்பட்ட பட்டியல்களுக்குப் பதிலாக ஹாஷ் அட்டவணை விரும்பப்படுவதற்கான காரணம், அதிக அளவிலான தரவுகளுக்குக் கூட தரவைத் தேடுவது, சேர்ப்பது மற்றும் நீக்குவது மிக விரைவாகச் செய்ய முடியும்.
In a Linked List, finding a person “Dosai” takes time because we would have to go from one node to the next, checking each node, until the node with “Dosai” is found.
இணைக்கப்பட்ட பட்டியலில், “தோசை” என்ற நபரைக் கண்டுபிடிப்பதற்கு நேரம் எடுக்கும், ஏனெனில் நாம் ஒரு முனையிலிருந்து அடுத்த முனைக்குச் சென்று, “தோசை” உள்ள முனை காணப்படும் வரை ஒவ்வொரு முனையையும் சரிபார்க்க வேண்டும்.
And finding “Dosai” in an list/array could be fast if we knew the index, but when we only know the name “Dosai”, we need to compare each element and that takes time.
மேலும் ஒரு பட்டியல்/வரிசையில் “தோசை”யைக் கண்டுபிடிப்பது நமக்கு குறியீட்டை அறிந்திருந்தால் வேகமாக இருக்கும், ஆனால் “தோசை” என்ற பெயரை மட்டுமே அறிந்திருக்கும் போது, ஒவ்வொரு உறுப்பையும் ஒப்பிட வேண்டும், அதற்கு நேரம் எடுக்கும்.
With a Hash Table however, finding “Dosai” is done really fast because there is a way to go directly to where “Dosai” is stored, using something called a hash function.
இருப்பினும், ஒரு ஹாஷ் அட்டவணை, “தோசை”யைக் கண்டுபிடிப்பது மிக வேகமாக செய்யப்படுகிறது, ஏனெனில் ஹாஷ் செயல்பாடு எனப்படும் ஒன்றைப் பயன்படுத்தி “தோசை” சேமிக்கப்பட்டுள்ள இடத்திற்கு நேரடியாகச் செல்ல ஒரு வழி உள்ளது.
Hash Table Creation
- Create an empty list (it can also be a dictionary or a set).
- Create a hash function.
- Inserting an element using a hash function.
- Looking up an element using a hash function.
- Handling collisions.
ஹாஷ் அட்டவணை உருவாக்கம்
- ஒரு வெற்றுப் பட்டியலை உருவாக்குதல் (அது ஒரு அகராதியாகவோ அல்லது தொகுப்பாகவோ கூட இருக்கலாம்).
- ஒரு ஹாஷ் சார்பை உருவாக்குதல்.
- ஹாஷ் சார்பைப் பயன்படுத்தி ஒரு உறுப்பைச் சேர்த்தல்.
- ஹாஷ் சார்பைப் பயன்படுத்தி ஒரு உறுப்பைத் தேடுதல்.
- மோதல்களைக் கையாளுதல்.
Create an Empty List /ஒரு வெற்று பட்டியலை உருவாக்கவும்
To keep it simple, let’s create a list with 10 empty elements.
எளிமையாகச் சொல்ல வேண்டுமென்றால், 10 வெற்று கூறுகளைக் கொண்ட பட்டியலை உருவாக்குவோம்.
my_list = [None, None, None, None, None, None, None, None, None, None]
Create a Hash Function / ஒரு ஹாஷ் சார்பு செயல்பாட்டை உருவாக்குதல்
Now comes the special way we interact with Hash Tables.
இப்போது ஹாஷ் அட்டவணைகளுடன் நாம் தொடர்பு கொள்ளும் சிறப்பு வழி வருகிறது.
We want to store a name directly into its right place in the array, and this is where the hash function comes in.
ஒரு பெயரை நேரடியாக வரிசையில் அதன் சரியான இடத்தில் சேமிக்க விரும்புகிறோம், இங்குதான் ஹாஷ் செயல்பாடு வருகிறது.
A hash function can be made in many ways, it is up to the creator of the Hash Table. A common way is to find a way to convert the value into a number that equals one of the Hash Table’s index numbers, in this case a number from 0 to 9.
ஒரு ஹாஷ் செயல்பாட்டை பல வழிகளில் உருவாக்கலாம், அது ஹாஷ் அட்டவணையை உருவாக்கியவரைப் பொறுத்தது. ஒரு பொதுவான வழி, மதிப்பை ஹாஷ் அட்டவணையின் குறியீட்டு எண்களில் ஒன்றிற்கு சமமான எண்ணாக மாற்றுவதற்கான வழியைக் கண்டுபிடிப்பதாகும், இந்த விஷயத்தில் 0 முதல் 9 வரையிலான எண்.
In our example we will use the Unicode number of each character, summarize them and do a modulo 10 operation to get index numbers 0-9.
எங்கள் எடுத்துக்காட்டில், ஒவ்வொரு எழுத்தின் யூனிகோட் எண்ணைப் பயன்படுத்துவோம், அவற்றைச் சுருக்கி, 0-9 குறியீட்டு எண்களைப் பெற மாடுலோ 10 செயல்பாட்டைச் செய்வோம்.
Example / உதாரணம்
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print(“‘Dosai’ has hash code:”, hash_function(‘Dosai’))
Output:
‘Dosai’ has hash code: 6
The character D has Unicode number 68, o has 111,s has 115, a has 97 and i has 105. Adding those together we get 496. Modulo 10 of 496 is 6, so “Dosai” should be stored at index 6.
The number returned by the hash function is called the hash code.
D என்ற எழுத்துக்குறி யூனிகோட் எண் 68, o என்பது 111, s என்பது 115, a என்பது 97 மற்றும் i என்பது 105. இவற்றை ஒன்றாகச் சேர்த்தால் நமக்கு 496 கிடைக்கும். 496 இல் மாடுலோ 10 என்பது 6, எனவே “தோசை” குறியீட்டு 6 இல் சேமிக்கப்பட வேண்டும்.
ஹாஷ் செயல்பாட்டால் வழங்கப்படும் எண் ஹாஷ் குறியீடு என்று அழைக்கப்படுகிறது.
Notes / குறிப்புகள்:
Unicode number: Everything in our computers are stored as numbers, and the Unicode code number is a unique number that exist for every character. For example, the character A has Unicode number 65.
Modulo: A modulo operation divides a number with another number, and gives us the resulting remainder. So for example, 7 % 3 will give us the remainder 1. (Dividing 7 apples between 3 people, means that each person gets 2 apples, with 1 apple to spare.)
In Python and most programming languages, the modolo operator is written as %.
யூனிகோட் எண்: நமது கணினிகளில் உள்ளேஅனைத்தும் எண்களாகவே சேமிக்கப்படுகின்றன, மேலும் யூனிகோட் குறியீட்டு எண் என்பது ஒவ்வொரு எழுத்திற்கும் உள்ள ஒரு தனித்துவமான எண்ணாகும். உதாரணமாக, ‘A’ என்ற எழுத்தின் யூனிகோட் எண் 65 ஆகும்.
மாடுலோ: ஒரு மாடுலோ செயல்பாடு ஒரு எண்ணை மற்றொரு எண்ணால் வகுத்து, அதன் மீதியை நமக்குத் தருகிறது. உதாரணமாக, 7 % 3 என்பது நமக்கு மீதி 1-ஐத் தரும். (7 ஆப்பிள்களை 3 பேருக்குப் பிரித்துக் கொடுத்தால், ஒவ்வொருவருக்கும் 2 ஆப்பிள்கள் கிடைக்கும், மீதி 1 ஆப்பிள் இருக்கும்.)
பைதான் மற்றும் பெரும்பாலான நிரலாக்க மொழிகளில், மாடுலோ செயற்குறி ‘%’ எனக் குறிக்கப்படுகிறது.
Inserting an element
In our hash function, “Dosai” should be stored at index 6.
Lets create a function that add items to our hash table
ஹாஷ் சார்பின்படி, “தோசை” என்ற சொல் 6வது குறியீட்டில் சேமிக்கப்பட வேண்டும்.
இப்போது, நமது ஹாஷ் அட்டவணையில் பொருட்களைச் சேர்க்கும் ஒரு செயற்கூறை உருவாக்குவோம்
my_list = [None, None, None, None, None, None, None, None, None, None]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def add(name):
index = hash_function(name)
my_list[index] = name
add(‘Dosai’)
print(my_list)
Output:
[None, None, None, None, None, None, ‘Dosai’, None, None, None]
We can use the same functions to store “Pongal”, “Sambar”, “Vadai”, and “Chuttney” as well.
my_list = [None, None, None, None, None, None, None, None, None, None]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def add(name):
index = hash_function(name)
my_list[index] = name
add(‘Dosai’)
add(‘Pongal’)
add(‘Vadai’)
add(‘Sambar’)
add(‘Chuttney’)
print(my_list)
Output:
[None, None, ‘Chuttney’, None, None, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]
Looking up an element / தரவைத் தேடுகிறது
To find “Dosai” in the Hash Table, we give the name “Dosai” to our hash function. The hash function returns 6, meaning that “Dosai” is stored at index 6.
ஹாஷ் அட்டவணையில் “தோசை”யைக் கண்டறிய, நாம் “தோசை” என்ற பெயரை நமது ஹாஷ் சார்புக்கு வழங்குகிறோம். அந்த ஹாஷ் சார்பு 6 என்ற எண்ணைத் தருகிறது, அதாவது “தோசை” என்பது 6வது குறியீட்டில் சேமிக்கப்பட்டுள்ளது.
my_list = [None, None, None, None, None, None, None, None, None, None]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def add(name):
index = hash_function(name)
my_list[index] = name
def contains(name):
index = hash_function(name)
return my_list[index] == name
add(‘Dosai’)
add(‘Idlli’)
add(‘Vadai’)
add(‘Sambar’)
add(‘Pongal’)
add(‘Chuttney’)
print(“‘Dosai’ is in the Hash Table:”, contains(‘Dosai’))
Output:
‘Dosai’ is in the Hash Table: True
Handling Collisions / மோதல்களைக் கையாளுதல்
We give “Coffee” to our hash function, which returns 4, meaning “Coffee” should be stored at index 4.
Trying to store “Coffee” in index 4, creates what is called a collision, because “Idlli” is already stored at index 4.
To fix the collision, we can make room for more elements in the same bucket. Solving the collision problem in this way is called chaining, and means giving room for more elements in the same bucket.
நாம் நமது ஹாஷ் ஃபங்ஷனுக்கு “காபி” என்ற உள்ளீட்டைக் கொடுக்கிறோம், அது 4 என்ற எண்ணைத் தருகிறது. அதாவது, “காபி” 4வது இன்டெக்ஸில் சேமிக்கப்பட வேண்டும்.
4வது இன்டெக்ஸில் “காபி”யைச் சேமிக்க முயற்சிக்கும்போது, ஒரு மோதல் (collision) ஏற்படுகிறது, ஏனெனில் அந்த இடத்தில் ஏற்கனவே “இட்லி” சேமிக்கப்பட்டுள்ளது.
இந்த மோதலைச் சரிசெய்ய, அதே பக்கெட்டில் அதிக உறுப்புகளுக்கு இடம் கொடுக்கலாம். இந்த வழியில் மோதல் சிக்கலைத் தீர்ப்பது ‘செயினிங்’ (chaining) என்று அழைக்கப்படுகிறது, மேலும் இது ஒரே பக்கெட்டில் அதிக உறுப்புகளுக்கு இடம் கொடுப்பதைக் குறிக்கிறது.
my_list = [None, None, None, None, None, None, None, None, None, None]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def add(name):
index = hash_function(name)
my_list[index] = name
add(‘Dosai’)
add(‘Idlli’)
add(‘Vadai’)
add(‘Sambar’)
add(‘Pongal’)
add(‘Chuttney’)
print(my_list)
add(‘Coffee’)
print(my_list)
Output:
[None, None, ‘Chuttney’, None, ‘Idlli’, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]
[None, None, ‘Chuttney’, None, ‘Coffee’, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]
Start by creating a new list with the same size as the original list, but with empty buckets
முதலில், அசல் பட்டியின் அதே அளவுள்ள, ஆனால் காலி பக்கெட்டுகளைக் கொண்ட ஒரு புதிய பட்டியலை உருவாக்குவதன் மூலம் தொடங்கவும்.
my_list = [
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
Example /உதாரணம்
After implementing each bucket as a list, “Coffee” can also be stored at index 4 along with Idlli, and our Hash Set now looks like this:
ஒவ்வொரு பக்கெட்டையும் ஒரு பட்டியலாகச் செயல்படுத்திய பிறகு, இட்லியுடன் சேர்த்து “காபி”யையும் குறியீடு 4-இல் சேமிக்க முடியும், மேலும் இப்போது நமது ஹாஷ் செட் இப்படித் தெரிகிறது:
my_list = [[], [], [], [], [], [], [], [], [], []]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def add(name):
index = hash_function(name)
my_list[index].append(name)
add(‘Dosai’)
add(‘Idlli’)
add(‘Vadai’)
add(‘Sambar’)
add(‘Pongal’)
add(‘Chuttney’)
add(‘Coffee’)
print(my_list)
Output:
[[], [], [‘Chuttney’], [], [‘Idlli’, ‘Coffee’], [‘Vadai’], [‘Dosai’], [], [‘Sambar’], [‘Pongal’]]
Uses of Hash Tables / ஹாஷ் அட்டவணைகளின் பயன்கள்
Hash Tables are great for:
Checking if something is in a collection (like finding a book in a library).
Storing unique items and quickly finding them (like storing phone numbers).
Connecting values to keys (like linking names to phone numbers).
The most important reason why Hash Tables are great for these things is that Hash Tables are very fast compared Arrays and Linked Lists, especially for large sets. Arrays and Linked Lists have time complexity O(n) for search and delete, while Hash Tables have just O(1) on average.
ஹாஷ் அட்டவணைகள் இதற்கு சிறந்தவை:
ஒரு தொகுப்பில் ஏதாவது இருக்கிறதா என்று சோதித்தல் (நூலகத்தில் ஒரு புத்தகத்தைக் கண்டுபிடிப்பது போல).
தனித்துவமான பொருட்களைச் சேமித்து அவற்றை விரைவாகக் கண்டறிதல் (தொலைபேசி எண்களைச் சேமிப்பது போல).
விசைகளுடன் மதிப்புகளை இணைத்தல் (தொலைபேசி எண்களுடன் பெயர்களை இணைப்பது போல).
இந்த விஷயங்களுக்கு ஹாஷ் அட்டவணைகள் சிறந்ததாக இருப்பதற்கான மிக முக்கியமான காரணம், ஹாஷ் அட்டவணைகள் வரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்களுடன் மிக வேகமாக ஒப்பிடப்படுகின்றன, குறிப்பாக பெரிய தொகுப்புகளுக்கு. வரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்கள் தேட மற்றும் நீக்குவதற்கு நேர சிக்கலான O(n) ஐக் கொண்டுள்ளன, அதே நேரத்தில் ஹாஷ் அட்டவணைகள் சராசரியாக O(1) ஐ மட்டுமே கொண்டுள்ளன.
Summary / சுருக்கம்
Hash Table elements are stored in storage containers called buckets.
A hash function takes the key of an element to generate a hash code.
The hash code says what bucket the element belongs to, so now we can go directly to that Hash Table element: to modify it, or to delete it, or just to check if it exists.
A collision happens when two Hash Table elements have the same hash code, because that means they belong to the same bucket.
Collision can be solved by Chaining by using lists to allow more than one element in the same bucket.
ஹாஷ் அட்டவணையின் கூறுகள் பக்கெட்டுகள் எனப்படும் சேமிப்புக் கொள்கலன்களில் சேமிக்கப்படுகின்றன.
ஒரு ஹாஷ் சார்பு, ஒரு கூறின் சாவியைப் பயன்படுத்தி ஒரு ஹாஷ் குறியீட்டை உருவாக்குகிறது.
அந்த ஹாஷ் குறியீடு, அந்தக் கூறு எந்தப் பக்கெட்டில் உள்ளது என்பதைக் கூறுகிறது. எனவே, நாம் நேரடியாக அந்த ஹாஷ் அட்டவணைக் கூறிற்குச் சென்று, அதை மாற்றியமைக்கலாம், அல்லது நீக்கலாம், அல்லது அது உள்ளதா என்பதைச் சரிபார்க்கலாம்.
இரண்டு ஹாஷ் அட்டவணைக் கூறுகளுக்கு ஒரே ஹாஷ் குறியீடு இருக்கும்போது ஒரு மோதல் ஏற்படுகிறது, ஏனெனில் அது இரண்டும் ஒரே பக்கெட்டில் உள்ளன என்பதைக் குறிக்கிறது.
ஒரே பக்கெட்டில் ஒன்றுக்கு மேற்பட்ட கூறுகளை அனுமதிக்க, பட்டியல்களைப் பயன்படுத்துவதன் மூலம் சங்கிலியிடுதல் முறையில் மோதலைத் தீர்க்கலாம்.