مقاله
شروع کنید
شروع به یادگیری
JavaRush /وبلاگ جاوا /Random-FA /تجزیه و تحلیل دقیق کلاس HashMap
Vonorim
مرحله

تجزیه و تحلیل دقیق کلاس HashMap

در گروه منتشر شد
قبل از اینکه به بحث مفصل در مورد کلاس بپردازیم، بیایید روی مفاهیم اساسی مرتبط با جداول هش تمرکز کنیم. در این مقاله روش‌های کار با هش مپینگ مورد بحث قرار نخواهد گرفت. فقط عملیات درج، جستجو و حذف به وضوح و با جزئیات مورد بحث قرار خواهد گرفت. من فکر می کنم خواندن شرح روش های موجود برای HashMap از همان Schildt دشوار نخواهد بود. شاید در آینده مقاله دیگری بنویسم که به چنین روش هایی اختصاص دارد، اما در حال حاضر این مورد شک است. در مقایسه با جاوا 7، کلاس HashMap در جاوا 8 دستخوش تغییرات قابل توجهی شده است (+1000 خط کد). می‌توانید در مورد پیاده‌سازی در جاوا 7 اینجا بخوانید (اما دیگر مرتبط نیست): habr یک جدول هش ساختار داده‌ای است که رابط آرایه‌ای انجمنی (مدل یا ورودی انتزاعی کلید-مقدار) را پیاده‌سازی می‌کند، که درج و جستجوی بسیار سریع را فراهم می‌کند: بدون توجه به درج عناصر عددی و جستجو (و گاهی اوقات حذف) در زمانی نزدیک به یک ثابت - O(1) انجام می شود. در اصل، این یک آرایه معمولی است که در آن مکان عنصر به مقدار خود عنصر بستگی دارد. رابطه بین مقدار یک عنصر و موقعیت آن در جدول هش توسط یک تابع هش مشخص می شود. یک تابع هش یک قطعه داده ورودی را می گیرد که آن را یک کلید می نامیم و به عنوان یک خروجی یک عدد صحیح به نام مقدار هش (یا کد هش) تولید می کند . سپس مقدار هش کلید ما را به یک فهرست جدول هش خاص متصل می کند. برای عملیات اصلی: درج، جستجو و حذف، از همان تابع هش استفاده می کنیم، بنابراین این عملیات بسیار سریع انجام می شود. به همین دلیل، مهم است که تابع هش به طور مداوم رفتار کند و همان شاخص را برای داده های ورودی یکسان تولید کند. شایان ذکر است که کد هش حاصل می تواند یک مقدار عددی بزرگ باشد و آرایه اصلی به صورت مشروط فقط برای 16 عنصر طراحی شده است. چرا یک آرایه با یک میلیارد عنصر ایجاد نمی کنید تا فقط ده عنصر را اضافه کنید؟ بنابراین، باید به نحوی این کد هش را به مقادیری از 0 تا 15 تبدیل کنیم (اگر اندازه آرایه 16 باشد). و برای این، از تبدیل های اضافی استفاده می شود. بنابراین ما یک شاخص ایجاد می کنیم تا اندازه آرایه را به حداقل برسانیم. به عنوان مثال، در HashMap قبل از جاوا 8، از این روش اضافی برای یافتن سلول مورد نظر استفاده می شد: 
static int indexFor(int h, int length) {
        return h & (length-1);
}
به عنوان ورودی، کد هش به دست آمده در نتیجه کار hashCode()و طول آرایه داخلی (تعداد سلول) را گرفت. و نتیجه "کد هش" -> بیتی "AND" -> را برگرداند (طول آرایه – 1). کلاس HashMapاز کلاس ارث می برد AbstractMapو رابط های زیر را پیاده سازی می کند: Map, Cloneable, Serializable. متد. مسئول تابع هش در جاوا است hashCode(). پیاده سازی پیش فرض hashCode()مقداری به نام کد هش هویت را برمی گرداند . حتی اگر یک کلاس لغو شود hashCode()، همیشه می‌توانید با فراخوانی هش شناسه شی را دریافت کنید System.identityHashCode(Object o). پیاده سازی پیش فرض hashCode()در OpenJDK هیچ ربطی به آدرس حافظه ندارد، همانطور که گاهی اوقات تصور می شود. جزئیات بیشتر در اینجا: habr در HashMap ، جدول هش بر اساس یک آرایه (یا به طور دقیق‌تر، پویا، زیرا جدول می‌تواند گسترش یابد) از لیست‌های پیوندی منفرد پیاده‌سازی می‌شود. اساساً ما کد هش کلید را در نتیجه روش بدست می آوریم hashCode()که سپس اصلاح می شود (همانطور که بعداً در نظر خواهیم گرفت) و در داخل با استفاده از یک روش اضافی ، مقادیر حاصل در سلول های مورد نیاز توزیع می شود. عناصر آرایه (سلول ها) نیز سطل نامیده می شوند که برای ذخیره گره های جداگانه استفاده می شوند. هر سطل یک مجموعه (فهرست یا درخت) است. گره یک شی از یک کلاس تودرتو Node(یا TreeNodeدر یک ساختار درختی) است. در واقع، در داخل سلول آرایه LinkedListفقط یک لیست پیوندی منفرد یا یک درخت قرمز-سیاه قرار دارد که زیربنای اجرای کلاس دیگری است - TreeMap.
تجزیه و تحلیل دقیق کلاس HashMap - 1
گزینه با درخت قرمز-مشکی اغلب ایجاد نمی شود (چگونه، چه چیزی و کجا - در زیر)، و درک این ساختار بسیار دشوار است، بنابراین تأکید بر گره ای از نوع Node خواهد بود. Node یک کلاس تو در تو است HashMapکه دارای فیلدهای زیر است:
تجزیه و تحلیل دقیق کلاس HashMap - 2
  • final int hash- هش عنصر فعلی که در نتیجه هش کردن کلید بدست می آوریم.
  • final K key- کلید عنصر فعلی. در اینجا چیزی است که شما به عنوان اولین شی در متد مشخص می کنید، روی آن نوشته می شود put().
  • V value- مقدار عنصر فعلی و آنچه به عنوان شیء دوم در متد مشخص می کنید در اینجا نوشته شده است put().
  • Node < K, V> next- پیوند به گره بعدی در همان سبد. لیست متصل است، بنابراین به پیوندی نیاز دارد نه به گره بعدی، در صورت وجود.
