Análisis detallado de la clase HashMap

Antes de pasar a una discusión detallada de la clase, centrémonos en los conceptos básicos asociados con las tablas hash. Este artículo no discutirá métodos para trabajar con mapeo hash. Sólo se comentarán de forma clara y detallada las operaciones de inserción, búsqueda y eliminación. Creo que no será difícil leer la descripción de los métodos disponibles para HashMap del mismo Schildt. Quizás en el futuro escriba otro artículo dedicado a estos métodos, pero por ahora esto es dudoso. En comparación con Java 7, la clase HashMap en Java 8 ha sufrido cambios significativos (+1000 líneas de código). Puede leer sobre la implementación en Java 7 aquí (pero ya no es relevante): habr Una tabla hash es una estructura de datos que implementa la interfaz de matriz asociativa (entrada o modelo clave-valor abstracto), que proporciona una inserción y búsqueda muy rápidas: independientemente de los elementos numéricos, la inserción y búsqueda (y a veces la eliminación) se realizan en un tiempo cercano a una constante: O (1). Esencialmente, se trata de una matriz regular, donde la ubicación del elemento depende del valor del elemento mismo. La relación entre el valor de un elemento y su posición en la tabla hash se especifica mediante una función hash. Una función hash toma un dato de entrada, al que llamamos clave , y como salida produce un número entero conocido como valor hash (o código hash) . Luego, el valor hash vincula nuestra clave a un índice de tabla hash específico. Para las operaciones básicas: inserción, búsqueda y eliminación, utilizamos la misma función hash, por lo que estas operaciones se realizan con bastante rapidez. Por este motivo, es importante que la función hash se comporte de forma coherente y genere el mismo índice para los mismos datos de entrada. Vale la pena señalar que el código hash resultante puede tener un valor numérico enorme y la matriz original está diseñada condicionalmente para solo 16 elementos. ¿Por qué no crear una matriz con mil millones de elementos para sumar sólo diez? Por lo tanto, debemos transformar de alguna manera este código hash en valores de 0 a 15 (si el tamaño de la matriz es 16). Y para ello se utilizan transformaciones adicionales. Entonces generamos un índice para minimizar el tamaño de la matriz. Por ejemplo, en HashMap antes de Java 8, se usaba este método adicional para encontrar la celda deseada:

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

Como entrada tomó el código hash obtenido como resultado del trabajo hashCode()y la longitud de la matriz interna (número de celdas). Y devolvió el resultado "código hash" -> bit a bit "Y" -> (longitud de la matriz - 1). La clase HashMaphereda de la clase AbstractMape implementa las siguientes interfaces: Map, Cloneable, Serializable. El .method es responsable de la función hash en Java hashCode(). La implementación predeterminada hashCode()devuelve un valor llamado código hash de identidad . Incluso si una clase anula hashCode(), siempre puedes obtener el hash de ID del objeto llamando a System.identityHashCode(Object o). La implementación predeterminada hashCode()en OpenJDK no tiene nada que ver con la dirección de memoria, como a veces se cree. Más detalles aquí: habr En HashMap , la tabla hash se implementa en base a una matriz (o, más precisamente, dinámica, ya que la tabla se puede expandir) de listas enlazadas individualmente. Básicamente, como resultado del método obtenemos el código hash de la clave hashCode(), que luego se modifica (como veremos más adelante), e internamente, utilizando un método adicional, los valores resultantes se distribuyen a las celdas requeridas. Los elementos de la matriz (celdas) también se denominan depósitos y se utilizan para almacenar nodos individuales. Cada uno de los depósitos es una colección (lista o árbol). Un nodo es un objeto de una clase anidada Node(o TreeNodeen una estructura de árbol). De hecho, dentro de la celda de la matriz se encuentra LinkedListsolo una lista enlazada individualmente, o un árbol rojo-negro, que subyace a la implementación de otra clase: TreeMap. La opción con un árbol rojo-negro no surge tan a menudo (cómo, qué y dónde, a continuación), y esta estructura es bastante difícil de entender, por lo que el énfasis estará en un nodo del tipo Nodo. Node es una clase anidada dentro HashMapde la cual tiene los siguientes campos:

• final int hash— el hash del elemento actual, que obtenemos como resultado del hash de la clave;
• final K key— la clave del elemento actual. Aquí es donde se escribe lo que usted especifica como el primer objeto del método put();
• V value— el valor del elemento actual. Y lo que especificas como segundo objeto en el método está escrito aquí put();
• Node < K, V> next— enlace al siguiente nodo dentro de la misma cesta. La lista está conectada, por lo que necesita un enlace, no al siguiente nodo, si lo hay.

Ahora veamos los campos de la propia clase HashMap:

• transient Node < K, V> [] table– la propia tabla hash, implementada sobre la base de una matriz, para almacenar pares clave-valor en forma de nodos. Aquí es donde se almacenan nuestros Nodos;
• transient int size— número de pares clave-valor;
• int threshold— el número máximo de elementos, al alcanzar el cual el tamaño de la tabla hash se duplica. Calculado usando la fórmula (capacidad * loadFactor);
• final float loadFactor— este parámetro determina en qué grado de carga la tabla hash actual necesita para crear una nueva tabla hash, es decir tan pronto como la tabla hash esté llena al 75%, se creará una nueva tabla hash y los elementos actuales se trasladarán a ella (una operación costosa, ya que todos los elementos deben repetirse);
• transient Set< Map.Entry< K,V>> entrySet- Contiene un caché entrySet(), con el que podemos iterar HashMap.

