HashMap کلاس کا تفصیلی تجزیہ

کلاس کی تفصیلی بحث پر جانے سے پہلے، آئیے ہیش ٹیبلز سے وابستہ بنیادی تصورات پر توجہ مرکوز کریں۔ یہ مضمون ہیش میپنگ کے ساتھ کام کرنے کے طریقوں پر بحث نہیں کرے گا۔ صرف داخل کرنے، تلاش کرنے اور حذف کرنے کی کارروائیوں پر واضح اور تفصیل سے بات کی جائے گی۔ میرے خیال میں اسی Schildt سے HashMap کے لیے دستیاب طریقوں کی تفصیل پڑھنا مشکل نہیں ہوگا۔ شاید مستقبل میں میں اس طرح کے طریقوں کے لئے وقف ایک اور مضمون لکھوں گا، لیکن فی الحال یہ شک میں ہے. Java 7 کے مقابلے میں، Java 8 میں HashMap کلاس میں اہم تبدیلیاں آئی ہیں (+1000 لائنز کوڈ)۔ آپ جاوا 7 میں نفاذ کے بارے میں یہاں پڑھ سکتے ہیں (لیکن اب متعلقہ نہیں): habr A ہیش ٹیبل ایک ڈیٹا ڈھانچہ ہے جو ایسوسی ایٹیو ارے انٹرفیس (خلاصہ کلیدی قدر ماڈل یا اندراج) کو نافذ کرتا ہے، جو بہت تیزی سے اندراج اور تلاش فراہم کرتا ہے: قطع نظر نمبر کے عناصر کا اندراج اور تلاش (اور بعض اوقات حذف کرنا) ایک مستقل - O(1) کے قریب وقت میں انجام دیا جاتا ہے۔ بنیادی طور پر، یہ ایک باقاعدہ صف ہے، جہاں عنصر کا مقام خود عنصر کی قدر پر منحصر ہوتا ہے۔ ہیش ٹیبل میں کسی عنصر کی قدر اور اس کی پوزیشن کے درمیان تعلق ہیش فنکشن کے ذریعے بیان کیا جاتا ہے۔ ایک ہیش فنکشن ڈیٹا کا ایک ان پٹ ٹکڑا لیتا ہے، جسے ہم کلید کہتے ہیں ، اور آؤٹ پٹ کے طور پر یہ ایک عدد عدد پیدا کرتا ہے جسے ہیش ویلیو (یا ہیش کوڈ) کہا جاتا ہے ۔ پھر ہیش ویلیو ہماری کلید کو ایک مخصوص ہیش ٹیبل انڈیکس سے منسلک کرتی ہے۔ بنیادی کارروائیوں کے لیے: داخل کرنا، تلاش کرنا اور حذف کرنا، ہم ایک ہی ہیش فنکشن کا استعمال کرتے ہیں، اس لیے یہ آپریشن کافی تیزی سے انجام پاتے ہیں۔ اس وجہ سے، یہ ضروری ہے کہ ہیش فنکشن مستقل طور پر برتاؤ کرے اور اسی ان پٹ ڈیٹا کے لیے ایک ہی انڈیکس کو آؤٹ پٹ کرے۔ یہ قابل غور ہے کہ نتیجے میں ہیش کوڈ ایک بہت بڑی عددی قدر ہو سکتی ہے، اور اصل صف مشروط طور پر صرف 16 عناصر کے لیے ڈیزائن کی گئی ہے۔ صرف دس کو شامل کرنے کے لیے ایک ارب عناصر کے ساتھ ایک صف کیوں نہیں بنائی جاتی؟ لہذا، ہمیں کسی نہ کسی طرح اس ہیش کوڈ کو 0 سے 15 تک اقدار میں تبدیل کرنا ہوگا (اگر سرنی کا سائز 16 ہے)۔ اور اس کے لیے اضافی تبدیلیاں استعمال کی جاتی ہیں۔ لہذا ہم صف کے سائز کو کم سے کم کرنے کے لیے ایک انڈیکس تیار کرتے ہیں۔ مثال کے طور پر، جاوا 8 سے پہلے HashMap میں، یہ اضافی طریقہ مطلوبہ سیل کو تلاش کرنے کے لیے استعمال کیا جاتا تھا:

static int indexFor(int h, int length) {
        return h & (length-1);
}

