HashMap сыныбының егжей-тегжейлі талдауы

Классты егжей-тегжейлі талқылауға көшпес бұрын, хэш кестелерімен байланысты негізгі түсініктерге тоқталайық. Бұл мақалада хэш картасымен жұмыс істеу әдістері талқыланбайды. Тек енгізу, іздеу және жою операциялары нақты және егжей-тегжейлі талқыланады. Сол Шилдттен HashMap үшін қол жетімді әдістердің сипаттамасын оқу қиын болмайды деп ойлаймын. Мүмкін болашақта мен осындай әдістерге арналған тағы бір мақала жазамын, бірақ әзірге бұл күмәнді. Java 7-мен салыстырғанда, Java 8-дегі HashMap сыныбы айтарлықтай өзгерістерге ұшырады (+1000 code жолы). Java 7 жүйесінде іске асыру туралы мына жерден оқи аласыз (бірақ енді өзекті емес): habr хэш кестесі – бұл өте жылдам кірістіру мен іздеуді қамтамасыз ететін ассоциативті массив интерфейсін (дерексіз кілт-мән үлгісі немесе жазба) жүзеге асыратын деректер құрылымы : қарамастан сандар элементтерінің кірістіру және іздеу (кейде жою) тұрақтыға жақын уақытта орындалады - O(1). Негізінде, бұл элементтің орны элементтің мәніне байланысты болатын тұрақты массив. Элемент мәні мен оның хэш кестесіндегі орны арасындағы қатынас хэш функциясы арқылы анықталады. Хэш функциясы деректердің кіріс бөлігін қабылдайды, оны біз кілт деп атаймыз және шығыс ретінде ол хэш мәні (немесе хэш codeы) ретінде белгілі бүтін санды шығарады . Содан кейін хэш мәні біздің кілтімізді хэш кестесінің нақты индексіне байланыстырады. Негізгі операциялар үшін: кірістіру, іздеу және жою, біз бірдей хэш функциясын қолданамыз, сондықтан бұл операциялар өте жылдам орындалады. Осы себепті хэш функциясының дәйекті әрекет етуі және бірдей кіріс деректері үшін бірдей индексті шығаруы маңызды. Айта кету керек, алынған хэш-code үлкен сандық мән болуы мүмкін және бастапқы массив шартты түрде тек 16 элементке арналған. Неліктен он элементті қосу үшін миллиард элементтері бар массив жасамасқа? Сондықтан, біз бұл хэш-codeты 0-ден 15-ке дейінгі мәндерге түрлендіруіміз керек (егер массив өлшемі 16 болса). Және бұл үшін қосымша түрлендірулер қолданылады. Осылайша, массив өлшемін азайту үшін индексті жасаймыз. Мысалы, Java 8 нұсқасына дейін HashMap бағдарламасында қалаған ұяшықты табу үшін бұл қосымша әдіс пайдаланылды:

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

Кіріс ретінде ол жұмыс нәтижесінде алынған хэш-codeты hashCode()және ішкі массивтің ұзындығын (ұяшықтардың саны) алды. Және ол нәтижені қайтарды «хэш codeы» -> биттік «ЖӘНЕ» -> (массив ұзындығы – 1). Класс HashMapсыныптан мұра алады AbstractMapжәне келесі интерфейстерді жүзеге асырады: Map, Cloneable, Serializable. .әдісі Java тіліндегі хэш функциясына жауап береді hashCode(). Әдепкі іске асыру сәйкестендіру хэш codeыhashCode() деп аталатын мәнді қайтарады . Сынып қайта анықталса да , сіз әрқашан қоңырау шалу арқылы нысанның идентификатор хэшін ала аласыз . OpenJDK-дегі әдепкі енгізудің жад мекенжайына ешқандай қатысы жоқ, кейде сенетіндей. Толығырақ мына жерден: habr HashMap бағдарламасында хэш кестесі жеке байланыстырылған тізімдердің массивіне (немесе, дәлірек айтқанда, динамикалық, кесте кеңеюі мүмкін) негізделген. Негізінде, біз әдіс нәтижесінде кілттің хэш codeын аламыз , ол кейін өзгертіледі (кейінірек қарастырамыз) және ішкі қосымша әдісті қолдана отырып, алынған мәндер қажетті ұяшықтарға таратылады. Массив элементтері (ұяшықтар) жеке түйіндерді сақтау үшін қолданылатын шелек деп те аталады. Шелектердің әрқайсысы жинақ (тізім немесе ағаш). Түйін кірістірілген класстың (немесе ағаш құрылымындағы) нысаны болып табылады. Шындығында, массив ұяшығының ішінде басқа класстың жүзеге асуының негізінде жатқан жалғыз байланыстырылған тізім немесе қызыл-қара ағаш бар . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap Қызыл-қара ағашы бар опция жиі пайда болмайды (қалай, не және қайда - төменде) және бұл құрылымды түсіну өте қиын, сондықтан түйін түріндегі түйінге баса назар аударылады. Түйін -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 будут заполнены. Например, для 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. Одновременно вычисляем индекс бакета, куда будет помещен наш an object, и проверяем, а есть ли уже в нем элементы. Вычисляем:

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

      проверяем:

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

   6. Так How в результате проверки мы получим true (в бакете элементов нет), будет сгенерирован an object Node со следующими полями:

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

      Наш сформированный an object Node будет добавлен в бакет под индексом [4]:

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

      newNode() — это метод, который просто возвращает an object класса Node.

   7. После добавления будет произведена проверка не превышает ли текущее количество элементов параметр threshold:

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

      Если превышает, тогда будет вызван метод resize() для увеличения размера хеш-таблицы.

      На этом метод putVal() (соответственно и put()) завершит свою работу.

      Графически полученный результат изобразить можно так:

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

