HashMap ڪلاس جو تفصيلي تجزيو

ڪلاس جي تفصيلي بحث تي هلڻ کان اڳ، اچو ته هيش ٽيبل سان لاڳاپيل بنيادي تصورن تي ڌيان ڏيون. هي مضمون هيش ميپنگ سان ڪم ڪرڻ جي طريقن تي بحث نه ڪندو. صرف داخل ڪرڻ، ڳولڻ ۽ حذف ڪرڻ جي عملن تي واضح ۽ تفصيل سان بحث ڪيو ويندو. مان سمجهان ٿو ته ساڳئي Schildt کان HashMap لاء دستياب طريقن جي وضاحت پڙهڻ ڏکيو نه ٿيندو. شايد مستقبل ۾ آئون هڪ ٻيو مضمون لکندس جيڪو اهڙن طريقن سان وقف آهي، پر هن وقت تائين اهو شڪ ۾ آهي. جاوا 7 جي مقابلي ۾، جاوا 8 ۾ HashMap ڪلاس ۾ اهم تبديليون آيون آهن (ڪوڊ جون +1000 لائينون). توهان هتي جاوا 7 ۾ عمل درآمد بابت پڙهي سگهو ٿا (پر هاڻي لاڳاپيل ناهي): habr A hash table هڪ ڊيٽا جو ڍانچو آهي جيڪو ايسوسيئيٽ ايري انٽرفيس کي لاڳو ڪري ٿو (خلاصي ڪي قدر ماڊل يا داخلا)، جيڪو مهيا ڪري ٿو تمام تيز داخل ۽ ڳولا: قطع نظر انگن جي عنصرن جي داخل ۽ ڳولها (۽ ڪڏهن ڪڏهن حذف ڪرڻ) هڪ وقت ۾ ڪيو ويندو آهي هڪ مستقل - O(1). لازمي طور تي، هي هڪ باقاعده صف آهي، جتي عنصر جو مقام خود عنصر جي قيمت تي منحصر آهي. هڪ عنصر جي قيمت ۽ هيش ٽيبل ۾ ان جي پوزيشن جي وچ ۾ تعلق هڪ هيش فنڪشن طرفان بيان ڪيو ويو آهي. هيش فنڪشن ڊيٽا جو هڪ ان پٽ پيس وٺي ٿو، جنهن کي اسين ڪيئي سڏين ٿا ، ۽ هڪ آئوٽ جي طور تي اهو هڪ انٽيجر پيدا ڪري ٿو جنهن کي hash value (يا hash code) طور سڃاتو وڃي ٿو . هيش ويليو وري اسان جي ڪنجي کي هڪ مخصوص هيش ٽيبل انڊيڪس سان ڳنڍي ٿو. بنيادي عملن لاءِ: داخل ڪرڻ، ڳولڻ ۽ حذف ڪرڻ، اسان ساڳيا هيش فنڪشن استعمال ڪندا آهيون، تنهن ڪري اهي آپريشن تمام جلدي ڪيا ويندا آهن. انهي سبب لاء، اهو ضروري آهي ته هيش فنڪشن مسلسل عمل ڪري ٿو ۽ ساڳئي ان پٽ ڊيٽا لاء ساڳيو انڊيڪس ڪڍي ٿو. اهو قابل ذڪر آهي ته نتيجو هيش ڪوڊ هڪ وڏي عددي قيمت ٿي سگهي ٿي، ۽ اصل صف مشروط طور تي صرف 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. .method جاوا ۾ هيش فنڪشن لاءِ ذميوار آهي hashCode(). ڊفالٽ عمل درآمد hashCode()هڪ قدر واپس ڪري ٿو جنهن کي شناخت هيش ڪوڊ سڏيو ويندو آهي . جيتوڻيڪ جيڪڏهن ڪو ڪلاس اوور رائيڊ ڪري ٿو hashCode()، توهان هميشه حاصل ڪري سگهو ٿا اعتراض جي ID هيش ڪال ڪندي System.identityHashCode(Object o). OpenJDK ۾ ڊفالٽ عملدرآمد جو hashCode()ميموري ايڊريس سان ڪو به واسطو نه آهي، جيئن ڪڏهن ڪڏهن مڃيو ويندو آهي. وڌيڪ تفصيل هتي: habr HashMap ۾ ، هيش ٽيبل تي عمل ڪيو ويندو آهي هڪ صف جي بنياد تي (يا، وڌيڪ واضح طور تي، متحرڪ، ڇاڪاڻ ته جدول کي وڌايو وڃي ٿو) اڪيلو ڳنڍيل فهرستن جي. لازمي طور تي، اسان حاصل ڪريون ٿا چاٻي جو هيش ڪوڊ طريقي جي نتيجي ۾ hashCode()، جيڪو پوء تبديل ڪيو ويو آهي (جيئن اسان بعد ۾ غور ڪنداسين)، ۽ اندروني طور تي، هڪ اضافي طريقو استعمال ڪندي، نتيجن جي قيمتن کي گهربل سيلز ۾ ورهايو ويو آهي. Array عنصرن (سيلز) کي بالٽ پڻ سڏيو ويندو آهي ، جيڪي انفرادي نوڊس کي ذخيرو ڪرڻ لاءِ استعمال ٿيندا آهن. هر بالٽ هڪ مجموعو آهي (فهرست يا وڻ). هڪ نوڊ هڪ نيسٽ ٿيل طبقي جو هڪ اعتراض آهي Node(يا TreeNodeوڻ جي جوڙجڪ ۾). حقيقت ۾، صف جي سيل جي اندر LinkedListصرف هڪ واحد ڳنڍيل فهرست آهي، يا هڪ ڳاڙهي-ڪارو وڻ، جيڪو ڪنهن ٻئي طبقي جي عمل کي هيٺ رکي ٿو - TreeMap. ڳاڙهي-ڪارو وڻ سان اختيار گهڻو ڪري نه ٿو پيدا ٿئي (ڪيئن، ڇا ۽ ڪٿي - هيٺان)، ۽ هن جوڙجڪ کي سمجهڻ ڏاڍو ڏکيو آهي، تنهنڪري زور نوڊ قسم جي نوڊ تي هوندو. Node ھڪڙو نسٽڊ ڪلاس آھي HashMapجنھن ۾ ھيٺيون فيلڊون آھن:

• 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- عنصرن جو وڌ ۾ وڌ تعداد، جنھن تي پھچڻ تي ھيش ٽيبل جي سائيز ٻيڻي ٿي وڃي ٿي. فارمولا استعمال ڪندي حساب ڪيو ويو (ظرفيت * لوڊ فيڪٽر)؛
• 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۽ ھڪڙي طبقي کي وڌائي ٿو 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' جا هيٺيان بٽ ڀريا ويا آهن. مثال طور، for Integer, Float- جيڪڏهن اسان HashMap ۾ ننڍيون قيمتون رکون ٿا، ته پوءِ صرف هيٺيون قيمتون انهن جي هيش ڪوڊ بٽس ۾ ڀريون وينديون. انهي صورت ۾، HashMap ۾ چابيون هيٺين سيلز ۾ جمع ٿيڻ جي ڪوشش ڪندا، جڏهن ته مٿيون خالي هونديون، جيڪي تمام ڪارائتو نه آهن. صرف هيش جا گهٽ ۾ گهٽ اهم بٽ متاثر ڪن ٿا ته ڪهڙي بالٽ ۾ نئين داخلا داخل ٿيندي. اهو ئي سبب آهي ته اسان هيش جي اعلي بِٽس کي هيٺين بِٽس ۾ ملائڻ لاءِ مختلف ڌانڌليون ڪيون آهن ته جيئن بڪٽس ۾ ورهائڻ کي بهتر بڻائي سگهجي (ته جيئن اعتراض جي اصلي هيش جا اعليٰ بِٽ ترتيب ڏيڻ شروع ڪن ته ڪهڙي بالٽ ۾ اعتراض ختم ٿي ويندو. up in) ۽، نتيجي طور، ڪارڪردگي. اهو ڇو ته hashHashMap اندر هڪ اضافي فنڪشن ايجاد ڪيو ويو.

