Tabela Hash
Última atualização
Uma tabela hash armazena itens em um arranjo de baldes. Para inserir ou encontrar uma chave, ela passa a chave por uma função hash e toma o resultado módulo o número de baldes - isso fornece o índice do balde em O(1). Pressione reproduzir acima para ver cada chave ser convertida em hash para um balde e armazenada, e depois uma busca saltar direto para o balde correto.
Quando duas chaves caem no mesmo balde - uma colisão - esta visualização usa encadeamento separado: cada balde contém uma pequena lista, e as chaves que colidem são anexadas a ela. Enquanto a tabela não estiver cheia demais (um fator de carga baixo) e o hash distribuir bem as chaves, as cadeias permanecem curtas e inserção, busca e remoção são O(1) em média.
Complexidade de tempo
| Operação | Média | Pior caso |
|---|---|---|
| Inserir | O(1) | O(n) (todas as chaves colidem) |
| Busca | O(1) | O(n) |
| Remover | O(1) | O(n) |
| Espaço | O(n) | O(n) |
Conceitos-chave
| Termo | Significado |
|---|---|
| Função hash | Mapeia uma chave para um índice de balde |
| Colisão | Duas chaves caem no mesmo balde |
| Encadeamento separado | Cada balde contém uma lista de entradas que colidem |
| Endereçamento aberto | Alternativa: sondar o próximo slot livre |
| Fator de carga | entradas / baldes - determina o redimensionamento |
Exemplo resolvido
Inserindo as chaves 20, 34, 9, 13 em uma tabela com 7 baldes, usando hash(k) = k % 7:
| Passo | Estrutura | Ação |
|---|---|---|
Inserir 20 | balde 6: [20] | 20 % 7 = 6, balde 6 vazio, armazenar 20 |
Inserir 34 | balde 6: [20, 34] | 34 % 7 = 6, colisão com 20, anexar 34 à cadeia |
Inserir 9 | balde 2: [9] | 9 % 7 = 2, balde 2 vazio, armazenar 9 |
Inserir 13 | balde 6: [20, 34, 13] | 13 % 7 = 6, colisão, anexar 13 à cadeia do balde 6 |
Buscar 34 | balde 6: [20, 34, 13] | 34 % 7 = 6, percorrer cadeia: 20 não, 34 corresponde - encontrado |
Quando usar uma tabela hash
| Use quando | Evite quando |
|---|---|
Você precisa de inserção, busca e remoção por chave em O(1) médio | Você precisa manter as chaves ordenadas - use uma BST balanceada |
| As chaves não têm ordem útil e você só testa pertencimento por correspondência exata | Você precisa de consultas por intervalo ou buscas da chave mais próxima |
| Você pode arcar com memória extra para baldes e um fator de carga baixo | A memória é extremamente limitada e cada byte conta |
| Existe uma boa função hash para o seu tipo de chave | A latência do pior caso deve ser limitada - as colisões a tornam O(n) |
Código de Hash Table
Uma implementação limpa e executável de Hash Table em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Hash Table em Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Código de Hash Table em JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Código de Hash Table em Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Código de Hash Table em C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Código de Hash Table em C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}Perguntas frequentes sobre a tabela hash
O que é uma colisão de hash e como ela é resolvida?
Uma colisão ocorre quando duas chaves diferentes caem no mesmo balde. As duas soluções comuns são o encadeamento separado (cada balde contém uma lista e as chaves que colidem são anexadas - mostrado aqui) e o endereçamento aberto (sondar o próximo slot vazio do arranjo). Ambos mantêm as buscas corretas; diferem no layout de memória e no desempenho sob carga alta.
Qual é a complexidade de tempo de uma tabela hash?
Inserção, busca e remoção são
O(1) em média quando a função hash distribui as chaves uniformemente e o fator de carga é mantido baixo. No pior caso - todas as chaves colidindo em um único balde - elas se degradam para O(n), por isso uma boa função hash e o redimensionamento importam.O que é um fator de carga?
O fator de carga é o número de entradas armazenadas dividido pelo número de baldes. À medida que cresce, as cadeias ficam mais longas e as operações mais lentas, por isso a maioria das tabelas hash redimensiona (refaz o hash para um arranjo maior) quando ele ultrapassa um limite como 0.75.
Quando devo usar uma tabela hash em vez de uma árvore binária de busca?
Use uma tabela hash quando você só precisa de buscas por correspondência exata e quer velocidade
O(1) média sem requisito de ordem. Use uma árvore binária de busca balanceada quando você precisa de chaves ordenadas, consultas por intervalo ou buscas de predecessor/sucessor, algo que uma tabela hash não faz de forma eficiente. Uma BST oferece operações O(log n) garantidas, enquanto uma tabela hash troca essa garantia por um desempenho médio mais rápido.Qual é a diferença entre encadeamento separado e endereçamento aberto?
O encadeamento separado armazena as chaves que colidem em uma lista por balde, de modo que um balde pode conter muitas entradas e a tabela nunca fica realmente cheia. O endereçamento aberto mantém tudo no próprio arranjo e sonda o próximo slot livre em uma colisão, o que é amigável ao cache mas se degrada bruscamente quando o fator de carga se aproxima de 1 e requer tratamento cuidadoso de remoção. O encadeamento tolera fatores de carga mais altos; o endereçamento aberto usa a memória de forma mais compacta.
Por que não posso confiar que uma tabela hash mantenha minhas chaves na ordem de inserção ou de ordenação?
Uma função hash espalha deliberadamente as chaves entre os baldes para evitar aglomeração, então a ordem de iteração reflete o layout dos baldes, não a ordem de inserção ou de ordenação. Se você precisa de ordem, use um mapa/árvore ordenado ou uma estrutura como um mapa com ordem de inserção (por exemplo, o
dict do Python preserva a ordem de inserção, mas isso é uma garantia da linguagem, não uma propriedade inerente da tabela hash). Nunca presuma que a ordem de iteração corresponde à forma como você inseriu as chaves, a menos que a linguagem prometa isso explicitamente.Recursos relacionados
Mais visualizações
