Toda vez que você escreve lista[3] ou usuarios.get(‘davi’), o computador entrega o valor quase instantaneamente. Parece mágica, mas não é. Por trás dessas duas linhas existem duas formas bem diferentes de organizar dados na memória: o array e a hash table.

A ideia aqui não é decorar tabela de complexidade, e sim entender por que um é rápido em certas coisas e lento em outras. Quando você enxerga como cada um fica guardado na memória, a escolha entre eles deixa de ser chute.

Os exemplos estão em JavaScript, mas o conceito vale pra qualquer linguagem.

Antes de tudo: o que é a memória?

Imagine a memória RAM como uma fileira gigante de gavetinhas, uma do lado da outra. Cada gavetinha guarda 1 byte e tem um número único, o seu endereço. Pra ler ou escrever alguma coisa, o processador precisa saber o endereço. Só isso.

Guarda essa imagem, porque tudo daqui pra frente é sobre como escolher em quais gavetinhas colocar cada dado e como encontrá-las de novo depois.

Array: tudo em fila

O array é a estrutura mais simples que existe: os elementos ficam um colado no outro, em um bloco contínuo de memória.

Pense num array de 5 números inteiros, onde cada número ocupa 4 bytes:

endereço: 1000  1004  1008  1012  1016
          [10]  [20]  [30]  [40]  [50]
índice:    0     1     2     3     4

Agora vem a parte bonita. Se eu quero o elemento de índice 3, o computador não precisa passar pelos três primeiros. Ele faz uma conta:

endereço = início + índice × tamanho
         = 1000   + 3      × 4
         = 1012

Uma multiplicação e uma soma, e pronto, está lá. Não importa se o array tem 5 ou 5 milhões de elementos, o custo é o mesmo. É isso que chamam de acesso O(1), ou tempo constante.

O preço da fila

Nem tudo são flores. Como os elementos precisam ficar colados, inserir algo no começo ou no meio dá trabalho. Pra colocar o 5 na posição 0, todo mundo tem que andar uma casa pra direita:

antes:   [10][20][30][40][50]
          ↓   ↓   ↓   ↓   ↓
depois:  [ 5][10][20][30][40][50]

Com 5 elementos, tranquilo. Com 5 milhões, são 5 milhões de cópias. Remover do começo é a mesma coisa, só que no sentido contrário.

E buscar um valor (não um índice) também não é rápido. Se eu quero saber se o 40 está no array, a única saída é olhar um por um até achar. No pior caso, olho todos: O(n).

“Mas o meu array cresce sozinho!”

Pois é. Em JavaScript, Python, Java (ArrayList) e companhia, você dá push à vontade e nunca pensa no tamanho. Isso acontece porque essas linguagens usam um array dinâmico: por baixo dos panos elas reservam um bloco maior do que o necessário (a capacidade). Quando esse bloco enche, alocam um novo, geralmente com o dobro do tamanho, copiam tudo pra lá e liberam o antigo.

cheio, chegou o 50:
cap. 4: [10][20][30][40]
cap. 8: [10][20][30][40][50][  ][  ][  ]

Essa cópia é cara, mas acontece cada vez mais raramente, então na média o push continua sendo O(1).

O bônus escondido: cache

Tem mais um motivo pra arrays serem rápidos, e esse quase ninguém comenta. Quando o processador lê um endereço da RAM, ele não traz só aquele byte: traz um pedaço inteiro da vizinhança (uma linha de cache, normalmente de 64 bytes) pra uma memória bem mais rápida dentro dele. Como os elementos do array estão colados, ao ler o primeiro ele já trouxe os próximos de brinde. Percorrer um array é praticamente andar em cima de dados que já estão à mão.

E no JavaScript?

Aqui cabe uma ressalva. No JavaScript, o array é tecnicamente um objeto, mas os motores (como o V8, do Chrome e do Node.js) são espertos: enquanto o array for “bem comportado”, ele é guardado num bloco contínuo de verdade. Se você fizer algo como:

const lista = [1, 2, 3]
lista[1000000] = 4