2. اسان حساب ڪريون ٿا انڊيڪس جي انڊيڪس بالٽ (سري سيل) جنهن ۾ اسان جو عنصر شامل ڪيو ويندو:

   
   i = (n - 1) & hash

   جتي n صف جي ڊگھائي آھي.

3. ھڪڙو نوڊ اعتراض ٺاھيو ويو آھي.

4. هاڻي، صف ۾ انڊيڪس کي ڄاڻڻ سان، اسان هن سيل سان لاڳاپيل عناصر جي هڪ فهرست (زنجيرن) حاصل ڪندا آهيون. جيڪڏهن بالٽ خالي آهي، ته اسان صرف ان ۾ عنصر رکون ٿا. ٻي صورت ۾، نئين عنصر جي هيش ۽ ڪيئي متبادل طور تي فهرست مان عناصر جي هيش ۽ ڪنجين سان مقابلي ۾ آهن، ۽ جيڪڏهن اهي پيرا ميٽر ملن ٿا، عنصر جي قيمت ختم ٿي ويندي آهي. جيڪڏهن ڪو ميلاپ نه ملي، عنصر فهرست جي آخر ۾ شامل ڪيو ويندو.

   هاڻي هڪ تمام تفصيلي مثال ڏانهن.

   1. اچو ته HashMap ڪلاس جو هڪ اعتراض ٺاهيو:

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

   2. طريقي کي استعمال ڪندي، put()اسان پهريون اهم-قدر جوڙو شامل ڪيو هيش نقشي ۾:

      map.put("KING", 100);

      هن وقت، طريقي کي اندروني طور سڏيو ويندو آهي putVal().

   3. هيش فنڪشن استعمال ڪندي، جنهن جو ڪردار ادا ڪيو ويندو آهي هيش طريقي سان، ڪيچ جو هيش ڪوڊ ڳڻيو ويندو آهي ، جنهن جي اندر هيش ڪوڊ ابتدائي طور تي استعمال ڪيو ويندو آهي hashCode() طريقي سان (هن صورت ۾ String ڪلاس)، جيئن جنهن جي نتيجي ۾ اسان ان جي "ابتدائي قيمت" حاصل ڪندا آهيون - 2306967 . IDEA استعمال ڪندي چيڪ ڪري سگهو ٿا

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

      نتيجو هيش ڪوڊ فارمولا استعمال ڪندي تبديل ڪيو ويو آهي: (хеш-code) ^ (хеш-code>>> 16), ۽ نتيجي طور اسان حاصل ڪيو فائنل هيش ڪوڊ - 2306996 .

   4. اسان "خالي" لاء ٽيبل چيڪ ڪريو:

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

      [] tabهيش ٽيبل پاڻ ڪٿي آهي: اسان ٽيب ۽ ٽيبل جو حوالو ڏيون ٿا (مون کي توهان کي ياد ڏيارڻ ڏيو ته هي هيش ميپ ڪلاس جو هڪ فيلڊ آهي جيڪو اسان جي عناصرن لاءِ هڪ سري کي محفوظ ڪري ٿو) ساڳئي صف ڏانهن، ۽ int n هڪ اضافي انسداد متغير آهي .

      جيئن ته چيڪ سچو موٽندو (ڇاڪاڻ ته ٽيبل لاءِ صف ٺاھيندڙ ۾ نئين آپريٽر استعمال ڪندي نه ٺاھي وئي)، طريقو سڏيو ويندو resize()، جيڪو اصل ۾ 16 عناصر جي جدول ٺاھيندو. ها، ها، ڪلاس تعمير ڪندڙ ڪا به ٽيبل نه ٺاهيندا آهن. ان جي بدران، طريقو هميشه سڏيو ويندو آهي resize()پهريون ڀيرو هڪ عنصر شامل ڪيو ويو آهي. ٺاهيل جدول جي ڊگھائي (صفن جي ڊگھائي تي غور ڪريو) variable ڏانهن لکيو ويندو 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. Бакет под указанным индексом проверяется на наличие в нем элементов и так How condition 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. چائلڊ نوڊ شامل ڪريو (کاٻي يا ساڄي تي منحصر ڪري ٿو):

      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. جيڪڏهن ايندڙ Node اعتراض null آهي، واپس null.