ان پٹ کے طور پر، اس نے کام کے نتیجے میں حاصل کردہ ہیش کوڈ hashCode()اور اندرونی صف کی لمبائی (خلیوں کی تعداد) لی۔ اور اس نے نتیجہ "ہیش کوڈ" -> bitwise "AND" -> (سرنی کی لمبائی - 1) کو واپس کیا۔ کلاس HashMapکلاس سے وراثت میں ملتی ہے AbstractMapاور درج ذیل انٹرفیس کو لاگو کرتی ہے: Map, Cloneable, Serializable. .میتھڈ جاوا میں ہیش فنکشن کے لیے ذمہ دار ہے hashCode()۔ پہلے سے طے شدہ نفاذ hashCode()ایک قدر لوٹاتا ہے جسے شناخت ہیش کوڈ کہتے ہیں ۔ یہاں تک کہ اگر ایک کلاس کو اوور رائیڈ کرتا ہے hashCode()، آپ ہمیشہ کال کرکے آبجیکٹ کی ID ہیش حاصل کرسکتے ہیں System.identityHashCode(Object o)۔ OpenJDK میں پہلے سے طے شدہ نفاذ کا hashCode()میموری ایڈریس سے کوئی تعلق نہیں ہے، جیسا کہ بعض اوقات خیال کیا جاتا ہے۔ مزید تفصیلات یہاں: habr HashMap میں ، ہیش ٹیبل کو اکیلے منسلک فہرستوں کی ایک صف (یا، زیادہ واضح طور پر، متحرک، چونکہ جدول پھیل سکتا ہے) کی بنیاد پر لاگو کیا جاتا ہے۔ بنیادی طور پر، ہم طریقہ کے نتیجے میں کلید کا ہیش کوڈ حاصل کرتے ہیں hashCode()، جس میں پھر ترمیم کی جاتی ہے (جیسا کہ ہم بعد میں غور کریں گے)، اور اندرونی طور پر، ایک اضافی طریقہ استعمال کرتے ہوئے، نتیجے میں آنے والی اقدار کو مطلوبہ خلیات میں تقسیم کیا جاتا ہے۔ سرنی عناصر (خلیات) کو بالٹی بھی کہا جاتا ہے ، جو انفرادی نوڈس کو ذخیرہ کرنے کے لیے استعمال ہوتے ہیں۔ ہر بالٹی ایک مجموعہ ہے (فہرست یا درخت)۔ نوڈ نیسٹڈ کلاس Node(یا TreeNodeدرخت کے ڈھانچے میں) کی ایک چیز ہے۔ درحقیقت، ارے سیل کے اندر LinkedListصرف ایک اکیلے جڑی ہوئی فہرست ہے، یا ایک سرخ سیاہ درخت ہے، جو کہ کسی اور طبقے کے نفاذ کو زیر کرتا ہے - TreeMap۔ سرخ سیاہ درخت والا آپشن اتنی کثرت سے پیدا نہیں ہوتا ہے (کیسے، کیا اور کہاں - نیچے)، اور اس ساخت کو سمجھنا کافی مشکل ہے، اس لیے نوڈ قسم کے نوڈ پر زور دیا جائے گا۔ نوڈ ایک نیسٹڈ کلاس ہے HashMapجس کے اندر درج ذیل فیلڈز ہیں:

• final int hash- موجودہ عنصر کی ہیش، جسے ہم کلید کو ہیش کرنے کے نتیجے میں حاصل کرتے ہیں۔
• final K key- موجودہ عنصر کی کلید۔ یہ وہ جگہ ہے جہاں آپ طریقہ کار میں پہلی چیز کے طور پر بیان کرتے ہیں put()؛
• V value- موجودہ عنصر کی قدر۔ اور جس چیز کو آپ طریقہ میں دوسری چیز کے طور پر بیان کرتے ہیں وہ یہاں لکھا گیا ہے put()۔
• Node < K, V> next- اسی ٹوکری کے اندر اگلے نوڈ سے لنک کریں۔ فہرست جڑی ہوئی ہے، اس لیے اسے اگلے نوڈ کے لیے لنک کی ضرورت نہیں، اگر کوئی ہے تو۔

اب آئیے ہیش میپ کلاس کے فیلڈز کو دیکھیں:

• transient Node < K, V> [] table- ہیش ٹیبل خود، ایک صف کی بنیاد پر لاگو کیا جاتا ہے، نوڈس کی شکل میں کلیدی قدر کے جوڑوں کو ذخیرہ کرنے کے لیے۔ یہ وہ جگہ ہے جہاں ہمارے نوڈس محفوظ ہوتے ہیں۔
• transient int size- کلیدی قدر کے جوڑوں کی تعداد؛
• int threshold- عناصر کی زیادہ سے زیادہ تعداد، جس تک پہنچنے پر ہیش ٹیبل کا سائز دوگنا ہو جاتا ہے۔ فارمولہ کا استعمال کرتے ہوئے شمار کیا جاتا ہے (صلاحیت * لوڈ فیکٹر)؛
• final float loadFactor— یہ پیرامیٹر اس بات کا تعین کرتا ہے کہ موجودہ ہیش ٹیبل کو ایک نئی ہیش ٹیبل بنانے کے لیے کس حد تک لوڈ کی ضرورت ہے، یعنی جیسے ہی ہیش ٹیبل 75% بھر جائے گا، ایک نیا ہیش ٹیبل بنایا جائے گا اور موجودہ عناصر کو اس میں منتقل کر دیا جائے گا (ایک مہنگا آپریشن، کیونکہ تمام عناصر کو دوبارہ ہیش کرنا ہوگا)؛
• transient Set< Map.Entry< K,V>> entrySet- ایک کیشڈ پر مشتمل ہے entrySet()، جس کے ساتھ ہم اعادہ کر سکتے ہیں HashMap۔

اور مستقل:

• 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کلاس کو بڑھاتی ہے ۔ ایک ہیش نقشہ اس کے عناصر کی ترتیب کی ضمانت نہیں دیتا۔ لہٰذا، جس ترتیب میں عناصر کو ہیش میپ میں داخل کیا جاتا ہے ضروری نہیں کہ وہ ترتیب ہو جس میں انہیں تکرار کرنے والے کے ذریعے بازیافت کیا جاتا ہے۔ آبجیکٹ شامل کرنا کلیدی قدر کے جوڑے کو شامل کرنا کا استعمال کرتے ہوئے کیا جاتا ہے ۔ آئیے کسی چیز کو شامل کرتے وقت شامل اقدامات کو دیکھیں: AbstractMapput()

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. چونکہ چیک کے نتیجے میں ہم درست ہوجاتے ہیں (بالٹی میں کوئی عنصر نہیں ہیں)، درج ذیل فیلڈز کے ساتھ ایک نوڈ آبجیکٹ تیار کیا جائے گا:

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      ہمارے تیار کردہ نوڈ آبجیکٹ کو انڈیکس [4] کے تحت بالٹی میں شامل کیا جائے گا:

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

      newNode()ایک ایسا طریقہ ہے جو نوڈ کلاس کی کسی چیز کو آسانی سے لوٹاتا ہے۔

   7. شامل کرنے کے بعد، یہ دیکھنے کے لیے چیک کیا جائے گا کہ آیا عناصر کی موجودہ تعداد پیرامیٹر سے زیادہ ہے threshold:

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

      اگر حد سے بڑھ جائے تو resize()ہیش ٹیبل کا سائز بڑھانے کے لیے ایک طریقہ کہا جائے گا۔

      اس مقام پر، طریقہ putVal()(اور بالترتیب put()) اپنا کام مکمل کر لے گا۔

      نتیجہ کو گرافک طور پر اس طرح پیش کیا جا سکتا ہے:

      عام طور پر، ہیش ٹیبل میں نوڈ (کلیدی قدر کا جوڑا) شامل کرنے سے ایسا لگتا ہے کہ مطلوبہ بالٹی خالی ہے ۔ اب آئیے ایک ایسا عنصر شامل کرنے کی کوشش کریں جو تصادم کا باعث بنے (جب ایک بالٹی میں ایک سے زیادہ عنصر ہوں)۔

تصادم کے بارے میں تھوڑا سا وہ صورتحال جب مختلف کیز ایک ہی بالٹی میں ختم ہو جائیں (مختلف ہیشوں کے ساتھ بھی) اسے ٹکراؤ یا تصادم کہا جاتا ہے۔ یہاں تک کہ اگر ہیش ٹیبل ڈیٹا سیٹ سے بڑا ہے اور ایک اچھا ہیش فنکشن منتخب کیا گیا ہے، یہ اس بات کی ضمانت نہیں دیتا کہ تصادم نہیں ہوگا۔ اور ہیش ویلیو انٹ ویلیوز (تقریباً 4 بلین) کی حد تک محدود ہے۔ نتیجے میں آنے والی نئی قدر کو بھی کہیں لکھنے کی ضرورت ہے، اور اس کے لیے آپ کو یہ تعین کرنا ہوگا کہ یہ کہاں لکھا جائے گا۔ اسے تنازعات کا حل کہا جاتا ہے۔ دو طریقے ہیں:

• بیرونی زنجیر یا زنجیر لگانے کا طریقہ (ہیش میپ میں نافذ) - یعنی سیل اصل میں ایک فہرست (زنجیر) پر مشتمل ہے۔ اور فہرست میں پہلے سے ہی کئی اقدار شامل ہوسکتی ہیں (ضروری نہیں کہ ایک ہی ہیش کوڈ کے ساتھ)۔
• لکیری پروبنگ یا اوپن ایڈریسنگ کا طریقہ (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 графически выглядит так:

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

   • проверяем с помощью методов 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)

      آپ واضح طور پر دیکھ سکتے ہیں کہ ایک سرخ سیاہ درخت کیسے بنایا گیا ہے اور یہاں خود توازن قائم کیا گیا ہے: تصور

