آموزش

راهنمای هش‌مپ‌ها در پایتون

کشف کن که هش‌مپ‌ها چی‌ان و چطور در پایتون از طریق دیکشنری‌ها پیاده‌سازی می‌شن.

تاریخ انتشار:

28 شهریور 1405

پایتون

11 دقیقه

مهندسی داده

کاربرهای فینکا در چه شرکت‌هایی مشغول به کار هستند؟

وقتی متخصصان داده امروز درباره ذخیره‌سازی داده صحبت می‌کنن، بیشتر اوقات منظورشون مکان ذخیره داده‌ست، چه فایل‌های محلی، چه دیتابیس‌های SQL یا NoSQL، یا فضای ابری. اما یک جنبه مهم دیگه در ذخیره‌سازی داده، نحوه ذخیره‌سازی اون‌هاست.

نحوه ذخیره‌سازی داده اغلب در سطح پایین‌تری اتفاق می‌افته، یعنی درست در هسته زبان‌های برنامه‌نویسی. این موضوع بیشتر به طراحی ابزارهایی که استفاده می‌کنیم مربوط می‌شه تا نحوه استفاده از اون‌ها. با این حال، دونستن اینکه داده چطور ذخیره می‌شه برای درک مکانیزم‌های پایه‌ای که کار رو ممکن می‌کنن، حیاتیه. علاوه بر این، این دانش می‌تونه به ما کمک کنه تا تصمیمات بهتری برای بهبود عملکرد پردازشی بگیریم.

اگر واقعا به هش‌مپ‌ها، لیست‌های پیوندی، پشته‌ها، صف‌ها و گراف‌ها علاقه داری، در فینکا ثبت‌نام کن تا بتونی دوره ساختارهای داده و الگوریتم‌ها در پایتون ما رو بگذرونی.

هش‌مپ چیه؟

برای تعریف یک هش‌مپ، اول باید بفهمیم هش کردن چیه. هش کردن فرایند تبدیل یک کلید یا رشته‌ای از کاراکترها به یک مقدار دیگه‌ست. نتیجه معمولا یک مقدار کوتاه‌تر و با طول ثابته که کار با اون رو از نظر پردازشی راحت‌تر از کلید اصلی می‌کنه.

هش‌مپ‌ها که به اون‌ها جداول هش هم می‌گن، یکی از رایج‌ترین پیاده‌سازی‌های هش کردن هستن. هش‌مپ‌ها جفت‌های کلید-مقدار (مثل آیدی و نام کارمند) رو در یک لیست ذخیره می‌کنن که از طریق اندیس اون قابل دسترسه. هش‌مپ‌ها ساختارهای داده بهینه‌ای هستن که امکان عملیات سریع‌تر روی داده‌ها، از جمله درج، حذف و جستجو رو فراهم می‌کنن.

ایده اصلی هش‌مپ‌ها اینه که جفت‌های کلید/مقدار رو با استفاده از تابع هش در نقاط مختلف یک آرایه پخش کنه. با داشتن یک کلید، یک تابع هش یک اندیس مشخص رو محاسبه می‌کنه که نشون می‌ده ورودی کجا پیدا می‌شه. استفاده از اندیس به جای کلید اصلی باعث می‌شه هش‌مپ‌ها برای عملیات مختلف روی داده‌ها، مثل درج، حذف و جستجو، بسیار مناسب باشن.

برای محاسبه مقدار هش یا همون هش، یک تابع هش مقادیر جدیدی رو بر اساس یک الگوریتم ریاضی تولید می‌کنه. از اونجا که جفت‌های کلید-مقدار در تئوری نامحدود هستن، تابع هش کلیدها رو بر اساس اندازه مشخصی از جدول نگاشت می‌کنه.

توابع هش متعددی وجود دارن که هر کدوم مزایا و معایب خودشون رو دارن. هدف اصلی یک تابع هش اینه که همیشه برای یک ورودی مشخص، یک مقدار یکسان رو برگردونه.

رایج‌ترین اون‌ها عبارتند از:

روش تقسیم: ساده‌ترین و سریع‌ترین راه برای محاسبه مقادیر هش هست. این کار با تقسیم کلید بر اندازه جدول و سپس استفاده از باقیمانده به عنوان هش انجام می‌شه.
روش مربع میانی: مربع کلید داده شده رو پیدا می‌کنه، سپس ارقام میانی رو می‌گیره و از اون‌ها به عنوان اندیس عنصر استفاده می‌کنه.
روش ضرب: اندیس هش رو از بخش کسری ضرب کلید در یک عدد حقیقی بزرگ تنظیم می‌کنه.
روش تا کردن: ابتدا کلید به قطعات مساوی تقسیم می‌شه، خروجی جمع می‌شه و نتیجه بر اندازه جدول تقسیم می‌شه. باقیمانده همون هش هست.

هش‌مپ‌ در پایتون

پایتون هش‌مپ‌ها رو از طریق نوع داده داخلی دیکشنری پیاده‌سازی می‌کنه. مثل هش‌مپ‌ها، دیکشنری‌ها هم داده‌ها رو به صورت جفت‌های {key:value} ذخیره می‌کنن. وقتی دیکشنری رو ایجاد می‌کنی (بخش بعدی رو ببین)، پایتون یک تابع هش مناسب رو در پس‌زمینه اعمال می‌کنه تا هش هر کلید رو محاسبه کنه.

دیکشنری‌های پایتون ویژگی‌های زیر رو دارن:

دیکشنری‌ها تغییرپذیر هستن: این یعنی می‌تونیم بعد از ایجاد دیکشنری، آیتم‌هایی رو تغییر بدیم، اضافه یا حذف کنیم.
عناصر مرتب هستن: در پایتون ۳.۶ و قبل‌تر، دیکشنری‌ها نامرتب بودن، یعنی آیتم‌ها ترتیب مشخصی نداشتن. اما با انتشار پایتون ۳.۷، دیکشنری‌ها ترتیب رو حفظ می‌کنن. حالا وقتی یک دیکشنری پایتون می‌سازی، کلیدها از ترتیبی که در سورس کد نوشته شده پیروی می‌کنن. برای دونستن دلایل این تغییر، می‌تونی این یادداشت از ریموند هتینگر، یکی از توسعه‌دهندگان اصلی پایتون رو بخونی.
کلیدها تغییرناپذیر هستن: این یعنی کلیدها همیشه باید از نوع داده‌هایی باشن که قابل تغییر نیستن. به عبارت دیگه، دیکشنری‌ها فقط نوع داده‌هایی رو می‌پذیرن که قابل هش شدن باشن، مثل رشته‌ها، اعداد و تاپل‌ها. در مقابل، کلیدها هرگز نمی‌تونن یک نوع داده تغییرپذیر مثل لیست باشن.
کلیدها منحصربه‌فرد هستن: کلیدها در یک دیکشنری منحصربه‌فرد هستن و نمی‌تونن تکراری باشن. اگر یک کلید بیش از یک بار استفاده بشه، ورودی‌های بعدی مقدار قبلی رو بازنویسی می‌کنن.

اگر برات سوال شده که تفاوت هش‌مپ و دیکشنری چیه، جواب ساده‌ست. دیکشنری صرفا پیاده‌سازی بومی پایتون از هش‌مپ‌هاست. در حالی که هش‌مپ یک ساختار داده‌ست که با استفاده از تکنیک‌های مختلف هش کردن ساخته می‌شه، دیکشنری یک هش‌مپ خاص مبتنی بر پایتونه که طراحی و رفتار اون در کلاس dict پایتون مشخص شده.

بسیاری از زبان‌های برنامه‌نویسی مدرن مثل پایتون، جاوا و ++C از هش‌مپ‌ها پشتیبانی می‌کنن. در پایتون، هش‌مپ‌ها از طریق دیکشنری‌ها پیاده‌سازی می‌شن، یک ساختار داده پرکاربرد که احتمالا باهاش آشنایی داری. در بخش‌های بعدی، اصول اولیه دیکشنری‌ها، نحوه کار اون‌ها و نحوه پیاده‌سازی‌شون با استفاده از پکیج‌های مختلف پایتون رو بررسی می‌کنیم.

نحوه استفاده از دیکشنری‌های پایتون

بیا بعضی از رایج‌ترین عملیات دیکشنری رو ببینیم. برای دونستن بیشتر درباره نحوه استفاده از دیکشنری‌ها، آموزش ما در فینکا رو ببین: آموزش دیکشنری‌های پایتون.

ایجاد یک دیکشنری

