هش تیبل ها (Hash Tables)
«هش تیبل (Hash Table)» یک ساختار داده سریع است. با «تابع هش (Hash Function)» کلید را به «کد هش» تبدیل می کنیم و مستقیم به باکت می رسیم.
ایده اصلی هش تیبل
در آرایه یا لیست پیوندی، جستجو زمان بر است. اما در هش تیبل، با کد هش به خانه درست می رویم. بنابراین افزودن، جستجو، و حذف معمولاً خیلی سریع است.
گام 1: ساخت تابع هش
تابع هش رشته را به عدد تبدیل می کند. سپس با «مدولو (Modulo)» آن را به اندیس تبدیل می کنیم.
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print("'Bob' has hash code:", hash_function('Bob'))
گام 2: درج ساده در هش تیبل
اندیس را از تابع هش می گیریم و مقدار را همان جا می گذاریم.
my_list = [None, None, None, None, None, None, None, None, None, None]
def add(name):
index = hash_function(name)
my_list[index] = name
add('Bob')
print(my_list)
اکنون چند نام دیگر هم اضافه می کنیم تا آرایه پرتر شود.
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
print(my_list)
گام 3: جستجو با نام
برای «Pete» اندیس را حساب می کنیم و همان خانه را چک می کنیم.
def contains(name):
index = hash_function(name)
return my_list[index] == name
print("'Pete' is in the Hash Table:", contains('Pete'))
گام 4: برخورد (Collision) و زنجیره سازی
اگر دو نام به یک باکت برسند، «برخورد» رخ می دهد. با «زنجیره سازی (Chaining)» هر باکت را لیست می کنیم.
my_list = [
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
def add(name):
index = hash_function(name)
my_list[index].append(name)
add('Bob')
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
add('Stuart')
print(my_list)
گام های عملی
- تابع هش را بنویس.
- درج و جستجو را بساز.
- برخوردها را با زنجیره سازی مدیریت کن.
برای مرور «لیست های پیوندی» سر بزن به لیست های پیوندی. همچنین صفحه هش تیبل ها را نشانه گذاری کن.
جمع بندی سریع
- هش تیبل معمولاً خیلی سریع است.
- تابع هش، کلید را به باکت می برد.
- برخورد با زنجیره سازی حل می شود.
- برای داده بزرگ، بهینه تر عمل می کند.