Соқтығыстар туралы аздап Әртүрлі кілттер бір шелекке (тіпті әртүрлі хэштермен) аяқталатын жағдай соқтығыс немесе соқтығыс деп аталады. Тіпті хэш кестесі деректер жиынынан үлкенірек болса және жақсы хэш функциясы таңдалған болса да, бұл соқтығыстардың болмайтынына кепілдік бермейді. Ал хэш мәні int мәндерінің ауқымымен шектеледі (шамамен 4 миллиард). Алынған жаңа мән де бір жерде жазылуы керек, ол үшін оның нақты қай жерде жазылатынын анықтау керек. Бұл қақтығысты шешу деп аталады. Екі тәсіл бар:

• сыртқы тізбектеу немесе тізбектеу әдісі (HashMap-те енгізілген) - яғни. ұяшықта шын мәнінде тізім (тізбек) бар. Және тізімде бірнеше мәндер болуы мүмкін (міндетті түрде бірдей хэш-codeпен емес).
• сызықтық зондтау немесе ашық addressтеу әдісі (IdentityHashMap бағдарламасында енгізілген) - хэш функциясымен көрсетілген ұяшықтан кейінгі бірінші бос ұяшықты іздеуден тұрады;

Соқтығыстар туралы мына жерден оқи аласыз: басыңыз

1. Әдісті пайдалана отырып, put()хэшті салыстыруға басқа кілт-мән жұбын қосамыз:

   map.put("BLAKE", 10);

2. Біз «алдын ала хэшті» есептейміз – 63281361. Біз оны өзгертеміз және нәтижесінде соңғы хэш codeын аламыз – 63281940.

3. «Бостығын» бірінші тексеру енді жалған мәнін қайтаратындықтан (кесте жасаудың қажеті жоқ), біз an objectіміз орналасатын шелек индексін дереу есептейміз:

   
   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)жалған мәнін қайтарса, онда қалған шарт еленбейді ( &&) өйткені нысандардың басқаша болуына кепілдік беріледі. Әйтпесе, кілттер сілтеме бойынша (==) салыстырылады және теңсіздік жағдайында кілттер әдісі арқылы салыстырылады equals(). Салыстырулар өнімділік үшін осы ретпен жасалады. Егер барлық үш өрнек шын мәнін қайтарса, бұл кілттердің тең екендігін және кейінірек кілт мәнін қайта жазу үшін жаңа элемент қосымша айнымалыға жазылатынын білдіреді:

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

   Кілттерді салыстыру нәтижесінде біз бірінші кезеңде жалған аламыз (әртүрлі хэштер).

6. Біз ( ) шартын елемейміз p instanceof TreeNode, өйткені бұл кезеңде шелектегі құрылым ағаш тәрізді емес.

7. Содан кейін біз циклге кіреміз for, онда бір шелек ішінде келесі элементке көрсеткіш үшін элементтерді тексереміз nextжәне егер ол нөл болса (бұл тізімдегі элемент соңғы және жалғыз екенін білдіреді), біз жаңа Түйін қосамыз. тізімнің соңына дейін элемент:

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

   Сіз сұрақ қоюыңыз мүмкін, негізгі теңдік тексеруі қайда? Біз жай ғана алға шығып, жаңа элемент қоса алмаймыз. Сондықтан ол (5) тармақта алдын ала орындалды. Осының арқасында біз осы элементтің көрсеткішін жай ғана тексере аламыз және ол қазір нөл болғандықтан, тізімде бір ғана элемент бар деп қорытынды жасауға болады. Біз олардың кілттерін тексеріп қойғандықтан, жаңа элементті қауіпсіз қоса аламыз.

   Егер бірінші итерация кезінде көрсеткіш нөл болмаса, бұл тізімде кемінде екі элемент бар екенін көрсетеді, сондықтан бұл жағдайда келесі шартқа көшеміз және қосылатын элементтің кілтін барлық пернелермен салыстырамыз. тізімдегі элементтер (бесінші абзацта сипатталған тәртіппен).

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

   Егер кілттерді салыстыру кезінде сәйкестік табылса, жаңа элемент қосымша айнымалыға жазылады, осылайша оны кейінірек кілттің мәнін қайта жазу үшін пайдалануға болады.

   Екінші элементті қосқаннан кейін, біздің HashMap нысаны графикалық түрде келесідей болады:

   Нәтижесінде, соқтығыс кезінде элементтерді қосу (бір шелек ішінде) келесідей болады:

   • Біз екі кілттің де бірдей екенін hashCode()және әдістерін қолданып тексереміз .equals()
   • пернелер бірдей болса, ағымдағы мәнді жаңасымен ауыстырыңыз.
   • әйтпесе, ағымдағы нысандағы келесі нысанға сілтемені көрсете отырып, «байланыстырылған тізім» деректер құрылымын пайдаланып жаңа және ескі нысандарды қосыңыз және екеуін де қажетті индекс астында сақтаңыз; немесе ағаш құрылымына ауысыңыз