ساخت دیکشنری در پایتون خیلی ساده‌ست. فقط باید از آکولاد استفاده کنی و جفت‌های کلید-مقدار رو با کاما از هم جدا کنی. در غیر این صورت، می‌تونی از تابع داخلی dict() استفاده کنی. بیا یک دیکشنری بسازیم که پایتخت‌ها رو به کشورها نگاشت می‌کنه:

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

یادت باشه که یک کلید در دیکشنری باید منحصربه‌فرد باشه؛ هیچ کلید تکراری مجاز نیست. با این حال، در صورت وجود کلیدهای تکراری، پایتون به جای خطا دادن، آخرین نمونه از کلید رو معتبر می‌دونه و جفت کلید-مقدار اول رو به سادگی نادیده می‌گیره. خودت ببین:

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

جستجو در یک دیکشنری

برای جستجوی اطلاعات در دیکشنری، باید کلید رو در براکت مشخص کنیم و پایتون مقدار مرتبط با اون رو برمی‌گردونه، به این شکل:

Spain

اگر سعی کنی به کلیدی که در دیکشنری وجود نداره دسترسی پیدا کنی، پایتون خطا می‌ده. برای جلوگیری از این اتفاق، می‌تونی از متد .get() برای دسترسی به کلیدها استفاده کنی. در صورت عدم وجود کلید، این متد فقط مقدار None رو برمی‌گردونه:

None

اضافه و حذف کردن مقادیر در یک دیکشنری

بیا یک جفت پایتخت-کشور جدید اضافه کنیم:

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom', 'Berlin': 'Italy'}

از همین سینتکس می‌تونی برای به‌روزرسانی مقدار یک کلید استفاده کنی. بیا مقدار مربوط به برلین رو اصلاح کنیم:

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom', 'Berlin': 'Germany'}

حالا بیا یکی از جفت‌ها رو از دیکشنری حذف کنیم.

{'Madrid': 'Spain', 'London': 'United Kingdom', 'Berlin': 'Germany'}

یا اگر بخوای تمام جفت‌های کلید-مقدار دیکشنری رو حذف کنی، می‌تونی از متد .clear() استفاده کنی:

{}

پیمایش دیکشنری‌ها با حلقه

اگر می‌خوای تمام جفت‌های کلید-مقدار رو بگیری، از متد .items() استفاده کن و پایتون یک لیست قابل پیمایش از تاپل‌ها بهت می‌ده:

dict_items([('Madrid', 'Spain'), ('Lisboa', 'Portugal'), ('London', 'United Kingdom'), ('Berlin', 'Germany')])

the capital of Spain is Madrid
the capital of Portugal is Lisboa
the capital of United Kingdom is London
the capital of Germany is Berlin

همین‌طور، اگر می‌خوای یک لیست قابل پیمایش از کلیدها و مقادیر به صورت جداگانه بگیری، می‌تونی به ترتیب از متدهای .keys() و .values() استفاده کنی:

dict_keys(['Madrid', 'Lisboa', 'London', 'Berlin'])

MADRID
LISBOA
LONDON
BERLIN

dict_values(['Spain', 'Portugal', 'United Kingdom', 'Germany'])

SPAIN
PORTUGAL
UNITED KINGDOM
GERMANY

کاربردهای هش‌مپ‌ها در دنیای واقعی

هش‌مپ‌ها ساختارهای داده قدرتمندی هستن که تقریبا همه جا در دنیای دیجیتال استفاده می‌شن. در ادامه می‌تونی لیستی از کاربردهای واقعی هش‌مپ‌ها رو ببینی:

اندیس‌گذاری دیتابیس: هش‌مپ‌ها اغلب برای اندیس‌گذاری و جستجوی حجم عظیمی از داده‌ها استفاده می‌شن. مرورگرهای وب رایج از هش‌مپ‌ها برای ذخیره صفحات وب اندیس‌شده استفاده می‌کنن.
مدیریت cache: سیستم‌عامل‌های مدرن از هش‌مپ‌ها برای سازماندهی حافظه cache استفاده می‌کنن تا دسترسی سریع به اطلاعات پرکاربرد رو فراهم کنن.
رمزنگاری: هش‌مپ‌ها نقش مهمی در زمینه رمزنگاری دارن. الگوریتم‌های رمزنگاری از هش‌مپ‌ها برای تضمین یکپارچگی داده‌ها، اعتبارسنجی داده‌ها و تراکنش‌های امن در شبکه‌ها استفاده می‌کنن.
بلاک‌چین: هش‌مپ‌ها در هسته بلاک‌چین قرار دارن. هر بار که تراکنشی در شبکه رخ می‌ده، داده‌های اون تراکنش به عنوان ورودی به تابع هش داده می‌شه که سپس یک خروجی منحصربه‌فرد تولید می‌کنه. هر بلاک در بلاک‌چین هش بلاک قبلی رو به همراه داره و زنجیره‌ای از بلاک‌ها رو تشکیل می‌ده.

