Analisi dettagliata della classe HashMap

Prima di passare a una discussione dettagliata della classe, concentriamoci sui concetti di base associati alle tabelle hash. Questo articolo non discuterà i metodi per lavorare con la mappatura hash. Verranno trattate in modo chiaro e dettagliato solo le operazioni di inserimento, ricerca e cancellazione. Penso che non sarà difficile leggere la descrizione dei metodi disponibili per HashMap da parte dello stesso Schildt. Forse in futuro scriverò un altro articolo dedicato a tali metodi, ma per ora questo è in discussione. Rispetto a Java 7, la classe HashMap in Java 8 ha subito notevoli modifiche (+1000 righe di codice). Puoi leggere l'implementazione in Java 7 qui (ma non più rilevante): habr Una tabella hash è una struttura dati che implementa l' interfaccia dell'array associativo (modello o voce di valore-chiave astratto), che fornisce inserimento e ricerca molto rapidi: indipendentemente degli elementi numerici l'inserimento e la ricerca (e talvolta la cancellazione) vengono eseguiti in un tempo prossimo ad una costante - O(1). Essenzialmente si tratta di un array regolare, in cui la posizione dell'elemento dipende dal valore dell'elemento stesso. La relazione tra il valore di un elemento e la sua posizione nella tabella hash è specificata da una funzione hash. Una funzione hash prende un dato in input, che chiamiamo chiave , e come output produce un numero intero noto come valore hash (o codice hash) . Il valore hash associa quindi la nostra chiave a uno specifico indice della tabella hash. Per le operazioni di base: inserimento, ricerca e cancellazione, utilizziamo la stessa funzione hash, quindi queste operazioni vengono eseguite abbastanza rapidamente. Per questo motivo è importante che la funzione hash si comporti in modo coerente e restituisca lo stesso indice per gli stessi dati di input. Vale la pena notare che il codice hash risultante può avere un valore numerico enorme e l'array originale è progettato in modo condizionale per soli 16 elementi. Perché non creare un array con un miliardo di elementi per aggiungerne solo dieci? Pertanto, dobbiamo in qualche modo trasformare questo codice hash in valori da 0 a 15 (se la dimensione dell'array è 16). E per questo vengono utilizzate ulteriori trasformazioni. Quindi generiamo un indice per ridurre al minimo la dimensione dell'array. Ad esempio, in HashMap prima di Java 8, questo metodo aggiuntivo veniva utilizzato per trovare la cella desiderata:

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

Come input ha preso il codice hash ottenuto come risultato del lavoro hashCode()e la lunghezza dell'array interno (numero di celle). E ha restituito il risultato "codice hash" -> "AND" bit per bit -> (lunghezza dell'array - 1). La classe HashMaperedita dalla classe AbstractMape implementa le seguenti interfacce: Map, Cloneable, Serializable. Il .method è responsabile della funzione hash in Java hashCode(). L'implementazione predefinita hashCode()restituisce un valore chiamato codice hash di identità . Anche se una classe sovrascrive hashCode(), puoi sempre ottenere l'hash ID dell'oggetto chiamando System.identityHashCode(Object o). L'implementazione predefinita hashCode()in OpenJDK non ha nulla a che fare con l'indirizzo di memoria, come talvolta si crede. Maggiori dettagli qui: habr In HashMap , la tabella hash è implementata sulla base di un array (o, più precisamente, dinamico, poiché la tabella può espandersi) di elenchi collegati singolarmente. In sostanza, come risultato del metodo otteniamo il codice hash della chiave hashCode(), che viene poi modificato (come vedremo in seguito), e internamente, utilizzando un metodo aggiuntivo, i valori risultanti vengono distribuiti alle celle richieste. Gli elementi dell'array (celle) sono anche chiamati bucket e vengono utilizzati per memorizzare i singoli nodi. Ciascuno dei bucket è una raccolta (elenco o albero). Un nodo è un oggetto di una classe nidificata Node(o TreeNodein una struttura ad albero). Infatti, all'interno della cella dell'array si trova LinkedListsolo una lista concatenata singolarmente, o un albero rosso-nero, che è alla base dell'implementazione di un'altra classe - TreeMap. L'opzione con un albero rosso-nero non si presenta così spesso (come, cosa e dove - sotto), e questa struttura è abbastanza difficile da capire, quindi l'enfasi sarà su un nodo del tipo Nodo. Node è una classe annidata HashMapal cui interno sono presenti i seguenti campi:

• final int hash— l'hash dell'elemento corrente, che otteniamo come risultato dell'hashing della chiave;
• final K key— la chiave dell'elemento corrente. Qui è dove viene scritto ciò che specifichi come primo oggetto nel metodo put();
• V value— il valore dell'elemento corrente. E ciò che specifichi come secondo oggetto nel metodo è scritto qui put();
• Node < K, V> next— collegamento al nodo successivo all'interno dello stesso paniere. L'elenco è connesso, quindi necessita di un collegamento non al nodo successivo, se presente.