حالا بیایید به فیلدهای خود کلاس HashMap نگاه کنیم:
  • transient Node < K, V> [] table- خود جدول هش که بر اساس یک آرایه برای ذخیره جفت های کلید-مقدار در قالب گره ها پیاده سازی شده است. این جایی است که گره های ما ذخیره می شوند.
  • transient int size- تعداد جفت های کلید-مقدار؛
  • int threshold- حداکثر تعداد عناصر که با رسیدن به آن اندازه جدول هش دو برابر می شود. با استفاده از فرمول (ظرفیت * loadFactor) محاسبه می شود.
  • final float loadFactor- این پارامتر تعیین می کند که جدول هش فعلی برای ایجاد یک جدول هش جدید در چه درجه ای از بار نیاز دارد. به محض اینکه جدول هش 75٪ پر شد، یک جدول هش جدید ایجاد می شود و عناصر فعلی به آن منتقل می شوند (عملیاتی پرهزینه، زیرا همه عناصر باید دوباره هش شوند).
  • transient Set< Map.Entry< K,V>> entrySet- حاوی یک حافظه پنهان است entrySet()که با آن می توانیم تکرار کنیم HashMap.
و ثابت ها:
Java-университет
  • static final int DEFAULT_INITIAL_CAPACITY= 1 << 4- ظرفیت جدول هش پیش فرض (16)؛
  • static final int MAXIMUM_CAPACITY = 1 << 30- حداکثر ظرفیت ممکن جدول هش (تقریباً 1 میلیارد)؛
  • static final float DEFAULT_LOAD_FACTOR = 0.75f- فاکتور بار پیش فرض؛
  • static final int TREEIFY_THRESHOLD = 8"آستانه" تعداد عناصر در یک سطل است که با رسیدن به آن لیست پیوند داخلی به ساختار درختی (درخت قرمز-سیاه) تبدیل می شود.
  • static final int UNTREEIFY_THRESHOLD = 6- اگر تعداد عناصر در یک سبد به 6 کاهش یابد، انتقال معکوس از یک درخت به یک لیست پیوندی رخ خواهد داد.
  • static final int MIN_TREEIFY_CAPACITY = 64- حداقل ظرفیت (تعداد سطل) جدول هش که در آن انتقال به ساختار درختی امکان پذیر است. آن ها اگر حداقل 64 سطل در جدول هش وجود داشته باشد و 8 یا بیشتر عنصر در یک سطل وجود داشته باشد، انتقال به ساختار درختی رخ خواهد داد.