5. جيڪڏهن ايندڙ نوڊ اعتراض 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. جيڪڏهن اڳوڻو اظهار درست اچي ٿو، توهان کي پڪ ڪرڻ جي ضرورت آهي ته اندروني صف جي ڊيگهه 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))))

      جيئن ته اسان جي صورت ۾، اهم "ڪنگ" کي ​​"بليڪ" کان اڳ ٿيندو (هڪ ڳنڍيل لسٽ ۾، نوان عناصر آخر ۾ شامل ڪيا ويا آهن، ۽ ڪنگ پهريون شامل ڪيو ويو آهي)، اسان هن نقطي تي روڪينداسين ۽ پهريون اعتراض واپس ڪنداسين. ٽائپ ڪريو نوڊ کي 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)، هن نوڊ کي واپس ڏيو. جيڪڏهن کاٻي يا ساڄي چائلڊ نوڊس null آهن، اسان اضافي طور تي compareTo (جيڪڏهن ڪنجيون انٽرفيس کي لاڳو ڪن ٿيون) استعمال ڪندي ڪنجين جو مقابلو ڪريون ٿا Comparable، ٻي صورت ۾ اسان وڻ (ساڄي يا کاٻي سب ٽري) ذريعي ٻيهر ڳولهيندا آهيون جيستائين ميچ نه ملي.

HashMap مان شيون هٽائڻ جڏهن ته آرٽيڪل ۾ جاءِ ختم ٿي رهي آهي، مان مختصر طور تي بيان ڪندس ته ڪيئي ذريعي حذف ڪيئن ٿئي ٿي. الورورٿم بلڪل ساڳيو آهي:

• مطلوب بالٽ ڏانھن وڃو (ٻيهر، اھو اڳ ۾ حساب ٿيل آھي)؛

• جيڪڏهن بالٽ ۾ صرف هڪ اعتراض آهي (اسان ان جي نال پوائنٽر کي چيڪ ڪندا آهيون) اسان هيش، لنڪس ۽ equals(جيڪڏهن اوچتو هيش برابر نه آهن) جي مقابلي ۾. هڪ ميچ مليو؟ عظيم، هي اسان جي ڪيٻي آهي - ان کي حذف ڪريو (= null) ۽ واپس ڪريو هن ڪيئي جي قيمت.

• جيڪڏهن بالٽ ۾ هڪ کان وڌيڪ عنصر آهن، اسان هر عنصر کي لوپ ۾ چيڪ ڪندا آهيون جيستائين اسان عنصر کي ڳوليندا آهيون يا فهرست جي آخر تائين پهچي ويندا آهيون.

• جيڪڏهن عنصر نه مليو، اسان واپس null.

هڪ وڻ جي صورتحال ۾، اتي هڪ تمام مشڪل عمل آهي، جنهن جي باري ۾ نه ڄاڻڻ ۽ سٺي ننڊ ڪرڻ بهتر آهي (طريقي جي وضاحت پڻ ٻڌائي ٿي ته عملدرآمد هڪ ڳاڙهي-ڪاري ۾ باقاعده حذف ڪرڻ جي عمل کان وڌيڪ پيچيده آهي. وڻ). ان کان علاوه، جڏهن ڊاهي، هڪ بالٽ ۾ نوڊس جو تعداد 6 ڏانهن واپس اچي سگهي ٿو، ۽ پوء وڻ کي ٻيهر ڳنڍيل فهرست ۾ ٻيهر تعمير ڪيو ويندو. جيڪڏهن توهان ڪيترن ئي سالن جي تجربي سان ڊولپر نه آهيو، اهو ڄاڻڻ ۽ سمجهڻ ضروري ناهي (۽ صرف ضروري ناهي).