Ora diamo un'occhiata ai campi della classe HashMap stessa:

• transient Node < K, V> [] table– la tabella hash stessa, implementata sulla base di un array, per memorizzare coppie chiave-valore sotto forma di nodi. Qui è dove sono archiviati i nostri Nodi;
• transient int size— numero di coppie chiave-valore;
• int threshold— il numero massimo di elementi, al raggiungimento del quale la dimensione della tabella hash raddoppia. Calcolato utilizzando la formula (capacità * loadFactor);
• final float loadFactor— questo parametro determina il livello di carico necessario alla tabella hash corrente per creare una nuova tabella hash, ovvero non appena la tabella hash sarà piena al 75%, verrà creata una nuova tabella hash e gli elementi correnti verranno spostati al suo interno (un'operazione costosa, poiché tutti gli elementi devono essere rielaborati);
• transient Set< Map.Entry< K,V>> entrySet- contiene un cached entrySet(), con il quale possiamo iterare HashMap.

E costanti:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— capacità della tabella hash predefinita (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— la capacità massima possibile della tabella hash (circa 1 miliardo);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— fattore di carico predefinito;
• static final int TREEIFY_THRESHOLD = 8è la “soglia” del numero di elementi in un bucket, al raggiungimento della quale la lista concatenata interna verrà convertita in una struttura ad albero (albero rosso-nero).
• static final int UNTREEIFY_THRESHOLD = 6— se il numero di elementi in un paniere diminuisce a 6, si verificherà una transizione inversa da un albero a un elenco concatenato;
• static final int MIN_TREEIFY_CAPACITY = 64— la capacità minima (numero di bucket) di una tabella hash alla quale è possibile la transizione a una struttura ad albero. Quelli. Se nella tabella hash sono presenti almeno 64 contenitori e in un contenitore sono presenti 8 o più elementi, si verificherà una transizione alla struttura ad albero.

Costruttori di classi:

1. public HashMap()— crea una visualizzazione hash per impostazione predefinita: per volume (capacity) = 16e con fattore di carico (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— crea una mappatura hash inizializzata dagli elementi di un'altra determinata mappatura con la capacità iniziale sufficiente ad accogliere gli elementi di un'altra mappatura;
3. public HashMap(int initialCapacity)— crea una mappa hash con una determinata capacità iniziale. Affinché HashMap funzioni correttamente e correttamente, la dimensione dell'array interno deve essere una potenza di due (ovvero 16, 64, 128, ecc.);
4. public HashMap(int initialCapacity, float loadFactor)— crea una mappa hash con i parametri specificati: capacità iniziale e fattore di carico.

Una classe implementa un'interfaccia Maped estende una classe AbstractMapsenza aggiungere i propri metodi. Una mappa hash non garantisce l'ordine dei suoi elementi. Pertanto, l'ordine in cui gli elementi vengono immessi nella mappa hash non è necessariamente l'ordine in cui vengono recuperati dall'iteratore. Aggiunta di oggetti L'aggiunta di una coppia chiave-valore viene eseguita utilizzando il metodo put(). Diamo un'occhiata ai passaggi necessari quando si aggiunge un oggetto:

1. Viene calcolato il valore hash della chiave dell'oggetto inserito. L'hash della chiave viene calcolato con un metodo static final int hash(Object key)che accede già al hashCode()metodo della chiave che conosciamo. hashCode()Per fare ciò, viene utilizzato un metodo sovrascritto o la sua implementazione predefinita. Ulteriori trasformazioni nel metodo 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. Allo stesso tempo, calcoliamo l'indice del bucket in cui verrà posizionato il nostro oggetto e controlliamo se sono già presenti elementi al suo interno. Calcoliamo:

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

      controllo:

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

   6. Poiché come risultato del controllo otteniamo true (non ci sono elementi nel bucket), verrà generato un oggetto Node con i seguenti campi:

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

      Il nostro oggetto Node generato verrà aggiunto al bucket sotto l'indice [4]:

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

      newNode()è un metodo che restituisce semplicemente un oggetto della classe Node.

   7. Dopo l'aggiunta, verrà effettuato un controllo per vedere se il numero corrente di elementi supera il parametro threshold:

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

      Se supera, verrà chiamato un metodo resize()per aumentare la dimensione della tabella hash.

      A questo punto il metodo putVal()(e , rispettivamente put()) completerà il suo lavoro.

      Il risultato può essere rappresentato graficamente come segue:

      In generale, questo è l'aspetto dell'aggiunta di un nodo (coppia chiave-valore) a una tabella hash se il bucket desiderato è vuoto . Ora proviamo ad aggiungere un elemento che porterà a una collisione (quando c'è più di un elemento in un bucket).

Un po' di collisioni La situazione in cui chiavi diverse finiscono nello stesso secchio (anche con hash diversi) è chiamata collisione o collisione. Anche se la tabella hash è più grande del set di dati ed è stata scelta una buona funzione hash, ciò non garantisce che non si verifichino collisioni. E il valore hash è limitato all'intervallo di valori int (circa 4 miliardi). Anche il nuovo valore risultante deve essere scritto da qualche parte, e per questo è necessario determinare dove verrà scritto esattamente. Questa si chiama risoluzione dei conflitti. Esistono due approcci:

• metodo di concatenamento o concatenamento esterno (implementato in HashMap) - ad es. la cella contiene effettivamente una lista (catena). E l'elenco potrebbe già contenere diversi valori (non necessariamente con lo stesso codice hash).
• metodo di sondaggio lineare o indirizzamento aperto (implementato in IdentityHashMap) - consiste nel cercare la prima cella vuota dopo quella indicata dalla funzione hash;

Puoi leggere informazioni sulle collisioni qui: clicca

1. Utilizzando il metodo, put()aggiungeremo un'altra coppia chiave-valore alla mappatura hash:

   
   map.put("BLAKE", 10);

2. Calcoliamo l'“hash preliminare” – 63281361. Lo modifichiamo e di conseguenza otteniamo il codice hash finale – 63281940.

3. Poiché il primo controllo di “vuoto” ora restituirà false (non è necessario creare una tabella), calcoliamo immediatamente l'indice del bucket in cui verrà posizionato il nostro oggetto:

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

4. Il bucket all'indice specificato viene controllato per la presenza di elementi al suo interno e poiché if ((p = tab[i = (n - 1) & hash]) == null)in questo caso la condizione non è soddisfatta (c'è già un elemento nel bucket), andiamo al blocco else.

5. Innanzitutto confrontiamo l'elemento da aggiungere con il primo elemento della lista concatenata all'interno del bucket:

   
   (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)

   Invece di passare alla struttura ad albero, verrà chiamato un metodo resize()per aumentare la dimensione della tabella hash, ridistribuendo gli elementi. treeify()a sua volta, l'elenco collegato si TreeNodeconverte in un albero rosso-nero. Il metodo resize()scorre tutti gli elementi della memoria corrente, ricalcola i loro indici (tenendo conto della nuova dimensione) e ridistribuisce gli elementi in un nuovo array.

   Brevemente, senza entrare nei dettagli della struttura dell'albero rosso-nero, accade quanto segue:

   1. Il primo elemento della lista è scritto come radice dell'intero albero (nero):

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

   2. Per altri elementi:

      distribuirli a sinistra o a destra a seconda del valore hash:

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

      Tutti i figli di sinistra devono essere inferiori (o uguali a) al loro nodo radice, mentre tutti i figli di destra devono essere maggiori.

   3. Se due elementi hanno gli stessi hash e non possono essere confrontati in nessun altro modo (non implementano l'interfaccia Comparable), interrompiamo la costruzione dell'albero e chiamiamo il metodo tieBreakOrder(), che a sua volta utilizza il metodo nativo System.identityHashCode()per calcolare un codice hash globalmente univoco .

      Maggiori dettagli qui: link all'articolo

   4. Controlliamo gli elementi dell'albero (oggetti TreeNode) finché non viene trovato un elemento zero figlio (sinistro o destro).

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

   5. Aggiungi un nodo figlio (sinistro o destro a seconda della directory):

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

   6. Poiché l'aggiunta di un nuovo elemento può sconvolgere l'equilibrio dell'albero, chiamiamo il metodo di riequilibrio:

      
      root = balanceInsertion(root, x);

      Puoi leggere informazioni sul bilanciamento del CCH qui: habr

   7. Dopo il bilanciamento, l'elemento radice potrebbe cambiare. Risolviamo questo problema chiamando un metodo che garantisce che la radice passata sarà il primo nodo:

      
      moveRootToFront(tab, root)

      Puoi vedere chiaramente come è costruito un albero rosso-nero e come si autobilancia qui: visualizzazione

Questo è tutto, in linea di principio e usando un esempio, supponiamo di voler aggiungere i seguenti nomi come chiavi: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. E diciamo che abbiamo almeno 64 bucket nella tabella hash e tutti questi elementi si sono accumulati in un bucket. Strutturalmente, questo bucket sarà simile al seguente (gli elementi sono ordinati per codice hash): Tipo di CCHD: Visualizza all'interno del secchio: Recupero di elementi (recupero di un valore tramite chiave) Per quanto riguarda l'operazione di aggiunta, è abbastanza semplice. L'algoritmo (quando è presente una lista concatenata nel bucket) può essere scritto in questo modo:

1. Calcolare il codice hash della chiave.
2. Calcolare l'indice del secchio.
3. Scorri l'indice e confronta la chiave del primo elemento con il valore esistente. Se sono uguali, restituisce il valore, altrimenti controlla l'elemento successivo, se esiste.
4. Se il successivo oggetto Nodo è nullo, restituisce null.
5. Se l'oggetto Nodo successivo non è nullo, vai su di esso e ripeti i primi tre passaggi finché non viene trovato l'elemento o finché l'oggetto Nodo successivo non è nullo.

Utilizzando il metodo, get()otteniamo il valore per la chiave “KING”:

map.get("KING");

Al suo interno si chiama il metodo getNode(int hash, Object key), al quale viene passata la chiave stessa (“KING”) e il suo hash (2306996), che viene precalcolato allo stesso modo che durante l'operazione put().

1. Controlliamo:

   1. esiste anche una tabella hash:(tab = table) != null

      Permettetemi di ricordarvi che quando si crea una HashMap, nel costruttore non viene creato un array per la tabella; questo avviene successivamente nel metodo resize(), che viene sempre chiamato quando si aggiunge il primo elemento alla tabella hash. Pertanto, se non sono stati aggiunti elementi a HashMap, semplicemente non esiste alcun array interno per archiviare gli elementi.

   2. se l'espressione precedente restituisce true, devi assicurarti che la lunghezza dell'array interno sia maggiore di 0:(n = tab.length) > 0;

   3. se anche l'espressione precedente restituisce true, vai al bucket in corrispondenza dell'indice (nel nostro caso 4), calcolato in precedenza, e controlla la presenza di elementi:

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

   4. Confrontiamo la chiave che stiamo cercando con la chiave del primo elemento della lista all'interno del bucket, poiché nella maggior parte dei bucket ci sarà (non ovunque ci siano collisioni) un solo elemento (il nostro caso). Come nel caso del metodo put(), gli hash vengono confrontati e, se corrispondono, le chiavi vengono confrontate per riferimento e solo successivamente per equals().

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

      Poiché nel nostro caso la chiave “KING” precederà la chiave “BLAKE” (all'interno di una lista concatenata i nuovi elementi vengono aggiunti alla fine e KING è stato aggiunto per primo), ci fermeremo a questo punto e restituiremo il primo oggetto di digitare Node al metodo get(), che gli “strappa” un campo con il valore (100):

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

2. Se è presente più di un elemento all'interno del bucket, allora:

   1. se il bucket è un elenco collegato, esaminiamo l'elenco attraverso ciascuno degli elementi in un ciclo do – whilefinché non viene trovata una corrispondenza:

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

   2. se il bucket è una struttura ad albero, il metodo viene inoltre chiamato getTreeNode(), che a sua volta utilizza il metodo per trovare la chiave richiesta find(). Effettuiamo una ricerca ad albero: gli hash vengono confrontati e viene determinato il nodo radice sinistro o destro da cercare. Se le chiavi sono uguali (per riferimento o per equals), restituisce questo nodo. Se i nodi figlio sinistro o destro sono nulli, confrontiamo inoltre le chiavi utilizzando compareTo (se le chiavi implementano l'interfaccia Comparable), altrimenti eseguiamo una ricerca ricorsiva attraverso l'albero (sottoalbero destro o sinistro) finché non viene trovata una corrispondenza.

Rimozione di oggetti da una HashMap Dato che lo spazio nell'articolo sta per esaurirsi, descriverò brevemente come avviene la cancellazione per chiave. L'algoritmo è molto simile:

• vai al secchio desiderato (di nuovo, è precalcolato);

• se c'è un solo oggetto nel bucket (controlliamo il suo puntatore nullo) confrontiamo hash, link e equals(se improvvisamente gli hash non sono uguali). Hai trovato una corrispondenza? Ottimo, questa è la nostra chiave: eliminala (=null) e restituisci il valore di questa chiave.

• se c'è più di un elemento nel bucket, controlliamo ogni elemento in un ciclo finché non troviamo l'elemento o raggiungiamo la fine dell'elenco.

• se l'elemento non è stato trovato, restituiamo null.

Nella situazione con un albero, c'è un'implementazione piuttosto complicata, di cui è meglio non sapere e dormire sonni tranquilli (la descrizione del metodo dice addirittura che l'implementazione è più complicata che in una normale operazione di cancellazione in rosso-nero albero). Inoltre, una volta eliminato, il numero di nodi in un bucket può tornare a 6, quindi l'albero verrà ricostruito nuovamente in un elenco collegato. Se non sei uno sviluppatore con molti anni di esperienza, non è affatto necessario saperlo e capirlo (e semplicemente non è necessario).