Algoritmo de Hashing: Excluindo um elemento em sondagem linear

5

Ao usar o método de sondagem linear para implementar hashing, quando excluímos e elemento, a posição do elemento excluído é declarada como uma marca de exclusão / marca como excluída. Por que não podemos simplesmente mudar todos os elementos da posição atual até que o próximo elemento vazio seja encontrado? Isso não salvará o tempo em que muitas lápides são encontradas mais tarde e uma reformulação pode ser necessária? Estou esquecendo de algo? Por favor, diga-me se preciso esclarecer minha pergunta.

Muito obrigado!

    
por P Ramesh 23.08.2013 / 19:45
fonte

1 resposta

7

Melhor explicado pelo contra-exemplo:

HASH(A) = 10
HASH(B) = 10
HASH(C) = 12

myHash.insert(A); // A goes to slot 10

              10   11   12
            +----+----+----+
            | A  |    |    |
            +----+----+----+

myHash.insert(B); // B goes to slot 10, but that is taken, so it sees 11 is empty and inserts there

              10   11   12
            +----+----+----+
            | A  | B  |    |
            +----+----+----+

myHash.insert(C); // C hashes to slot 12 and gets put there

              10   11   12
            +----+----+----+
            | A  | B  | C  |
            +----+----+----+

myHash.remove(B); // We remove B, and shift the ones after it back

              10   11   12
            +----+----+----+
            | A  | C  |    |
            +----+----+----+

myHash.contains(C) == false; // C hashes to slot 12, but there is nothing there.  So therefore the hash does not contain C (but it does CONTRADICTION).

Portanto, por prova de contradição, simplesmente deslizar os elementos subsequentes após a remoção resultará em incorreção.

EDIT : C deveria ter dito que hashes para 12

    
por 23.08.2013 / 20:02
fonte