Qual é a organização interna dos dados que está na base da estrutura Map?

A estrutura de Map em Java baseia-se numa organização interna de dados que depende da implementação específica:

• HashMap — usa um array de baldes, cada um contendo uma lista ligada ou uma árvore (a partir do Java 8) para armazenar pares chave-valor. As chaves são hashadas para determinar o índice do balde.

• TreeMap — é implementado com base numa árvore vermelho-preto, o que garante o armazenamento ordenado das chaves.

• LinkedHashMap — estende HashMap, mantendo a ordem de inserção dos elementos através de uma lista ligada.

Assim, a estrutura básica é ou uma tabela de hash com cadeias (HashMap), ou uma árvore balanceada (TreeMap).