Question

int P( char *s, int tablesize) {
return s[0] % tablesize;
}

int S( char *s, int tablesize) {
int sum = 0;
for (char *p = s; *p; p++)

sum = (sum + *p) % tablesize;

return sum; }

As alternativas comparam as duas funções em relação à conveniência de serem usadas como função de hash, considerando o tempo de busca médio. Marque a alternativa FALSA.

Accepted Answer

D) O problema descrito em C) pode ser resolvido, fazendo com que a ocupação da tabela de hash seja uniforme, bastando aumentar o tamanho da tabela de hash, definindoo como o próximo número primo. E.g., se o tamanho era 1000, o mudamos para 1009.

Answer

A) S será provavelmente melhor que P, pois em muitos casos comuns, há muito mais strings que iniciam com alguns caracteres do que com outros. Um exemplo válido são palavras em português: há muitas palavras iniciando com ‘a’.

Answer

B) S permite aumentar o tamanho da tabela de hash arbitrariamente, enquanto para P, se o tamanho da tabela de hash for maior que o número de caracteres do alfabeto, algumas posições (buckets) serão pouco ocupadas.

Answer

C) Suponha que todas as strings contém apenas caracteres maiúsculos. Se aumentarmos o tamanho da tabela até milhares de posições, a ocupação da tabela de hash será pouco uniforme. Porque as somas dos caracteres estarão concentradas em torno dos múltiplos do valor médio dos caracteres.

Answer

E) Se as strings armazenadas são sempre aleatórias, por exemplo, são sempre senhas geradas aleatoriamente, P e S podem ter, na média, desempenho equivalente em termos de colisões. Mas nesse caso, P é O(1) enquanto S é O(n).

Mais questões de Criptografia