8. Әрбір итерациядан кейін (жаңа элементті қосу) for циклі шелектегі элементтердің санына жауап беретін есептегішті арттырады:

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

   Олардың саны 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), біз ағаштың құрылысын тоқтатып, әдісті шақырамыз , ол өз кезегінде ғаламдық бірегей хэш codeын есептеу үшін 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 шелек бар және бұл элементтердің барлығы бір шелекке жиналды делік. Құрылымдық жағынан бұл шелек келесідей болады (элементтер хэш-code бойынша сұрыпталады): CCHD түрі: Шелек ішіндегі көрініс: Элементтерді шығарып алу (мәнді перне арқылы алу) Қосу операциясына қатысты бұл өте қарапайым. Алгоритмді (шелекте байланыстырылған тізім болған кезде) келесідей жазуға болады:

1. Кілттің хэш codeын есептеңіз.
2. Шелек индексін есептеңіз.
3. Индекс арқылы өтіп, бірінші элементтің кілтін бар мәнмен салыстырыңыз. Егер олар тең болса, мәнді қайтарыңыз, әйтпесе ол бар болса, келесі элементті тексеріңіз.
4. Келесі Түйін нысаны бос болса, нөлді қайтарыңыз.
5. Келесі Түйін нысаны бос емес болса, оған өтіп, элемент табылғанша немесе келесі Түйін нысаны бос болғанша алғашқы үш қадамды қайталаңыз.

Әдістің көмегімен 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))))

      Біздің жағдайда «KING» пернесі «BLAKE» пернесінен бұрын болатындықтан (байланысты тізімде жаңа элементтер соңына қосылады және алдымен KING қосылды), біз осы жерде тоқтап, бірінші нысанды қайтарамыз. Get() әдісіне Node теріңіз, ол одан (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), осы түйінді қайтарыңыз. Егер сол немесе оң жақ еншілес түйіндер нөл болса, біз салыстыру арқылы пернелерді қосымша салыстырамыз (егер пернелер интерфейсті орындаса Comparable), әйтпесе сәйкестік табылғанша ағаш (оң немесе сол ішкі ағаш) арқылы рекурсивті іздеуді орындаймыз.

HashMap-тен нысандарды жою Мақалада бос орын таусылғандықтан, кілт арқылы жоюдың қалай орындалатынын қысқаша сипаттаймын. Алгоритм өте ұқсас:

• қалаған шелекке барыңыз (қайтадан, ол алдын ала есептелген);

• шелекте бір ғана нысан болса (біз оның нөлдік көрсеткішін тексереміз) хэштерді, сілтемелерді және equals(егер кенеттен хэштер тең болмаса) салыстырамыз. Сәйкес таптыңыз ба? Керемет, бұл біздің кілтіміз - оны жойыңыз (=null) және осы кілттің мәнін қайтарыңыз.

• егер шелекте бірнеше элемент болса, біз элементті тапқанша немесе тізімнің соңына жеткенше циклдегі әрбір элементті тексереміз.

• егер элемент табылмаса, біз нөлді қайтарамыз.

Ағаш жағдайында өте күрделі іске асыру бар, ол туралы білмеу және тыныш ұйықтау жақсы (әдістің сипаттамасы тіпті қызыл-қара түсте қарапайым жою операциясына қарағанда жүзеге асыру күрделірек екенін айтады. ағаш). Сонымен қатар, жойылған кезде бір шелектегі түйіндер саны 6-ға оралуы мүмкін, содан кейін ағаш байланыстырылған тізімге қайта құрылады. Егер сіз көп жылдық тәжірибесі бар әзірлеуші ​​болмасаңыз, мұны білу және түсіну мүлдем қажет емес (және жай ғана қажет емес).