Please enable JavaScript.

Coggle requires JavaScript to display documents.

Space and Time Trade-Offs - Coggle Diagram

- - - - No open hashing , as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela hash.
        Cada lista contém todas as chaves com hash para sua célula
      - Em geral, a eficiência da pesquisa depende dos comprimentos dos links listas, que, por sua vez, dependem dos tamanhos do dicionário e da tabela, bem como da qualidade da função hash. Se a função hash distribuir n chaves entre m células do tabela hash aproximadamente uniformemente, cada lista terá cerca de n / m de chaves. A proporção α = n / m, chamado de fator de carga (load factor) da tabela de hash, desempenha um papel crucial na eficiência de hashing.
      - Normalmente, queremos que o fator de carga não esteja longe de 1. Tendo-o muito pequeno implicaria muitas listas vazias e, portanto, uso ineficiente do espaço; tendo que isso também significaria listas vinculadas mais longas e, portanto, tempos de pesquisa mais longos. Mas se nós temos o fator de carga em torno de 1, temos um esquema incrivelmente eficiente que possibilita a busca de uma determinada chave pelo preço médio de uma ou duas comparações! É verdade, além de comparações, precisamos gastar tempo calcular o valor da função hash para uma chave de pesquisa, mas é um tempo constante operação, independente de n e m. Observe que estamos obtendo este notáveleficiência não apenas como resultado da engenhosidade do método, mas também às custas de espaço extra.
      - As duas outras operações de dicionário - inserção e exclusão - são quase idêntico à pesquisa. As inserções são normalmente feitas no final de uma lista. A exclusão é realizada procurando uma chave a ser excluída e, em seguida, removendo de sua lista. Portanto, a eficiência dessas operações é idêntica à de procurando, e eles são todos (1) no caso médio se o número de chaves n for quase igual ao tamanho da tabela de hash m
    - - No closed hashing, todas as chaves são armazenadas na própria tabela de hash sem o uso de listas vinculadas. (Claro, isso implica que o tamanho da mesa m deve ser pelo menos igual grande quanto o número de chaves n.) Diferentes estratégias podem ser empregadas para resolução de colisão. O mais simples, chamado de linear probing, verifica a célula seguinte aquela onde ocorre a colisão. Se essa célula estiver vazia, a nova chave é instalada lá; se a próxima célula já estiver ocupada, a disponibilidade dessa imediata célula sucessora é verificada e assim por diante. Observe que se o fim da tabela de hash for alcançado, a pesquisa é ajustada ao início da tabela; ou seja, é tratado como uma circular variedade.