سازندگان کلاس:
  1. public HashMap()- به طور پیش فرض یک نمایش هش ایجاد می کند: بر اساس حجم (capacity) = 16و با ضریب بار (load factor) = 0.75.
  2. public HashMap(Map< ? extends K, ? extends V> m)- یک نگاشت هش ایجاد می کند که توسط عناصر یک نقشه داده شده دیگر با ظرفیت اولیه ای که برای جا دادن عناصر یک نقشه دیگر کافی است، مقداردهی اولیه می کند.
  3. public HashMap(int initialCapacity)- یک نقشه هش با ظرفیت اولیه مشخص ایجاد می کند. برای اینکه HashMap به درستی و درستی کار کند، اندازه آرایه داخلی باید توان دو باشد (یعنی 16، 64، 128، و غیره).
  4. public HashMap(int initialCapacity, float loadFactor)- یک نقشه هش با پارامترهای مشخص شده ایجاد می کند: ظرفیت اولیه و ضریب بار.
یک کلاس یک رابط را پیاده سازی می کند Mapو یک کلاس را AbstractMapبدون اضافه کردن متدهای خود گسترش می دهد. نقشه هش ترتیب عناصر آن را تضمین نمی کند. بنابراین، ترتیب ورود عناصر به نقشه هش لزوماً ترتیبی نیست که توسط تکرار کننده بازیابی می شوند. افزودن اشیا افزودن یک جفت کلید-مقدار با استفاده از put(). بیایید به مراحلی که در هنگام افزودن یک شیء در آن وجود دارد نگاه کنیم:

  1. مقدار هش کلید شی وارد شده محاسبه می شود. هش کلید با روشی محاسبه می شود static final int hash(Object key)که از قبل به hashCode()روش کلیدی که ما می شناسیم دسترسی دارد. برای انجام این کار، یا از یک روش بازنویسی شده hashCode()یا پیاده سازی پیش فرض آن استفاده می شود. تغییرات اضافی در روش hash():

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

    Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

  2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

    
i = (n - 1) & hash

    где n – длина массива.

  3. Создается an object Node.

  4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

    Теперь к очень подробному примеру.

    1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

    2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

    3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

    4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

    5. در همان زمان، شاخص سطلی را محاسبه می کنیم که شی ما در آن قرار می گیرد و بررسی می کنیم که آیا از قبل عناصری در آن وجود دارد یا خیر. محاسبه می کنیم:

      
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4

      بررسی:

      