Y constantes:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— capacidad de la tabla hash por defecto (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— la capacidad máxima posible de la tabla hash (aproximadamente mil millones);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— factor de carga por defecto;
• static final int TREEIFY_THRESHOLD = 8es el "umbral" del número de elementos en un depósito, al alcanzar el cual la lista enlazada interna se convertirá en una estructura de árbol (árbol rojo-negro).
• static final int UNTREEIFY_THRESHOLD = 6— si el número de elementos en una cesta disminuye a 6, se producirá una transición inversa de un árbol a una lista enlazada;
• static final int MIN_TREEIFY_CAPACITY = 64— la capacidad mínima (número de depósitos) de una tabla hash en la que es posible una transición a una estructura de árbol. Aquellos. Si hay al menos 64 depósitos en la tabla hash y hay 8 o más elementos en un depósito, se producirá una transición a una estructura de árbol.

Constructores de clases:

1. public HashMap()— crea una visualización hash por defecto: por volumen (capacity) = 16y con factor de carga (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— crea un mapeo hash inicializado por los elementos de otro mapeo dado con la capacidad inicial suficiente para acomodar los elementos de otro mapeo;
3. public HashMap(int initialCapacity)— crea un mapa hash con una capacidad inicial determinada. Para que HashMap funcione correcta y correctamente, el tamaño de la matriz interna debe ser una potencia de dos (es decir, 16, 64, 128, etc.);
4. public HashMap(int initialCapacity, float loadFactor)— crea un mapa hash con los parámetros especificados: capacidad inicial y factor de carga.

Una clase implementa una interfaz Mapy extiende una clase AbstractMapsin agregar sus propios métodos. Un mapa hash no garantiza el orden de sus elementos. Por lo tanto, el orden en que se ingresan los elementos en el mapa hash no es necesariamente el orden en que el iterador los recupera. Agregar objetos Para agregar un par clave-valor se utiliza el archivo put(). Veamos los pasos involucrados al agregar un objeto:

1. Se calcula el valor hash de la clave del objeto ingresado. El hash de clave se calcula mediante un método static final int hash(Object key)que ya accede al hashCode()método de clave que conocemos. Para ello, hashCode()se utiliza un método anulado o su implementación predeterminada. Transformaciones adicionales en el método 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 кладем маленькие значения, то у них и биты хеш-códigoов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Cómoой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша un objetoа начали вносить коррективы в то, в Cómoой бакет попадёт un objeto) и, Cómo следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

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

   
   i = (n - 1) & hash

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

3. Создается un objeto Node.

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

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

   1. Создадим un objeto класса HashMap:

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

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

      map.put("KING", 100);

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

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

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

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

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

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

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

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

   5. Одновременно вычисляем индекс бакета, куда будет помещен наш un objeto, и проверяем, а есть ли уже в нем элементы. Вычисляем:

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

      проверяем:

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

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

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

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

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

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

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

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

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

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

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

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

Un poco sobre colisiones La situación en la que diferentes claves terminan en el mismo depósito (incluso con diferentes hashes) se llama colisión o colisión. Incluso si la tabla hash es más grande que el conjunto de datos y se ha elegido una buena función hash, esto no garantiza que no se produzcan colisiones. Y el valor hash está limitado al rango de valores int (alrededor de 4 mil millones). El nuevo valor resultante también debe escribirse en algún lugar y, para ello, debe determinar dónde se escribirá exactamente. A esto se le llama resolución de conflictos. Hay dos enfoques:

• método de encadenamiento o encadenamiento externo (implementado en HashMap), es decir, la celda en realidad contiene una lista (cadena). Y es posible que la lista ya contenga varios valores (no necesariamente con el mismo código hash).
• sondeo lineal o método de direccionamiento abierto (implementado en IdentityHashMap): consiste en buscar la primera celda vacía después de la que señala la función hash;

Puede leer sobre colisiones aquí: haga clic

1. Usando el método, put()agregaremos otro par clave-valor al mapeo hash:

   map.put("BLAKE", 10);

2. Calculamos el “hash preliminar” – 63281361. Lo modificamos y como resultado obtenemos el código hash final – 63281940.

3. Dado que la primera comprobación de "vacío" ahora devolverá falso (no es necesario crear una tabla), calculamos inmediatamente el índice del depósito donde se colocará nuestro objeto:

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

4. Se verifica la presencia de elementos en el depósito en el índice especificado y, como if ((p = tab[i = (n - 1) & hash]) == null)en este caso no se cumple la condición (ya hay un elemento en el depósito), vamos al bloque else.

5. En primer lugar, comparamos el elemento que se agrega con el primer elemento de la lista vinculada dentro del depósito:

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

   Al realizar la verificación, primero se comparan los hashes de claves. Si esta "parte" (p.hash == hash)devuelve falso, entonces el resto de la condición se ignora ( &&) ya que se garantiza que los objetos serán diferentes. De lo contrario, las claves se comparan por referencia (==) y, en caso de desigualdad, las claves se comparan mediante el método equals(). Las comparaciones se realizan en este orden por motivos de rendimiento. Si las tres expresiones devuelven verdadero, esto significa que las claves son iguales y el nuevo elemento se escribirá en una variable adicional para luego sobrescribir el valor de la clave:

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

   Como resultado de comparar las claves, ya obtenemos falso en la primera etapa (diferentes hashes).

6. Ignoramos la condición ( p instanceof TreeNode) ya que la estructura en el depósito no tiene forma de árbol en esta etapa.

7. A continuación, entramos en un bucle for, donde dentro de un depósito verificamos los elementos en busca de un puntero al siguiente elemento next, y si es nulo (lo que significa que el elemento en la lista es el último y único), agregamos un nuevo Nodo. elemento al final de la lista:

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

   Quizás te preguntes, ¿dónde está el control clave de igualdad? No podemos simplemente seguir adelante y agregar un nuevo elemento. Por lo tanto, ya se aplicó de antemano en el párrafo (5). Gracias a esto, ahora podemos simplemente verificar el puntero de este elemento y, como ahora es nulo, podemos concluir que solo hay un elemento en la lista. Y como ya hemos verificado sus claves, podemos agregar de forma segura un nuevo elemento.

   Si durante la primera iteración el puntero no es nulo, esto indica que hay al menos dos elementos en la lista, por lo que en este caso pasamos a la siguiente condición y comparamos la clave del elemento que se está agregando con todas las claves del elementos de la lista (en la forma descrita en el quinto párrafo).

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

   Si se encuentra una coincidencia al comparar las claves, el nuevo elemento se escribirá en una variable adicional para luego sobrescribir el valor de la clave.

   Después de agregar el segundo elemento, nuestro objeto HashMap se ve gráficamente así:

   Como resultado, agregar elementos durante una colisión (dentro de un segmento) se ve así:

   • Comprobamos mediante los métodos hashCode()y equals()que ambas claves son iguales.
   • Si las claves son las mismas, reemplace el valor actual por el nuevo.
   • de lo contrario, conecte los objetos nuevos y antiguos usando una estructura de datos de “lista enlazada”, indicando un enlace al siguiente objeto en el actual y almacene ambos bajo el índice deseado; o cambiar a una estructura de árbol

8. Después de cada iteración (agregar un nuevo elemento), el bucle for aumenta el contador, que es responsable de la cantidad de elementos en el depósito:

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

   Hasta que su número sea igual o mayor que 7:

   binCount >= TREEIFY_THRESHOLD – 1

   En este caso, se llamará a un método treeifyBin()treeify()para construir directamente la estructura de árbol. Sin embargo, si la cantidad de depósitos en la tabla hash actual es inferior a 64:

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

   En lugar de ir a la estructura de árbol, se llamará a un método resize()para aumentar el tamaño de la tabla hash, redistribuyendo los elementos. treeify()a su vez, la lista enlazada de TreeNodese convierte en un árbol rojo-negro. El método resize()recorre en iteración todos los elementos del almacenamiento actual, recalcula sus índices (teniendo en cuenta el nuevo tamaño) y redistribuye los elementos en una nueva matriz.

   Brevemente, sin entrar en detalles de la estructura del árbol rojo-negro, sucede lo siguiente:

   1. El primer elemento de la lista se escribe como la raíz de todo el árbol (negro):

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

   2. Para otros elementos:

      distribuirlos a la izquierda o a la derecha dependiendo del valor hash:

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

      Todos los hijos de la izquierda deben ser menores (o iguales) que su nodo raíz, mientras que todos los hijos de la derecha deben ser mayores.

   3. Si dos elementos tienen los mismos hashes y no se pueden comparar de ninguna otra manera (no implementan la interfaz Comparable), interrumpimos la construcción del árbol y llamamos al método tieBreakOrder(), que a su vez utiliza el método nativo System.identityHashCode()para calcular un código hash globalmente único. .

      Más detalles aquí: enlace al artículo

   4. Verificamos los elementos del árbol (objetos TreeNode) hasta que se encuentra un elemento cero secundario (izquierdo o derecho).

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

   5. Agregue un nodo secundario (izquierda o derecha según el directorio):

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

   6. Dado que agregar un nuevo elemento puede alterar el equilibrio del árbol, llamamos al método de reequilibrio:

      root = balanceInsertion(root, x);

      Puede leer sobre el equilibrio del CCH aquí: habr

   7. Después del equilibrio, el elemento raíz puede cambiar. Arreglamos esto llamando a un método que garantiza que la raíz que se le pasa será el primer nodo:

      moveRootToFront(tab, root)

      Aquí puedes ver claramente cómo se construye y se equilibra un árbol rojo-negro: visualización

Eso es todo, en principio, y usando un ejemplo, supongamos que queremos agregar como claves los siguientes nombres: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Y digamos que tenemos al menos 64 depósitos en la tabla hash y todos estos elementos se han acumulado en un depósito. Estructuralmente, este depósito se verá así (los elementos están ordenados por código hash): Tipo de CCHD: Vista dentro del cubo: Recuperar elementos (recuperar un valor por clave) En cuanto a la operación de suma, es bastante sencilla. El algoritmo (cuando hay una lista vinculada en el depósito) se puede escribir así:

1. Calcule el código hash de la clave.
2. Calcule el índice del cubo.
3. Revise el índice y compare la clave del primer elemento con el valor existente. Si son iguales, devuelve el valor; de lo contrario, comprueba el siguiente elemento, si existe.
4. Si el siguiente objeto Nodo es nulo, devuelve nulo.
5. Si el siguiente objeto Nodo no es nulo, vaya a él y repita los primeros tres pasos hasta que se encuentre el elemento o el siguiente objeto Nodo sea nulo.

Usando el método, get()obtenemos el valor de la clave "KING":

map.get("KING");

En su interior se llama al método getNode(int hash, Object key)al que se le pasa la propia clave (“KING”) y su hash (2306996), el cual se calcula previamente de la misma forma que durante la operación put().

1. Verificamos:

   1. ¿Existe siquiera una tabla hash?(tab = table) != null

      Permítanme recordarles que al crear un HashMap, no se crea una matriz para la tabla en el constructor, esto sucede más adelante en el método resize(), que siempre se llama al agregar el primer elemento a la tabla hash. Por lo tanto, si no se han agregado elementos al HashMap, simplemente no hay una matriz interna para almacenar los elementos.

   2. Si la expresión anterior devuelve verdadero, debes asegurarte de que la longitud de la matriz interna sea mayor que 0:(n = tab.length) > 0;

   3. Si la expresión anterior también devuelve verdadero, vaya al depósito en el índice (en nuestro caso 4), que se calculó previamente, y verifique la presencia de elementos:

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

   4. Comparamos la clave que estamos buscando con la clave del primer elemento de la lista dentro del depósito, ya que en la mayoría de los depósitos habrá (no en todos los lugares donde tenemos colisiones) solo un elemento (nuestro caso). Como en el caso del método put(), se comparan los hashes, y si coinciden, las claves se comparan por referencia, y solo entonces por equals().

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

      Dado que en nuestro caso, la clave “KING” precederá a la clave “BLAKE” (dentro de una lista enlazada, los nuevos elementos se agregan al final y KING se agregó primero), nos detendremos en este punto y devolveremos el primer objeto de escriba Nodo al método get(), que le “arrebata” un campo con el valor (100):

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

2. Si hay más de un elemento dentro del depósito, entonces:

   1. Si el depósito es una lista vinculada, revisamos la lista a través de cada uno de los elementos en un bucle do – whilehasta encontrar una coincidencia:

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

   2. si el depósito es una estructura de árbol, entonces se llama adicionalmente al método getTreeNode(), que a su vez utiliza el método para encontrar la clave requerida find(). Realizamos una búsqueda de árbol: se comparan los hashes y se determina el nodo raíz izquierdo o derecho a buscar. Si las claves son iguales (por referencia o por equals), devuelve este nodo. Si los nodos secundarios izquierdo o derecho son nulos, además comparamos las claves usando compareTo (si las claves implementan la interfaz Comparable); de lo contrario, realizamos una búsqueda recursiva en el árbol (subárbol derecho o izquierdo) hasta encontrar una coincidencia.

Eliminación de objetos de un HashMap Dado que el espacio en el artículo se está agotando, describiré brevemente cómo se produce la eliminación por clave. El algoritmo es muy similar:

• vaya al depósito deseado (nuevamente, está calculado previamente);

• si solo hay un objeto en el depósito (comprobamos su puntero nulo) comparamos hashes, enlaces y equals(si de repente los hashes no son iguales). ¿Encontraste una coincidencia? Genial, esta es nuestra clave: elimínela (= nula) y devuelva el valor de esta clave.

• si hay más de un elemento en el depósito, verificamos cada elemento en un bucle hasta que encontramos el elemento o llegamos al final de la lista.

• si no se encontró el elemento, devolvemos nulo.

En la situación con un árbol, hay una implementación bastante complicada, que es mejor no conocer y dormir tranquilo (la descripción del método incluso dice que la implementación es más complicada que en una operación de eliminación normal en un color rojo-negro árbol). Además, cuando se elimina, la cantidad de nodos en un depósito puede volver a 6 y luego el árbol se reconstruirá nuevamente en una lista vinculada. Si no es un desarrollador con muchos años de experiencia, no es necesario que lo sepa y lo comprenda (y simplemente no es necesario).