o V8 percebe que não vale a pena reservar um milhão de posições vazias e passa a guardar esse array como… uma hash table. Guarda essa informação, porque já já ela vai fazer sentido.

Outro detalhe: um array de objetos não guarda os objetos em si em sequência, e sim referências (endereços) para eles. As referências ficam coladas; os objetos ficam espalhados pela memória.

Hash Table: cada coisa no seu lugar

O array é ótimo quando você sabe a posição do que quer. Mas na vida real a gente quer buscar por nome, por e-mail, por id. Queremos algo como:

estoque.get('banana') // 12

Sem ter que percorrer item por item. É aí que entra a hash table (ou tabela hash, ou tabela de dispersão, pra quem gosta do nome em português).

No dia a dia você quase nunca usa uma hash table “crua”. O que você usa é um hash map: a implementação de um dicionário chave → valor que roda em cima de uma hash table. É o Map no JS, o dict no Python, o HashMap no Java. A hash table é a estrutura; o hash map é o que as linguagens te entregam pronto usando ela.

E aqui vai a revelação: uma hash table é um array por baixo dos panos. O truque está em como ela transforma uma chave (‘banana’) num índice (5).

A função hash

Quem faz essa mágica é a função hash: ela recebe uma chave e devolve um número. A regra mais importante é que, pra mesma chave, o número é sempre o mesmo. Uma versão bem simples pra strings:

const hash = (key) => {
  let h = 0
  for (const char of key) {
    h = (h * 31 + char.charCodeAt(0)) >>> 0
  }
  return h
}

hash('banana') // 2898612069

Esse número é enorme, e o nosso array interno (os buckets, ou baldes) é pequeno. Então pegamos o resto da divisão pelo tamanho do array:

2898612069 % 8 = 5
→ 'banana' vai pro bucket 5

Pra buscar, é o mesmo caminho: calcula o hash de ‘banana’, tira o resto, cai no bucket 5. Sem percorrer nada. Uma conta e um acesso a um array, exatamente como antes: O(1).

Colisões

Agora o problema. Vamos guardar o estoque de uma feira numa hash table de 8 buckets:

'banana' → 2898612069 % 8 = 5
'uva'    →     116192 % 8 = 0
'maçã'   →    3347824 % 8 = 0   ← opa
'pera'   →    3437284 % 8 = 4

‘uva’ e ‘maçã’ caíram no mesmo bucket. Isso é uma colisão, e ela não é um bug: com infinitas chaves possíveis e poucos buckets, colisões são inevitáveis. A questão é como lidar com elas. As duas abordagens mais comuns são:

  • Encadeamento (chaining): cada bucket guarda uma listinha. Colidiu? Entra na fila daquele bucket.
  • Endereçamento aberto (open addressing): colidiu? Procura o próximo bucket livre e coloca lá.

Com encadeamento, a memória fica assim:

bucket 0 │ → ['uva', 30] → ['maçã', 7]
bucket 1 │
bucket 2 │
bucket 3 │
bucket 4 │ → ['pera', 3]
bucket 5 │ → ['banana', 12]
bucket 6 │
bucket 7 │

Pra buscar ‘maçã’, vou direto no bucket 0 e percorro só aquela listinha, comparando as chaves. Desde que as listinhas sejam curtas, continua rápido.

Fator de carga e redimensionamento

Se eu continuar enfiando chaves numa hash table de 8 buckets, as listinhas vão crescer e a busca vai degradar até virar uma busca linear. Pra evitar isso, a hash table acompanha o fator de carga: quantidade de itens dividida pela quantidade de buckets. Quando passa de um limite (0.75 é um valor clássico), ela cria um array de buckets com o dobro do tamanho e redistribui todo mundo, já que o resto da divisão muda quando o tamanho muda. Esse processo se chama rehash.

É a mesma ideia do array dinâmico: uma operação cara de vez em quando, pra manter tudo barato no dia a dia.

Colocando a mão na massa

Juntando tudo, uma hash table de brinquedo fica assim:

class HashTable {
  constructor(capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => [])
    this.size = 0
  }

  #indexOf(key) {
    return hash(key) % this.buckets.length
  }

  set(key, value) {
    const bucket = this.buckets[this.#indexOf(key)]
    const entry = bucket.find(([k]) => k === key)
    if (entry) {
      entry[1] = value
      return
    }
    bucket.push([key, value])
    this.size++
    if (this.size / this.buckets.length > 0.75) this.#resize()
  }

  get(key) {
    const bucket = this.buckets[this.#indexOf(key)]
    const entry = bucket.find(([k]) => k === key)
    return entry?.[1]
  }

  #resize() {
    const old = this.buckets
    this.buckets = Array.from({ length: old.length * 2 }, () => [])
    this.size = 0
    for (const bucket of old) {
      for (const [key, value] of bucket) this.set(key, value)
    }
  }
}

Testando:

const estoque = new HashTable()
estoque.set('banana', 12)
estoque.set('uva', 30)
estoque.set('maçã', 7)
estoque.set('pera', 3)

estoque.get('maçã') // 7
estoque.get('kiwi') // undefined

Óbvio que isso aqui não vai pra produção, as implementações de verdade são bem mais sofisticadas. Mas a estrutura é essa: um array de buckets, uma função hash e um plano pra colisões.

O preço da hash table

  • Mais memória: sempre sobram buckets vazios (é de propósito, pra manter o fator de carga baixo), e cada entrada guarda a chave junto com o valor.
  • Dados espalhados: com encadeamento, as entradas ficam em pedaços diferentes da memória, então o bônus do cache que o array tem aqui é bem menor.
  • O(1) é na média: se a função hash for ruim e todo mundo cair no mesmo bucket, a busca vira O(n).
  • Sem ordem natural: a posição de cada chave depende do hash, não da ordem de inserção. (O Map do JavaScript é uma exceção: a especificação garante a ordem de inserção, e o V8 mantém uma estrutura extra só pra isso.)

Na prática: quando a diferença aparece

Um exemplo clássico: verificar se uma lista tem itens duplicados. Usando só array, a solução intuitiva é comparar cada item com todos os outros:

const temDuplicado = (lista) => {
  for (let i = 0; i < lista.length; i++) {
    for (let j = i + 1; j < lista.length; j++) {
      if (lista[i] === lista[j]) return true
    }
  }
  return false
}

Isso é O(n²). Agora, usando um Set (que por baixo também é uma hash table, só que guarda apenas as chaves):

const temDuplicado = (lista) => {
  const vistos = new Set()
  for (const item of lista) {
    if (vistos.has(item)) return true
    vistos.add(item)
  }
  return false
}

Uma passada só: O(n). Rodando as duas versões aqui com uma lista de 50 mil números sem duplicados, a primeira levou cerca de 1,1 segundo e a segunda, 15 milissegundos. Pau na bala!!!

Resumindo

  • Array: elementos colados na memória. Acesso por índice instantâneo, percorrer é muito rápido (cache), ocupa pouca memória. Em compensação, buscar por valor e inserir no começo ou no meio custam caro.
  • Hash table: um array de buckets + função hash. Busca, inserção e remoção por chave instantâneas na média. Em compensação, usa mais memória, os dados ficam mais espalhados e não existe “ordem” natural.

Precisa de uma sequência, ordem importa, vai percorrer tudo? Array. Precisa achar coisas por uma chave, rápido e muitas vezes? Hash table (na prática, um Map, dict ou HashMap da sua linguagem).

Conclusão

No fim das contas, as duas estruturas resolvem o mesmo problema fundamental: como achar o endereço certo na memória sem ter que procurar. O array resolve isso com posição: se eu sei o índice, sei o endereço. A hash table resolve com uma conta em cima da chave: se eu sei a chave, sei o bucket.

Entender isso muda a forma de olhar pro código. Aquele .find() dentro de um loop, aquele .includes() em uma lista gigante, muitas vezes podem virar um Map ou um Set e a performance agradece. E o contrário também vale: nem tudo precisa de hash table, às vezes um array simples, percorrido do começo ao fim, é a opção mais rápida e mais legível.

Referências