if ((p = tab[i = (n - 1) & hash]) == null)

    6. از آنجایی که در نتیجه بررسی درست می‌شویم (هیچ عنصری در سطل وجود ندارد)، یک شی Node با فیلدهای زیر تولید می‌شود:

      
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
      تجزیه و تحلیل دقیق کلاس HashMap - 3

      شی Node تولید شده ما به سطل زیر شاخص [4] اضافه می شود:

      tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()متدی است که به سادگی یک شی از کلاس Node را برمی گرداند.

    7. پس از افزودن، بررسی می شود که آیا تعداد عناصر فعلی از پارامتر بیشتر است یا خیر threshold:

      if (++size > threshold)
    resize();

      اگر بیش از آن باشد، روشی resize()برای افزایش اندازه جدول هش فراخوانی می شود.

      در این مرحله، متد putVal()(و به ترتیب put()) کار خود را کامل می کند.

      نتیجه را می توان به صورت گرافیکی به صورت زیر نشان داد:

      تجزیه و تحلیل دقیق کلاس HashMap - 4

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

کمی در مورد برخورد وضعیتی که در آن کلیدهای مختلف در یک سطل (حتی با هش های مختلف) قرار می گیرند، برخورد یا برخورد نامیده می شود. حتی اگر جدول هش بزرگ‌تر از مجموعه داده‌ها باشد و یک تابع هش خوب انتخاب شده باشد، این تضمین نمی‌کند که برخورد رخ ندهد. و مقدار هش محدود به محدوده مقادیر int (حدود 4 میلیارد) است. مقدار جدید به دست آمده نیز باید در جایی نوشته شود، و برای این باید تعیین کنید که دقیقا کجا نوشته شود. به این می گویند حل تعارض. دو رویکرد وجود دارد:
  • روش زنجیره ای یا زنجیره ای خارجی (اجرا شده در HashMap) - i.e. سلول در واقع شامل یک لیست (زنجیره) است. و لیست ممکن است قبلاً حاوی چندین مقدار باشد (نه لزوما با کد هش یکسان).
  • روش کاوش خطی یا آدرس دهی باز (اجرا شده در IdentityHashMap) - شامل جستجوی اولین سلول خالی بعد از سلولی است که تابع هش به آن اشاره می کند.
شما می توانید در مورد برخورد اینجا بخوانید: کلیک کنید

  1. با استفاده از روش، put()یک جفت کلید-مقدار دیگر را به نگاشت هش اضافه می کنیم:

    map.put("BLAKE", 10);

  2. ما "هش اولیه" - 63281361 را محاسبه می کنیم. آن را تغییر می دهیم و در نتیجه کد هش نهایی - 63281940 را می گیریم.

  3. از آنجایی که اولین بررسی برای "خالی بودن" اکنون نادرست است (نیازی به ایجاد جدول نیست)، بلافاصله شاخص سطلی را محاسبه می کنیم که شی ما در آن قرار می گیرد:

    
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4

  4. سطل در شاخص مشخص شده برای وجود عناصر در آن بررسی می شود، و از آنجایی که شرط if ((p = tab[i = (n - 1) & hash]) == null)در این مورد برآورده نمی شود (از قبل یک عنصر در سطل وجود دارد)، به بلوک می رویم else.

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

    (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:

    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
      e.value = value;
      afterNodeAccess(e);
       return oldValue;
 }

    В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

  6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

  7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

    if ((e = p.next) == null){
	p.next = newNode(hash, key, value, null)
... };

    Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

    Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))

    Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

    После добавления второго element наш an object HashMap графически выглядит так:

    تجزیه و تحلیل دقیق کلاس HashMap - 5

    В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

    • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
    • если ключи одинаковы, заменить текущее meaning новым.
    • иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

  8. После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

    for (int binCount = 0; ; ++binCount)

    До тех пор, пока их количество не станет равно or больше 7:

    binCount >= TREEIFY_THRESHOLD – 1

    В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

    به جای رفتن به ساختار درختی، روشی resize()برای افزایش اندازه جدول هش و توزیع مجدد عناصر فراخوانی می شود. treeify()به نوبه خود، لیست پیوندی TreeNodeتبدیل شده به درخت قرمز-سیاه. این روش resize()در تمام عناصر ذخیره سازی فعلی تکرار می شود، شاخص های آنها را مجدداً محاسبه می کند (با در نظر گرفتن اندازه جدید) و عناصر را در یک آرایه جدید توزیع می کند.

    به طور خلاصه، بدون پرداختن به جزئیات ساختار درخت قرمز-سیاه، موارد زیر رخ می دهد:

    1. اولین عنصر لیست به عنوان ریشه کل درخت (سیاه) نوشته می شود:

      if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}

    2. برای سایر عناصر:

      آنها را بسته به مقدار هش به چپ یا راست توزیع کنید:

      if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;

      همه فرزندان سمت چپ باید کمتر از (یا مساوی) گره ریشه خود باشند، در حالی که همه فرزندان سمت راست باید بزرگتر باشند.

    3. اگر دو عنصر دارای هش‌های یکسانی باشند و به هیچ وجه قابل مقایسه نباشند (اینترفیس را پیاده‌سازی نمی‌کنند Comparable)، ساخت درخت را قطع می‌کنیم و متد را فراخوانی می‌کنیم tieBreakOrder()، که به نوبه خود از روش بومی System.identityHashCode()برای محاسبه کد هش منحصربه‌فرد جهانی استفاده می‌کند. .

      جزئیات بیشتر در اینجا: پیوند به مقاله

    4. عناصر درختی (اشیاء TreeNode) را بررسی می کنیم تا زمانی که عنصر صفر فرزند (چپ یا راست) پیدا شود.

      if ((p = (dir <= 0) ? p.left : p.right) == null)

    5. اضافه کردن یک گره فرزند (چپ یا راست بسته به dir):

      x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;

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

      root = balanceInsertion(root, x);

      شما می توانید در مورد تعادل CCH در اینجا بخوانید: habr

    7. پس از متعادل کردن، عنصر ریشه ممکن است تغییر کند. ما این مشکل را با فراخوانی متدی که تضمین می‌کند ریشه ارسال شده به آن اولین گره باشد، برطرف می‌کنیم:

      moveRootToFront(tab, root)

      در اینجا می توانید به وضوح ببینید که چگونه یک درخت قرمز-سیاه ساخته شده و خود را متعادل می کند: تجسم