بهترین روش‌ها و اشتباهات رایج در استفاده از هش‌مپ

هش‌مپ‌ها ساختارهای داده فوق‌العاده همه‌کاره و کارآمدی هستن. با این حال، مشکلات و محدودیت‌های خاص خودشون رو هم دارن. برای مقابله با چالش‌های رایج مرتبط با هش‌مپ‌ها، مهمه که بعضی از نکات و روش‌های خوب رو در نظر داشته باشی.

کلیدها باید تغییرناپذیر باشن

این موضوع منطقیه: اگر محتوای کلید تغییر کنه، تابع هش مقدار متفاوتی رو برمی‌گردونه، بنابراین پایتون نمی‌تونه مقدار مرتبط با کلید رو پیدا کنه.

رسیدگی به تداخل‌ها در هش‌مپ‌

هش کردن تنها در صورتی کار می‌کنه که هر آیتم به یک مکان منحصربه‌فرد در جدول هش نگاشت بشه. اما گاهی اوقات، توابع هش ممکنه برای ورودی‌های مختلف، خروجی یکسانی برگردونن. برای مثال، اگر از یک تابع هش تقسیمی استفاده می‌کنی، ممکنه اعداد صحیح مختلف تابع هش یکسانی داشته باشن (ممکنه هنگام اعمال تقسیم ماژول، باقیمانده یکسانی برگردونن)، در نتیجه مشکلی به نام تداخل ایجاد می‌شه. تداخل‌ها باید برطرف بشن و تکنیک‌های مختلفی برای این کار وجود داره. خوشبختانه در مورد دیکشنری‌ها، پایتون تداخل‌های احتمالی رو در پس‌زمینه مدیریت می‌کنه.

درک load factor

load factor به صورت نسبت تعداد عناصر به تعداد جایگاه‌های موجود در جدول تعریف می‌شه. این معیاری برای تخمین میزان توزیع خوب داده‌هاست. به عنوان یک قاعده کلی، هرچه داده‌ها به طور یکنواخت‌تر توزیع بشن، احتمال تداخل کمتره. باز هم، در مورد دیکشنری‌ها، پایتون به طور خودکار اندازه جدول رو در صورت درج یا حذف جفت‌های کلید-مقدار جدید تطبیق می‌ده.

توجه به عملکرد

یک تابع هش خوب تعداد تداخل‌ها رو به حداقل می‌رسونه، محاسبه اون آسونه و آیتم‌ها رو به طور مساوی در جدول هش توزیع می‌کنه. این کار می‌تونه با افزایش اندازه جدول یا پیچیدگی تابع هش انجام بشه. اگرچه این کار برای تعداد کمی از آیتم‌ها عملیه، اما زمانی که تعداد آیتم‌های احتمالی زیاد باشه، امکان‌پذیر نیست؛ چون منجر به هش‌مپ‌های پرمصرف از نظر حافظه و با کارایی کمتر می‌شه.

آیا دیکشنری‌ها همون چیزی هستن که نیاز داری؟

دیکشنری‌ها عالی هستن، اما ساختارهای داده دیگه ممکنه برای داده‌ها و نیازهای خاص تو مناسب‌تر باشن. در نهایت، دیکشنری‌ها از عملیات رایجی مثل اندیس‌گذاری، برش و اتصال پشتیبانی نمی‌کنن، که باعث می‌شه انعطاف‌پذیری کمتری داشته باشن و کار با اون‌ها در بعضی سناریوها دشوارتر باشه.

پیاده‌سازی‌های جایگزین هش‌مپ‌ در پایتون

