Análise detalhada da classe HashMap

Antes de prosseguirmos para uma discussão detalhada da classe, vamos nos concentrar nos conceitos básicos associados às tabelas hash. Este artigo não discutirá métodos para trabalhar com mapeamento hash. Somente as operações de inserção, busca e exclusão serão discutidas de forma clara e detalhada. Acho que não será difícil ler a descrição dos métodos disponíveis para HashMap do mesmo Schildt. Talvez no futuro eu escreva outro artigo dedicado a tais métodos, mas por enquanto isso está em dúvida. Comparada ao Java 7, a classe HashMap no Java 8 sofreu alterações significativas (+1000 linhas de código). Você pode ler sobre a implementação em Java 7 aqui (mas não é mais relevante): habr Uma tabela hash é uma estrutura de dados que implementa a interface de array associativo (modelo abstrato de valor-chave ou entrada), que fornece inserção e pesquisa muito rápidas: independentemente dos elementos numéricos a inserção e a busca (e às vezes a exclusão) são realizadas em um tempo próximo a uma constante - O(1). Essencialmente, este é um array regular, onde a localização do elemento depende do valor do próprio elemento. A relação entre o valor de um elemento e sua posição na tabela hash é especificada por uma função hash. Uma função hash pega um dado de entrada, que chamamos de key , e como saída produz um número inteiro conhecido como valor hash (ou código hash) . O valor hash então vincula nossa chave a um índice específico da tabela hash. Para as operações básicas: inserção, pesquisa e exclusão, usamos a mesma função hash, portanto essas operações são realizadas com bastante rapidez. Por esse motivo, é importante que a função hash se comporte de forma consistente e produza o mesmo índice para os mesmos dados de entrada. É importante notar que o código hash resultante pode ser um valor numérico enorme, e o array original é projetado condicionalmente para apenas 16 elementos. Por que não criar um array com um bilhão de elementos para somar apenas dez? Portanto, devemos de alguma forma transformar esse código hash em valores de 0 a 15 (se o tamanho do array for 16). E para isso, são utilizadas transformações adicionais. Então geramos um índice para minimizar o tamanho do array. Por exemplo, no HashMap anterior ao Java 8, este método adicional era usado para encontrar a célula desejada:

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

Como entrada, tomou-se o código hash obtido como resultado do trabalho hashCode()e o comprimento do array interno (número de células). E retornou o resultado “código hash” -> bit a bit “AND” -> (comprimento do array – 1). A classe HashMapherda da classe AbstractMape implementa as seguintes interfaces: Map, Cloneable, Serializable. O .method é responsável pela função hash em Java hashCode(). A implementação padrão hashCode()retorna um valor chamado código hash de identidade . Mesmo que uma classe seja substituída hashCode(), você sempre poderá obter o hash de ID do objeto chamando System.identityHashCode(Object o). A implementação padrão hashCode()no OpenJDK não tem nada a ver com o endereço de memória, como às vezes se acredita. Mais detalhes aqui: habr No HashMap , a tabela hash é implementada com base em um array (ou, mais precisamente, dinâmico, já que a tabela pode se expandir) de listas vinculadas individualmente. Essencialmente, obtemos o código hash da chave como resultado do método hashCode(), que é então modificado (como consideraremos mais tarde) e internamente, usando um método adicional, os valores resultantes são distribuídos para as células necessárias. Os elementos da matriz (células) também são chamados de buckets , que são usados ​​para armazenar nós individuais. Cada um dos buckets é uma coleção (lista ou árvore). Um nó é um objeto de uma classe aninhada Node(ou TreeNodeem uma estrutura em árvore). Na verdade, dentro da célula da matriz existe LinkedListapenas uma lista vinculada individualmente, ou uma árvore vermelha e preta, que fundamenta a implementação de outra classe - TreeMap. A opção com árvore rubro-negra não surge com tanta frequência (como, o quê e onde - abaixo), e essa estrutura é bastante difícil de entender, então a ênfase estará em um nó do tipo Node. Node é uma classe aninhada dentro HashMapda qual possui os seguintes campos:

• final int hash— o hash do elemento atual, que obtemos como resultado do hash da chave;
• final K key— a chave do elemento atual. É aqui que o que você especifica como o primeiro objeto no método é gravado put();
• V value— o valor do elemento atual. E o que você especifica como segundo objeto no método está escrito aqui put();
• Node < K, V> next— link para o próximo nó dentro da mesma cesta. A lista está conectada, portanto não precisa de um link para o próximo nó, se houver.