در اصل این همه چیز است و با استفاده از یک مثال، فرض می کنیم که می خواهیم نام های زیر را به عنوان کلید اضافه کنیم: KING، MARY، JOSE، ANNA، FRED، TONY، ALEX، PEPE. و فرض کنید که ما حداقل 64 سطل در جدول هش داریم و همه این عناصر در یک سطل جمع شده اند. از نظر ساختاری، این سطل به این شکل خواهد بود (عناصر بر اساس کد هش مرتب شده اند): نوع CCHD:
تجزیه و تحلیل دقیق کلاس HashMap - 6
نمای داخل سطل:
تجزیه و تحلیل دقیق کلاس HashMap - 7
بازیابی عناصر (بازیابی یک مقدار توسط کلید) در مورد عملیات اضافه کردن، بسیار ساده است. الگوریتم (زمانی که یک لیست پیوندی در سطل وجود دارد) را می توان به صورت زیر نوشت:
  1. کد هش کلید را محاسبه کنید.
  2. شاخص سطل را محاسبه کنید.
  3. فهرست را مرور کنید و کلید عنصر اول را با مقدار موجود مقایسه کنید. اگر آنها برابر هستند، مقدار را برگردانید، در غیر این صورت عنصر بعدی را در صورت وجود بررسی کنید.
  4. اگر شی Node بعدی null است، null را برگردانید.
  5. اگر شی Node بعدی null نیست، به آن بروید و سه مرحله اول را تکرار کنید تا عنصر پیدا شود یا شی Node بعدی null شود.