همون‌طور که قبلا گفته شد، پایتون هش‌مپ‌ها رو از طریق دیکشنری‌های داخلی پیاده‌سازی می‌کنه. با این حال، مهمه بدونی ابزارهای بومی دیگه پایتون و همچنین کتابخونه‌های جانبی برای استفاده از قدرت هش‌مپ‌ها وجود دارن.

بیا چند تا از محبوب‌ترین نمونه‌ها رو ببینیم.

Defaultdict

هر بار که سعی می‌کنی به کلیدی که در دیکشنری وجود نداره دسترسی پیدا کنی، پایتون یک خطای KeyError می‌ده. یک راه برای جلوگیری از این کار، جستجوی اطلاعات با استفاده از متد .get() هست. با این حال، یک راه بهینه‌تر برای این کار استفاده از Defaultdict هست که در ماژول collections موجوده. Defaultdict و دیکشنری‌ها تقریبا یکسان هستن. تنها تفاوت اینه که Defaultdict هرگز خطا نمی‌ده چون یک مقدار پیش‌فرض برای کلیدهای ناموجود فراهم می‌کنه.

Spain
Portugal
The key doesn't exist

Counter

Counter یک زیرکلاس از دیکشنری پایتونه که مخصوص شمارش آبجکت‌های قابل هش طراحی شده. این یک دیکشنریه که در اون عناصر به عنوان کلید و تعداد اون‌ها به عنوان مقدار ذخیره می‌شه.

چندین راه برای مقداردهی اولیه Counter وجود داره:

با استفاده از دنباله‌ای از آیتم‌ها.
با استفاده از کلیدها و تعداد در یک دیکشنری.
با استفاده از نگاشت name:value.

Counter({'aaa': 3, 'ccc': 2, 'bbb': 1})
Counter({'red': 4, 'blue': 2})
Counter({'dogs': 8, 'cats': 4})

کلاس شمارنده یک سری متدهای کاربردی برای انجام محاسبات رایج داره.

keys of the counter:  dict_keys(['cats', 'dogs'])
values of the counter:  dict_values([4, 8])
list with all elements:  ['cats', 'cats', 'cats', 'cats', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs']
number of elements:  12
2 most common occurrences:  [('dogs', 8), ('cats', 4)]

متدهای هش کردن Scikit-learn

کتابخونه Scikit-learn که با نام sklearn هم شناخته می‌شه، یک کتابخونه یادگیری ماشین قوی و متن‌باز در پایتونه. این کتابخونه برای کمک به ساده‌سازی فرایند پیاده‌سازی یادگیری ماشین و مدل‌های آماری در پایتون ساخته شده.

کتابخونه Sklearn متدهای هش کردن مختلفی داره که برای فرایندهای مهندسی ویژگی بسیار مفیدن.

یکی از رایج‌ترین اون‌ها، متد CountVectorizer هست. از این متد برای تبدیل یک متن مشخص به یک بردار بر اساس فراوانی تکرار هر کلمه در کل متن استفاده می‌شه. CountVectorizer به خصوص در زمینه‌های تحلیل متن خیلی مفیده.

unique words:  ['analyst' 'career' 'course' 'data' 'finca' 'new' 'python' 'skill'
 'this' 'to' 'track' 'welcome']

       analyst  career  course  data  finca  new  python  skill  this  to  track  welcome
0        0       0       1     0         1    1       1      0     1   1      0        1
1        0       0       0     0         1    1       0      1     1   1      1        1
2        1       1       0     1         1    1       0      0     1   1      1        1

متدهای هش کردن دیگه‌ای هم در sklearn وجود داره، از جمله FeatureHasher و DictVectorizer.

نتیجه‌گیری

تبریک می‌گیم که این آموزش درباره هش‌مپ‌ها رو به پایان رسوندی. امیدواریم حالا درک بهتری از هش‌مپ‌ها و دیکشنری‌های پایتون داشته باشی. اگر احساس می‌کنی می‌خوای چیزهای بیشتری درباره دیکشنری‌ها و نحوه استفاده از اون‌ها در سناریوهای واقعی یاد بگیری، به شدت پیشنهاد می‌کنیم آموزش دیکشنری‌های پایتون، و همچنین آموزش دیکشنری کامپرهنشن ما رو بخونی.

در نهایت، اگر به تازگی کار با پایتون رو شروع کردی و دوست داری بیشتر یاد بگیری، نگاهی به آموزش پایتون برای مبتدیان بنداز.