HashMap یکی از متداول‌ترین ساختارهای داده‌ای است که در جاوا استفاده می‌شود و به دلیل کارایی آن مشهور است. داده ها در HashMap به شکل جفت کلید-مقدار ذخیره می شوند.

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

HashMap در جاوا چیست ؟

یک HashMap رابط Map را پیاده سازی می کند که بخشی از چارچوب مجموعه جاوا است. این بر اساس مفهوم Hashing است.

هش کردن تکنیکی است که ورودی با اندازه دلخواه را با استفاده از تابع هش به خروجی با اندازه ثابت تبدیل می کند. خروجی تولید شده کد هش نامیده می شود و با یک عدد صحیح در جاوا نشان داده می شود. کدهای هش برای عملیات جستجو و ذخیره سازی کارآمد در HashMap استفاده می شود.

عملیات مشترک

همانطور که در بالا توضیح دادیم، داده ها در HashMap به شکل جفت های کلید-مقدار ذخیره می شوند. کلید یک شناسه منحصر به فرد است و هر کلید با یک مقدار مرتبط است.

در زیر برخی از عملیات متداول پشتیبانی شده توسط HashMap آورده شده است. بیایید بفهمیم که این روش ها با چند نمونه کد ساده چه کار می کنند:

درج

این روش یک جفت کلید-مقدار جدید را به HashMap وارد می کند.

ترتیب درج جفت های کلید-مقدار حفظ نمی شود.

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

شما می توانید تنها یک کلید تهی را در HashMap وارد کنید، اما می توانید چندین مقدار null داشته باشید.

امضای متد برای این عملیات در زیر آورده شده است و به دنبال آن یک مثال آمده است:

 public V put (K key, V value)

 Map<String, Integer> map = new HashMap<>(); map.put( "apple" , 1 ); map.put( "banana" , 2 );

در کد بالا، یک مثال HashMap داریم که در آن یک کلید از نوع String و مقدار از نوع Integer اضافه می کنیم.

بازیابی:

مقدار مرتبط با یک کلید داده شده را واکشی می کند.

اگر کلید در HashMap وجود نداشته باشد، null برمی‌گرداند.

امضای متد برای این عملیات در زیر آورده شده است و به دنبال آن یک مثال آمده است:

 public V get (Object key)

 Integer value = map.get( "apple" ); // returns 1

در کد بالا، مقدار مربوط به key apple را بازیابی می کنیم.

سایر عملیات رایج عبارتند از:

remove : جفت کلید-مقدار را برای کلید مشخص شده حذف می کند. اگر کلید پیدا نشد، آن را null برمی گرداند.

containsKey : تحلیل می کند که آیا کلید خاصی در HashMap وجود دارد یا خیر.

containsValue : تحلیل می کند که آیا مقدار مشخص شده در HashMap وجود دارد یا خیر.

ساختار داخلی HashMap

در داخل، HashMap از آرایه ای از سطل ها یا سطل ها استفاده می کند. هر سطل یک فهرست پیوندی از نوع Node است که برای نشان دادن جفت کلید-مقدار HashMap استفاده می شود.

 static class Node < K , V > { final int hash; final K key; V value; Node<K, V> next; Node( int hash, K key, V value, Node<K, V> next) { this .hash = hash; this .key = key; this .value = value; this .next = next; } }

در بالا، می‌توانید ساختار کلاس Node را ببینید که برای ذخیره جفت‌های کلید-مقدار HashMap استفاده می‌شود.

کلاس Node دارای فیلدهای زیر است:

hash : به hashCode کلید اشاره دارد.

key : به کلید جفت کلید-مقدار اشاره دارد.

value : به مقدار مرتبط با کلید اشاره دارد.

next : به عنوان ارجاع به گره بعدی عمل می کند.

HashMap اساساً مبتنی بر اجرای جدول هش است و عملکرد آن به دو پارامتر کلیدی بستگی دارد: ظرفیت اولیه و ضریب بار. javadoc های اصلی کلاس جدول Hash این دو پارامتر را به صورت زیر تعریف می کنند:

ظرفیت تعداد سطل های جدول هش است و ظرفیت اولیه به سادگی ظرفیت در زمان ایجاد جدول هش است.

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

اکنون بیایید تلاش کنیم و بفهمیم که چگونه عملیات اساسی، put و get ، در HashMap کار می کنند.

عملکرد هش

در طول درج ( put ) یک جفت کلید-مقدار، HashMap ابتدا کد هش کلید را محاسبه می کند. سپس تابع هش یک عدد صحیح برای کلید محاسبه می کند. کلاس ها می توانند از متد hashCode کلاس Object استفاده کنند یا این متد را لغو کنند و پیاده سازی خود را ارائه دهند. (در مورد قرارداد کد هش اینجا را بخوانید). سپس کد هش با 16 بیت بالای آن (h >>> 16) XOR می شود (OR eXclusive) تا توزیع یکنواخت تری حاصل شود.

XOR یک عملیات بیتی است که دو بیت را با هم مقایسه می کند و اگر بیت ها متفاوت باشند 1 و اگر یکسان باشند 0 می شود. در این زمینه، انجام عملیات XOR بیتی بین کد هش و 16 بیت بالای آن (که با استفاده از عملگر تغییر علامت سمت راست >>> به دست آمده است) به ترکیب بیت ها کمک می کند و منجر به توزیع یکنواخت کد هش می شود.

 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }

در بالا، می توانید متد هش استاتیک کلاس HashMap را مشاهده کنید.

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

محاسبه شاخص

هنگامی که کد هش برای یک کلید تولید شد، HashMap یک شاخص را در آرایه سطل ها محاسبه می کند تا تعیین کند جفت کلید-مقدار کجا ذخیره می شود. این کار با استفاده از یک عملیات بیتی AND انجام می شود، که روشی کارآمد برای محاسبه مدول زمانی است که طول آرایه توان دو باشد.

 int index = (n - 1 ) & hash;

در اینجا، ما در حال محاسبه شاخصی هستیم که n طول آرایه سطلی است.

هنگامی که شاخص محاسبه شد، کلید در آن شاخص در آرایه سطلی ذخیره می شود. با این حال، اگر چندین کلید در نهایت دارای یک شاخص باشند، باعث برخورد می شود. در چنین سناریویی، HashMap آن را به یکی از دو روش مدیریت می کند:

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

Treeify: اگر تعداد گره ها از یک آستانه خاص فراتر رود، فهرست پیوند شده به درخت تبدیل می شود (این در جاوا 8 معرفی شد).

 static final int TREEIFY_THRESHOLD = 8 ;

این آستانه ای است که درخت شدن را تعیین می کند.

پس ، داشتن یک عملکرد هش خوب که کلیدها را به طور یکنواخت در بین سطل ها توزیع می کند و احتمال برخورد را به حداقل می رساند ضروری است.

عملیات بازیابی ( get ) و حذف ( remove ) مشابه عملیات درج ( put ) عمل می کنند. در اینجا به این صورت است:

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

حذف ( remove ): کد هش را با استفاده از تابع هش محاسبه می کند -> شاخص را با استفاده از کد هش محاسبه می کند -> گره را از فهرست پیوند یا درخت حذف می کند.

پیچیدگی زمانی

عملیات اصلی HashMap ، مانند put ، get و remove ، معمولاً عملکرد زمانی ثابت O(1) را ارائه می‌کنند، با این فرض که کلیدها به طور یکنواخت توزیع شده‌اند. در مواردی که توزیع کلید ضعیف وجود دارد و برخوردهای زیادی رخ می دهد، این عملیات ممکن است به پیچیدگی زمانی خطی O(n) تنزل یابد.

تحت درخت‌سازی، که در آن زنجیره‌های طولانی از برخوردها به درخت‌های متعادل تبدیل می‌شوند، عملیات جستجو می‌تواند به پیچیدگی زمانی لگاریتمی کارآمدتر O(log n) ارتقا یابد.

همگام سازی

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

برای جلوگیری از این امر، می توانید با استفاده از متد Collections.synchronizedMap یک نمونه thread-safe ایجاد کنید.

نتیجه گیری

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

خبرکاو