Hashing
Introduzido| English | Significado |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | função de hash |
| key/kiː/ | chave |
| address/əˈdres/ | endereço |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | determinístico |
| collision/kəˈlɪʒn/ | colisão |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | sondagem linear |
| chaining/ˈtʃeɪnɪŋ/ | encadeamento |
| load factor/ləʊd ˈfæktə/ | fator de carga |
Encontrar uma linha em cinquenta milhões sem olhar
- Um caixa de supermercado escaneia um código de barras e o preço aparece antes de sua mão deixar o item. O arquivo de produtos tem cinquenta milhões de linhas.
- Nada os pesquisou. O número do código de barras passou por um curto cálculo que produziu uma posição, e o computador leu aquela posição: uma leitura, nenhuma comparação, o mesmo tempo se o arquivo tem cinquenta linhas ou cinquenta milhões.
- O cálculo é uma função hash 散列函数, e toda a ideia se baseia nisso: não armazene dados onde caber, armazene-o onde sua própria chave diz que pertence.
- Esta lição é sobre algoritmos de hashing, o que acontece quando duas chaves querem o mesmo slot, e como pesquisar e inserir.
A função hash
- Uma função hash, ou algoritmo de hashing, pega a chave 键 de um registro e produz o endereço 地址 no qual o registro é armazenado.
- Uma boa é rápida, determinística 确定性 (a mesma chave sempre dá o mesmo endereço), e espalha chaves uniformemente pelos slots disponíveis.
- Para $N$ slots, os três que o currículo espera: modulo,
address ← key MOD N; folding, divida a chave em pedaços, some-os, depois MOD $N$; um string hash, some os códigos dos caracteres, depois MOD $N$.
Uma função hash:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma função hash mapeia uma chave para um endereço, habilitando consulta direta quase instantânea.
O que torna uma função hash boa? Selecione todas que se aplicam.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Rápida, determinística e uniformemente espalhada. Nenhuma função hash real evita colisões inteiramente, por isso todo projeto inclui uma estratégia de resolução.
Exemplo resolvido: aplique cada algoritmo
- Um arquivo tem 10 slots, numerados de 0 a 9. Onde vai a chave 4517?
- Modulo: $4517 \bmod 10 = 7$, então slot 7.
- Folding em pares: $45 + 17 = 62$, então $62 \bmod 10 = 2$, então slot 2.
- E a chave "CAB" por um string hash? $67 + 65 + 66 = 198$, então $198 \bmod 10 = 8$, então slot 8.
- Mostre a aritmética. A nota é pelo cálculo, não pelo número do slot sozinho.
Usando o hash módulo address ← key MOD N com key = 27 e N = 10, qual endereço é produzido?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
27 MOD 10 = 7 (o resto quando 27 é dividido por 10).
Uma tabela tem 10 slots. Usando folding em pares na chave 4517 (somar 45 e 17, depois MOD 10), em qual slot ela vai?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
45 + 17 = 62, e 62 MOD 10 = 2. A mesma chave sob um hash módulo iria para o slot 7 em vez disso.
Colisões
- Uma colisão 冲突 acontece quando duas chaves diferentes hasham para o mesmo endereço. Com qualquer hashing e qualquer arquivo realista, colisões são certas, então uma estratégia para elas faz parte do projeto, não um após-pensamento.
- Linear probing 线性探测 coloca o registro no próximo slot livre, voltando ao início no fim da tabela. Simples, mas registros aglomeram: um bloco cheio cresce e toda chave que pousa nele leva mais tempo.
- Chaining 链接法 faz de cada slot a cabeça de uma lista ligada de todos os registros que hasharam lá. Sem aglomeração, mas memória extra para os ponteiros e uma caminhada curta pela lista.
- Rehashing aplica uma segunda função hash para encontrar outro slot, espalhando chaves melhor à custa de mais computação.
Uma colisão ocorre quando:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Duas chaves mapeando para o mesmo slot é uma colisão; deve ser resolvida por probing, chaining ou rehashing.
Associe cada ideia de resolução de colisão ao que ela faz.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Colisões são resolvidas por chaining ou probing; manter o fator de carga baixo mantém consultas próximas de O(1).
Pesquisando e inserindo
- Para inserir: hash a chave. Se o slot estiver livre, escreva o registro lá. Se não, siga a estratégia de resolução, o próximo slot livre para linear probing, ou a frente da lista daquele slot para chaining.
- Para pesquisar: hash a chave e leia aquele slot. Se a chave armazenada corresponder, o registro é encontrado. Se não, siga a mesma estratégia, até que as chaves correspondam ou um slot vazio prove que o registro não está no arquivo.
- Ambas as operações usam a mesma estratégia. Uma pesquisa que parar no primeiro desajuste perderia todo registro que já foi deslocado por uma colisão.
Exemplo resolvido: rastreie uma colisão
- Uma tabela de 10 slots usa
key MOD 10com linear probing. Insira 23, 33, 43 nessa ordem, depois pesquise por 43. - 23 hasha para 3; slot 3 está livre, então vai lá. 33 hasha para 3; slot 3 está ocupado por 23, então linear probing o coloca no slot 4. 43 hasha para 3; slots 3 e 4 estão ocupados, então vai no slot 5.
- Pesquisando por 43: hasha para 3, lê slot 3, chave é 23, não corresponde, então probe; slot 4 contém 33, não corresponde; slot 5 contém 43, encontrado, após três leituras.
- Aquela sequência crescente de três é a aglomeração que linear probing causa.
Haqueie cada chave diretamente em um bucket
Uma função hash transforma uma chave em um número de bucket, para que você vá direto ao registro em vez de buscar. Quando duas chaves caem no mesmo bucket, isso é uma colisão — elas formam uma cadeia naquele bucket.
Ao buscar em uma tabela hash, o registro não está no arquivo assim que o primeiro slot lido contém uma chave diferente.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O registro pode ter sido deslocado por uma colisão. A busca segue a mesma estratégia de resolução até encontrar uma correspondência ou um slot vazio.
Fator de carga
- O fator de carga 装填因子 é o número de registros dividido pelo número de slots. É o único número que prediz quão bem a tabela performará.
- Abaixo de cerca de 70% a busca média é próxima de uma leitura. Acima dela, sequências de probes alongam-se drasticamente e o desempenho degrada em direção a uma busca linear.
- A correção é tornar a tabela maior e rehashar todos os registros nela, que é por isso que uma tabela hash é dimensionada para os dados que ela conterá, não os dados que ela tem hoje.
Uma tabela de 10 slots usa key MOD 10 com linear probing. Após inserir 23, 33 e 43 nessa ordem, qual slot contém 43?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Todos hasham para 3. 23 ocupa o slot 3, 33 é probeado para 4, e 43 para 5. Três chaves seguidas é exatamente o clustering que a linear probing causa.
Marcas que escapam
- Uma colisão é duas chaves, um endereço. Não é um erro nem um registro perdido; é o caso normal que uma estratégia lida.
- Uma pesquisa deve seguir a mesma estratégia de resolução que a inserção, e parar apenas em uma correspondência ou um slot vazio.
- Linear probing aglomera; chaining custa memória. Dê o trade-off, não apenas o mecanismo.
- O fator de carga é registros divididos por slots, e o limiar é cerca de 70%, não 100%.
Para manter as buscas em hash rápidas, o fator de carga (registros ÷ slots) deve ser mantido:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Um fator de carga menor significa menos colisões, mantendo as buscas próximas a O(1).
Entendeu?
- uma função hash transforma uma chave em um endereço: rápida, determinística, espalhada uniformemente; modulo, folding e string hashes são os três para saber
- uma colisão é duas chaves hashando para um endereço, resolvida por linear probing (próximo slot livre, aglomerações), chaining (uma lista ligada por slot, mais memória) ou rehashing
- inserir e pesquisar seguem a mesma estratégia; uma pesquisa termina em uma correspondência ou um slot vazio
- mantenha o fator de carga, registros divididos por slots, abaixo de cerca de 70% para buscas de quase uma leitura