| English | Português |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | função hash |
| key/kiː/ | chave |
| address/əˈdres/ | endereço |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | determinista |
| collision/kəˈlɪʒn/ | colisão |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | sonda linear |
| chaining/ˈtʃeɪnɪŋ/ | encadeamento |
| load factor/ləʊd ˈfæktə/ | fator de carga |
Finding one row in fifty million without looking
- A supermarket till scans a barcode and the price appears before your hand leaves the item. The product file holds fifty million lines.
- Nothing searched them. The barcode number went through a short calculation that produced a position, and the computer read that position: one read, no comparisons, the same time whether the file holds fifty rows or fifty million.
- The calculation is a hash function 散列函数, and the whole idea rests on it: do not store data where it will fit, store it where its own key says it belongs.
- This lesson is hashing algorithms, what happens when two keys want the same slot, and how to search and insert.
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.
The hash function
- A hash function, or hashing algorithm, takes a record's key 键 and produces the address 地址 at which the record is stored.
- A good one is fast, deterministic 确定性 (the same key always gives the same address), and spreads keys evenly across the available slots.
- For $N$ slots, the three the syllabus expects: modulo,
address ← key MOD N; folding, split the key into pieces, add them, then MOD $N$; a string hash, add the character codes, then MOD $N$.
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$.
A hash function: · Uma função hash:
A hash function maps a key to an address, enabling near-instant direct lookup. · Uma função hash mapeia uma chave para um endereço, habilitando consulta direta quase instantânea.
What makes a hash function a good one? Select all · todos that apply. · O que torna uma função hash boa? Selecione todas que se aplicam.
Fast, deterministic and evenly spread. No realistic hash avoids collisions entirely, which is why every design includes a resolution strategy. · 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.
Worked example: apply each algorithm
- A file has 10 slots, numbered 0 to 9. Where does key 4517 go?
- Modulo: $4517 \bmod 10 = 7$, so slot 7.
- Folding in pairs: $45 + 17 = 62$, then $62 \bmod 10 = 2$, so slot 2.
- And the key "CAB" by a string hash? $67 + 65 + 66 = 198$, then $198 \bmod 10 = 8$, so slot 8.
- Show the arithmetic. The mark is for the calculation, not the slot number alone.
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.
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced? · Usando o hash módulo address ← key MOD N com key = 27 e N = 10, qual endereço é produzido?
27 MOD 10 = 7 (the remainder when 27 is divided by 10). · 27 MOD 10 = 7 (o resto quando 27 é dividido por 10).
A table has 10 slots. Using folding in pairs on key 4517 (add 45 and 17, then MOD 10), which slot does it go to? · Uma tabela tem 10 slots. Usando folding em pares na chave 4517 (somar 45 e 17, depois MOD 10), em qual slot ela vai?
45 + 17 = 62, and 62 MOD 10 = 2. The same key under a modulo hash would go to slot 7 instead. · 45 + 17 = 62, e 62 MOD 10 = 2. A mesma chave sob um hash módulo iria para o slot 7 em vez disso.
Collisions
- A collision 冲突 happens when two different keys hash to the same address. With any hash and any realistic file, collisions are certain, so a strategy for them is part of the design, not an afterthought.
- Linear probing 线性探测 puts the record in the next free slot, wrapping round to the start at the end of the table. Simple, but records cluster: a full patch grows and every key landing in it takes longer.
- Chaining 链接法 makes each slot the head of a linked list of all the records that hashed there. No clustering, but extra memory for the pointers and a short walk along the list.
- Rehashing applies a second hash function to find another slot, spreading keys better at the cost of more computation.
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.
A collision occurs when: · Uma colisão ocorre quando:
Two keys mapping to the same slot is a collision; it must be resolved by probing, chaining or rehashing. · Duas chaves mapeando para o mesmo slot é uma colisão; deve ser resolvida por probing, chaining ou rehashing.
Match each collision-handling idea to what it does. · Associe cada ideia de resolução de colisão ao que ela faz.
Collisions are resolved by chaining or probing; keeping the load factor low keeps lookups near O(1). · Colisões são resolvidas por chaining ou probing; manter o fator de carga baixo mantém consultas próximas de O(1).
Searching and inserting
- To insert: hash the key. If the slot is free, write the record there. If not, follow the resolution strategy, the next free slot for linear probing, or the front of that slot's list for chaining.
- To search: hash the key and read that slot. If the stored key matches, the record is found. If it does not, follow the same strategy, until either the keys match or an empty slot proves the record is not in the file.
- Both operations use the same strategy. A search that stops at the first mismatch would miss every record that was ever displaced by a collision.
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.
Worked example: trace a collision
- A table of 10 slots uses
key MOD 10with linear probing. Insert 23, 33, 43 in that order, then search for 43. - 23 hashes to 3; slot 3 is free, so it goes there. 33 hashes to 3; slot 3 is taken by 23, so linear probing puts it in slot 4. 43 hashes to 3; slots 3 and 4 are taken, so it goes in slot 5.
- Searching for 43: hash to 3, read slot 3, key is 23, not a match, so probe on; slot 4 holds 33, not a match; slot 5 holds 43, found, after three reads.
- That growing run of three is the clustering that linear probing causes.
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.
Hash each key straight to a bucket · Haqueie cada chave diretamente em um bucket
A hash function turns a key into a bucket number, so you jump straight to the record instead of searching. When two keys land in the same bucket that is a collision — they chain together in that 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.
When searching a hash table, the record is not in the file as soon as the first slot read holds a different key. · Ao buscar em uma tabela hash, o registro não está no arquivo assim que o primeiro slot lido contém uma chave diferente.
The record may have been displaced by a collision. The search follows the same resolution strategy until a match or an empty slot. · 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.
Load factor
- The load factor 装填因子 is the number of records divided by the number of slots. It is the single number that predicts how well the table performs.
- Below about 70% the average lookup is near one read. Above it, probe sequences lengthen sharply and performance degrades towards a linear search.
- The fix is to make the table larger and rehash every record into it, which is why a hash table is sized for the data it will hold, not the data it holds today.
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.
A 10-slot table uses key MOD 10 with linear probing. After inserting 23, 33 and 43 in that order, which slot holds 43? · 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?
All three hash to 3. 23 takes slot 3, 33 is probed to 4, and 43 to 5. Three keys in a row is exactly the clustering linear probing causes. · 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.
Marks that slip away
- A collision is two keys, one address. It is not an error and not a lost record; it is the normal case a strategy handles.
- A search must follow the same resolution strategy as the insert, and stop only on a match or an empty slot.
- Linear probing clusters; chaining costs memory. Give the trade-off, not just the mechanism.
- The load factor is records divided by slots, and the threshold is about 70%, not 100%.
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%.
To keep hash lookups fast, the load factor (records ÷ slots) should be kept: · Para manter as buscas em hash rápidas, o fator de carga (registros ÷ slots) deve ser mantido:
A lower load factor means fewer collisions, so lookups stay close to O(1). · Um fator de carga menor significa menos colisões, mantendo as buscas próximas a O(1).
You've got it
- a hash function turns a key into an address: fast, deterministic, evenly spread; modulo, folding and string hashes are the three to know
- a collision is two keys hashing to one address, resolved by linear probing (next free slot, clusters), chaining (a linked list per slot, more memory) or rehashing
- insert and search both follow the same strategy; a search ends on a match or an empty slot
- keep the load factor, records divided by slots, below about 70% for near one-read lookups
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