Agora vamos dar uma olhada nos campos da própria classe HashMap:

• transient Node < K, V> [] table– a própria tabela hash, implementada com base em um array, para armazenar pares de valores-chave na forma de nós. É aqui que nossos Nodes são armazenados;
• transient int size— número de pares de valores-chave;
• int threshold— o número máximo de elementos, ao atingir o qual o tamanho da tabela hash dobra. Calculado usando a fórmula (capacidade * loadFactor);
• final float loadFactor— este parâmetro determina em que grau de carga a tabela hash atual precisa para criar uma nova tabela hash, ou seja, assim que a tabela hash estiver 75% cheia, uma nova tabela hash será criada e os elementos atuais serão movidos para ela (uma operação dispendiosa, uma vez que todos os elementos devem ser refeitos);
• transient Set< Map.Entry< K,V>> entrySet- contém um arquivo em cache entrySet(), com o qual podemos iterar HashMap.

E constantes:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— capacidade padrão da tabela hash (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— a capacidade máxima possível da tabela hash (aproximadamente mil milhões);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— fator de carga padrão;
• static final int TREEIFY_THRESHOLD = 8é o “limiar” do número de elementos em um balde, ao atingir o qual a lista vinculada interna será convertida em uma estrutura em árvore (árvore vermelha e preta).
• static final int UNTREEIFY_THRESHOLD = 6— se o número de elementos em uma cesta diminuir para 6, ocorrerá uma transição reversa de uma árvore para uma lista vinculada;
• static final int MIN_TREEIFY_CAPACITY = 64— a capacidade mínima (número de buckets) de uma tabela hash na qual é possível uma transição para uma estrutura em árvore. Aqueles. Se houver pelo menos 64 buckets na tabela hash e houver 8 ou mais elementos em um bucket, ocorrerá uma transição para uma estrutura em árvore.

Construtores de classe:

1. public HashMap()— cria uma exibição hash por padrão: por volume (capacity) = 16e com fator de carga (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— cria um mapeamento hash inicializado pelos elementos de outro mapeamento com capacidade inicial suficiente para acomodar os elementos de outro mapeamento;
3. public HashMap(int initialCapacity)— cria um mapa hash com uma determinada capacidade inicial. Para que o HashMap funcione correta e corretamente, o tamanho do array interno deve ser uma potência de dois (ou seja, 16, 64, 128, etc.);
4. public HashMap(int initialCapacity, float loadFactor)— cria um mapa hash com os parâmetros especificados: capacidade inicial e fator de carga.

Uma classe implementa uma interface Mape estende uma classe AbstractMapsem adicionar seus próprios métodos. Um mapa hash não garante a ordem de seus elementos. Portanto, a ordem em que os elementos são inseridos no mapa hash não é necessariamente a ordem em que são recuperados pelo iterador. Adicionando objetos A adição de um par chave-valor é feita usando o arquivo put(). Vejamos as etapas envolvidas ao adicionar um objeto:

1. O valor hash da chave do objeto inserido é calculado. O hash da chave é calculado por um método static final int hash(Object key)que já acessa o hashCode()método da chave que conhecemos. Para fazer isso, é usado um método substituído hashCode()ou sua implementação padrão. Transformações adicionais no 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 кладем маленькие значения, то у них и биты хеш-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. Ao mesmo tempo, calculamos o índice do bucket onde nosso objeto será colocado e verificamos se já existem elementos nele. Calculamos:

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

      verificar:

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

   6. Como como resultado da verificação obtemos true (não há elementos no bucket), será gerado um objeto Node com os seguintes campos:

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

      Nosso objeto Node gerado será adicionado ao bucket no índice [4]:

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

      newNode()é um método que simplesmente retorna um objeto da classe Node.

   7. Após a adição, será feita uma verificação para ver se o número atual de elementos excede o parâmetro threshold:

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

      Se exceder, um método será chamado resize()para aumentar o tamanho da tabela hash.

      Neste ponto, o método putVal()(e, respectivamente put()) completará seu trabalho.

      O resultado pode ser representado graficamente da seguinte forma:

      Em geral, é assim que se parece adicionar um Node (par chave-valor) a uma tabela hash se o bucket desejado estiver vazio . Agora vamos tentar adicionar um elemento que levará a uma colisão (quando houver mais de um elemento em um balde).

Um pouco sobre colisões A situação em que chaves diferentes acabam no mesmo bucket (mesmo com hashes diferentes) é chamada de colisão ou colisão. Mesmo que a tabela hash seja maior que o conjunto de dados e uma boa função hash tenha sido escolhida, isso não garante que não ocorrerão colisões. E o valor do hash é limitado ao intervalo de valores int (cerca de 4 bilhões). O novo valor resultante também precisa ser escrito em algum lugar, e para isso você precisa determinar exatamente onde ele será escrito. Isso é chamado de resolução de conflitos. Existem duas abordagens:

• encadeamento externo ou método de encadeamento (implementado no HashMap) - ou seja, a célula na verdade contém uma lista (cadeia). E a lista já pode conter vários valores (não necessariamente com o mesmo código hash).
• método de sondagem linear ou endereçamento aberto (implementado em IdentityHashMap) - consiste em procurar a primeira célula vazia após aquela apontada pela função hash;

Você pode ler sobre colisões aqui: clique

1. Usando o método, put()adicionaremos outro par de valores-chave ao mapeamento hash:

   map.put("BLAKE", 10);

2. Calculamos o “hash preliminar” – 63281361. Nós o modificamos e como resultado obtemos o código hash final – 63281940.

3. Como a primeira verificação de “vazio” agora retornará falso (não há necessidade de criar uma tabela), calculamos imediatamente o índice do bucket onde nosso objeto será colocado:

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

4. O balde no índice especificado é verificado quanto à presença de elementos nele e, como a condição if ((p = tab[i = (n - 1) & hash]) == null)neste caso não é atendida (já existe um elemento no balde), então vamos para o bloco else.

5. Primeiro de tudo, comparamos o elemento que está sendo adicionado com o primeiro elemento da lista vinculada dentro do 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)

   Ao invés de ir para a estrutura em árvore, será chamado um método resize()para aumentar o tamanho da tabela hash, redistribuindo os elementos. treeify()por sua vez, a lista vinculada de TreeNodese converte em uma árvore rubro-negra. O método resize()itera por todos os elementos do armazenamento atual, recalcula seus índices (levando em consideração o novo tamanho) e redistribui os elementos em um novo array.

   Resumidamente, sem entrar em detalhes da estrutura da árvore rubro-negra, acontece o seguinte:

   1. O primeiro elemento da lista é escrito como a raiz de toda a árvore (preto):

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

   2. Para outros elementos:

      distribua-os para a esquerda ou direita dependendo do valor do hash:

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

      Todos os filhos da esquerda devem ser menores (ou iguais) ao seu nó raiz, enquanto todos os filhos da direita devem ser maiores.

   3. Se dois elementos possuem os mesmos hashes e não podem ser comparados de nenhuma outra forma (eles não implementam a interface Comparable), interrompemos a construção da árvore e chamamos o método tieBreakOrder(), que por sua vez utiliza o método nativo System.identityHashCode()para calcular um código hash globalmente único .

      Mais detalhes aqui: link para o artigo

   4. Verificamos os elementos da árvore (objetos TreeNode) até que um elemento zero filho (esquerdo ou direito) seja encontrado.

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

   5. Adicione um nó filho (esquerdo ou direito dependendo do diretório):

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

   6. Como adicionar um novo elemento pode perturbar o equilíbrio da árvore, chamamos o método de reequilíbrio:

      root = balanceInsertion(root, x);

      Você pode ler sobre como equilibrar o CCH aqui: habr

   7. Após o balanceamento, o elemento raiz pode mudar. Corrigimos isso chamando um método que garante que a raiz passada para ele será o primeiro nó:

      moveRootToFront(tab, root)

      Você pode ver claramente como uma árvore rubro-negra é construída e se autoequilibra aqui: visualização

Isso é tudo, em princípio, e usando um exemplo, vamos supor que queremos adicionar os seguintes nomes como chaves: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. E digamos que temos pelo menos 64 baldes na tabela hash e todos esses elementos foram acumulados em um balde. Estruturalmente, este bucket terá a seguinte aparência (os elementos são classificados por código hash): Tipo de CCHD: Veja dentro do bucket: Recuperar elementos (recuperar um valor por chave) Quanto à operação de adição, é bastante simples. O algoritmo (quando há uma lista vinculada no intervalo) pode ser escrito assim:

1. Calcule o código hash da chave.
2. Calcule o índice do balde.
3. Percorra o índice e compare a chave do primeiro elemento com o valor existente. Se forem iguais, retorne o valor, caso contrário, verifique o próximo elemento, se existir.
4. Se o próximo objeto Node for nulo, retorne nulo.
5. Se o próximo objeto Node não for nulo, vá até ele e repita as três primeiras etapas até que o elemento seja encontrado ou o próximo objeto Node seja nulo.

Usando o método, get()obtemos o valor da chave “KING”:

map.get("KING");

Dentro é chamado o método getNode(int hash, Object key), para o qual são passadas a própria chave (“KING”) e seu hash (2306996), que é pré-calculado da mesma forma que durante a operação put().

1. Nós verificamos:

   1. existe uma tabela hash:(tab = table) != null

      Deixe-me lembrar que ao criar um HashMap, um array para a tabela não é criado no construtor, isso acontece posteriormente no método resize(), que é sempre chamado ao adicionar o primeiro elemento à tabela hash. Portanto, se nenhum elemento tiver sido adicionado ao HashMap, simplesmente não haverá array interno para armazenar os elementos.

   2. se a expressão anterior retornar verdadeiro, você precisa ter certeza de que o comprimento da matriz interna é maior que 0:(n = tab.length) > 0;

   3. se a expressão anterior também retornar verdadeiro, vá até o balde do índice (no nosso caso 4), que foi calculado anteriormente, e verifique a presença de elementos:

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

   4. Comparamos a chave que procuramos com a chave do primeiro elemento da lista dentro do bucket, já que na maioria dos buckets haverá (nem em todos os lugares onde temos colisões) apenas um elemento (nosso caso). Assim como no caso do método put(), os hashes são comparados e, caso correspondam, as chaves são comparadas por referência, e só então por equals().

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

      Como no nosso caso a chave “KING” precederá a chave “BLAKE” (dentro de uma lista encadeada, novos elementos são adicionados ao final, e KING foi adicionado primeiro), pararemos neste ponto e retornaremos o primeiro objeto de type Node ao método get(), que “arranca” dele um campo com o valor (100):

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

2. Se houver mais de um elemento dentro do bucket, então:

   1. se o bucket for uma lista vinculada, percorremos a lista por cada um dos elementos em um loop do – whileaté que uma correspondência seja encontrada:

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

   2. se o intervalo for uma estrutura de árvore, o método será chamado adicionalmente getTreeNode(), que por sua vez usa o método para encontrar a chave necessária find(). Realizamos uma pesquisa em árvore - os hashes são comparados e o nó raiz esquerdo ou direito a ser pesquisado é determinado. Se as chaves forem iguais (por referência ou por equals), retorne este nó. Se os nós filhos esquerdo ou direito forem nulos, comparamos adicionalmente as chaves usando compareTo (se as chaves implementarem a interface Comparable), caso contrário, realizamos uma pesquisa recursiva na árvore (subárvore direita ou esquerda) até que uma correspondência seja encontrada.

Removendo objetos de um HashMap Como o espaço no artigo está acabando, descreverei brevemente como ocorre a exclusão por chave. O algoritmo é muito semelhante:

• vá até o balde desejado (novamente, é pré-calculado);

• se houver apenas um objeto no bucket (verificamos seu ponteiro nulo), comparamos hashes, links e equals(se de repente os hashes não forem iguais). Encontrou uma correspondência? Ótimo, esta é a nossa chave - exclua-a (=null) e retorne o valor desta chave.

• se houver mais de um elemento no balde, verificamos cada elemento em um loop até encontrar o elemento ou chegar ao final da lista.

• se o elemento não foi encontrado, retornamos nulo.

Na situação com uma árvore, há uma implementação bastante complicada, da qual é melhor não saber e dormir profundamente (a descrição do método diz até que a implementação é mais complicada do que em uma operação de exclusão regular em vermelho-preto árvore). Além disso, quando excluído, o número de nós em um intervalo pode retornar para 6 e então a árvore será reconstruída novamente em uma lista vinculada. Se você não é um desenvolvedor com muitos anos de experiência, não é necessário saber e compreender isso (e simplesmente não é necessário).