اصولی طور پر، بس اتنا ہی ہے، اور ایک مثال کا استعمال کرتے ہوئے، فرض کرتے ہیں کہ ہم مندرجہ ذیل ناموں کو کیز کے طور پر شامل کرنا چاہتے ہیں: کنگ، میری، جوس، اینا، فریڈ، ٹونی، ایلکس، پیپ۔ اور ہم کہتے ہیں کہ ہمارے پاس ہیش ٹیبل میں کم از کم 64 بالٹیاں ہیں، اور یہ تمام عناصر ایک بالٹی میں جمع ہو گئے ہیں۔ ساختی طور پر، یہ بالٹی اس طرح نظر آئے گی (عناصر کو ہیش کوڈ کے ذریعے ترتیب دیا گیا ہے): CCHD کی قسم: بالٹی کے اندر دیکھیں: عناصر کو بازیافت کرنا (کلید کے ذریعہ قدر کی بازیافت) شامل کرنے کے عمل کے بارے میں ، یہ بہت آسان ہے۔ الگورتھم (جب بالٹی میں ایک منسلک فہرست موجود ہے) اس طرح لکھا جا سکتا ہے:

1. کلید کے ہیش کوڈ کا حساب لگائیں۔
2. بالٹی انڈیکس کا حساب لگائیں۔
3. انڈیکس کے ذریعے جائیں اور پہلے عنصر کی کلید کا موجودہ قدر سے موازنہ کریں۔ اگر وہ برابر ہیں تو، قدر واپس کریں، بصورت دیگر اگلے عنصر کی جانچ کریں، اگر یہ موجود ہے۔
4. اگر اگلا نوڈ آبجیکٹ null ہے تو null واپس کریں۔
5. اگر اگلا نوڈ آبجیکٹ null نہیں ہے تو اس پر جائیں اور پہلے تین مراحل کو اس وقت تک دہرائیں جب تک کہ عنصر نہ مل جائے یا اگلا Node آبجیکٹ null نہ ہو جائے۔

طریقہ استعمال کرتے ہوئے، get()ہم "KING" کلید کی قدر حاصل کرتے ہیں:

map.get("KING");

اندر، طریقہ کو کہا جاتا ہے getNode(int hash, Object key)، جس میں خود کلید ("KING") اور اس کا ہیش (2306996) گزر جاتا ہے، جس کا پہلے سے حساب اسی طرح کیا جاتا ہے جیسا کہ آپریشن کے دوران ہوتا ہے put()۔

1. ہم چیک کرتے ہیں:

   1. کیا ایک ہیش ٹیبل بھی موجود ہے:(tab = table) != null

      میں آپ کو یاد دلاتا ہوں کہ ہیش میپ بناتے وقت، کنسٹرکٹر میں ٹیبل کے لیے کوئی صف نہیں بنائی جاتی؛ یہ طریقہ بعد میں ہوتا ہے resize()، جسے ہمیشہ ہیش ٹیبل میں پہلا عنصر شامل کرتے وقت کہا جاتا ہے۔ لہذا، اگر HashMap میں کوئی عناصر شامل نہیں کیے گئے ہیں، تو عناصر کو ذخیرہ کرنے کے لیے کوئی اندرونی صف نہیں ہے۔

   2. اگر پچھلا اظہار درست ہوجاتا ہے، تو آپ کو یہ یقینی بنانا ہوگا کہ اندرونی صف کی لمبائی 0 سے زیادہ ہے:(n = tab.length) > 0;

   3. اگر پچھلا اظہار بھی درست ہو جاتا ہے تو، انڈیکس میں بالٹی پر جائیں (ہمارے کیس 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" سے پہلے آئے گی (ایک منسلک فہرست کے اندر، آخر میں نئے عناصر شامل کیے جاتے ہیں، اور کنگ کو پہلے شامل کیا گیا تھا)، ہم اس مقام پر رکیں گے اور کا پہلا اعتراض واپس کریں گے۔ نوڈ کو 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 پر واپس آ سکتی ہے، اور پھر درخت کو دوبارہ منسلک فہرست میں دوبارہ بنایا جائے گا۔ اگر آپ کئی سالوں کا تجربہ رکھنے والے ڈویلپر نہیں ہیں، تو یہ جاننا اور سمجھنا بالکل ضروری نہیں ہے (اور صرف ضروری نہیں)۔