با استفاده از روش، get()مقدار کلید "KING" را دریافت می کنیم: 
map.get("KING");
در داخل، متد فراخوانی می شود getNode(int hash, Object key)که خود کلید ("KING") و هش آن (2306996) به آن منتقل می شود که به همان روشی که در طول عملیات از قبل محاسبه می شود put().

  1. بررسی می کنیم:

    1. آیا حتی جدول هش وجود دارد:(tab = table) != null

      اجازه دهید به شما یادآوری کنم که هنگام ایجاد HashMap، آرایه‌ای برای یک جدول در سازنده ایجاد نمی‌شود؛ این اتفاق بعداً در متد رخ می‌دهد resize()که همیشه هنگام افزودن اولین عنصر به جدول هش فراخوانی می‌شود. بنابراین، اگر هیچ عنصری به HashMap اضافه نشده باشد، به سادگی هیچ آرایه داخلی برای ذخیره عناصر وجود ندارد.

    2. اگر عبارت قبلی true را برگرداند، باید مطمئن شوید که طول آرایه داخلی بزرگتر از 0 باشد:(n = tab.length) > 0;

    3. اگر عبارت قبلی نیز true را برگرداند، به سطل در شاخص (در مورد ما 4) که قبلاً محاسبه شده بود بروید و آن را برای وجود عناصر بررسی کنید:

      (first = tab[(n - 1) & hash]) != null)

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

      if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))

      از آنجایی که در مورد ما، کلید "KING" قبل از کلید "BLAKE" قرار می گیرد (در یک لیست پیوندی، عناصر جدید به انتها اضافه می شوند و KING ابتدا اضافه شده است)، در این نقطه توقف کرده و اولین شیء را برمی گردانیم. Node را در متد get() تایپ کنید، که فیلدی با مقدار (100) از او می گیرد:

      return (e = getNode(hash(key), key)) == null ? null : e.value;

  2. اگر بیش از یک عنصر در داخل سطل وجود داشته باشد، پس:

    1. اگر سطل یک لیست پیوندی است، لیست را از طریق هر یک از عناصر موجود در یک حلقه مرور می کنیم do – whileتا زمانی که مطابقت پیدا شود:

      do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);

    2. اگر سطل یک ساختار درختی باشد، متد به‌علاوه نامیده می‌شود getTreeNode()، که به نوبه خود از متد برای یافتن کلید مورد نیاز استفاده می‌کند find(). ما یک جستجوی درختی انجام می دهیم - هش ها مقایسه می شوند و گره ریشه چپ یا راست برای جستجو تعیین می شود. اگر کلیدها برابر هستند (با مرجع یا با equals)، این گره را برگردانید. اگر گره های فرزند چپ یا راست تهی باشند، علاوه بر این، کلیدها را با استفاده از compareTo مقایسه می کنیم (اگر کلیدها رابط را اجرا می کنند Comparable)، در غیر این صورت یک جستجوی بازگشتی از طریق درخت (درخت فرعی راست یا چپ) انجام می دهیم تا زمانی که مطابقت پیدا شود.

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

  • به سطل مورد نظر بروید (باز هم از قبل محاسبه شده است).

  • اگر فقط یک شی در سطل وجود داشته باشد (نشانگر تهی آن را بررسی می کنیم) هش ها، پیوندها و equals(اگر ناگهان هش ها برابر نیستند) مقایسه می کنیم. مسابقه پیدا کردی؟ عالی است، این کلید ما است - آن را حذف کنید (=null) و مقدار این کلید را برگردانید.

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

  • اگر عنصر پیدا نشد، null را برمی‌گردانیم.

در وضعیت درخت، اجرای نسبتاً پیچیده ای وجود دارد که بهتر است در مورد آن ندانید و به آرامی بخوابید (توضیح روش حتی می گوید که پیاده سازی پیچیده تر از یک عملیات حذف معمولی در قرمز-سیاه است. درخت). علاوه بر این، هنگامی که حذف می شود، تعداد گره ها در یک سطل می تواند به 6 بازگردد و سپس درخت دوباره به یک لیست پیوندی ساخته می شود. اگر توسعه دهنده ای با سال ها تجربه نیستید، دانستن و درک این موضوع اصلاً ضروری نیست (و به سادگی ضروری نیست).
نظرات
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION