Os fundamentos de tabelas de hash?

https://stackoverflow.com/questions/282712

08-07-2019
|

Pergunta

Eu estou muito confuso sobre os conceitos básicos de uma tabela hash. Se eu fosse para código um hash como eu ia começar? Qual é a diferença entre uma tabela hash e apenas uma matriz normal?

Basicamente, se alguém respondeu a esta pergunta eu acho que todas as minhas perguntas seriam respondidas: Se eu tivesse 100 números gerados aleatoriamente (como chaves), como eu iria implementar uma tabela hash e por que isso seria vantajoso sobre um array?

Psuedo-código ou Java seria apreciada como uma ferramenta de aprendizagem ...

Solução

As respostas até agora ajudaram a definir tabelas de hash e explicar alguma teoria, mas eu acho que um exemplo pode ajudá-lo a obter uma sensação melhor para eles.

O que é a diferença entre uma tabela hash e apenas uma matriz normal?

Uma tabela e uma série são duas estruturas que lhe permitem armazenar e recuperar dados. Ambos permitem que você especifique um index e recuperar um valor associado a ele. A diferença, como Daniel Spiewak notado, é que os índices de uma matriz são sequencial , enquanto que as de uma mesa de hash são baseadas no valor dos dados que lhes estão associados.

Por que eu usaria uma tabela hash?

Uma tabela pode fornecer uma maneira muito eficiente para procurar itens em grandes quantidades de dados, especialmente dados que não é de outra forma facilmente pesquisável. ( "Large" aqui significa ginormous , no sentido de que seria levar um longo tempo para realizar uma pesquisa seqüencial).

Se eu fosse código hash como eu ia começar?

Não há problema. A maneira mais simples é inventar uma operação matemática arbitrária que você pode executar nos dados, que retorna um N número (geralmente um inteiro). Em seguida, usar esse número como o índice em uma matriz de "baldes" e armazenar seus dados em #N balde. O truque está em escolher uma operação que tende a valores de lugar em diferentes baldes de uma forma que torna mais fácil para o seu para encontrá-los mais tarde.

Exemplo: Um grande centro mantém um banco de dados de carros dos seus clientes e locais de estacionamento, para ajudar os compradores se lembrar onde estacionou. O banco de dados armazena make, color, license plate e parking location. Ao sair da loja de um cliente encontra o seu carro, digitando o seu make e cor. O banco de dados retorna uma lista (relativamente curto) de placas e lugares de estacionamento. A Localiza digitalização carro do comprador rápido.

Você poderia implementar isso com uma consulta SQL:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

Se os dados foram armazenados em uma matriz, que é essencialmente apenas uma lista, você pode imaginar implementar a consulta digitalizando uma matriz para todas as entradas correspondentes.

Por outro lado, imagine uma regra de hash:

Adicione os códigos de caracteres ASCII de todas as letras na marca e cor, dividir por 100, e usar o restante como o valor hash.

Essa regra irá converter cada item para um número entre 0 e 99, essencialmente classificação os dados em 100 baldes. Cada vez que um cliente precisa para localizar um carro, você pode botar a marca e cor para encontrar o um balde fora de 100 que contém as informações. Você imediatamente reduzido a busca por um fator de 100!

Agora escalar o exemplo de grandes quantidades de dados, digamos, um banco de dados com milhões de entradas que é pesquisado com base em dezenas de critérios. A "boa" função hash irá distribuir os dados em baldes de uma forma que minimiza qualquer pesquisa adicional, economizando uma quantidade significativa de tempo.

Outras dicas

Em primeiro lugar, você tem que entender a que uma função hash é. A função hash é uma função que recebe uma chave (por exemplo, uma cadeia de comprimento arbritrary) e retorna um número como único possível . A mesma chave deve retornar sempre o mesmo hash. Uma função muito simples seqüência de hash em java pode parecer

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

Você pode estudar uma boa função hash em http://www.azillionmonkeys.com/qed/ hash.html

Agora, o mapa de hash usa esse valor de hash para colocar o valor em uma matriz. método java simplista:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(Este mapa impõe chaves únicas. Nem todos os mapas fazem.)

É possível que duas chaves diferentes para hash para o mesmo valor, ou dois hash diferentes para mapear o mesmo índice de matriz. Existe muitas técnicas para lidar com isso. O mais simples é usar uma lista ligada (ou árvore binária) para cada índice da matriz. Se a função hash é bom o suficiente, você nunca terá uma busca linear.

Agora, para procurar uma chave:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Hashtables são associativo . Esta é uma enorme diferença de matrizes, que são estruturas de dados apenas lineares. Com uma matriz, você pode fazer algo como isto:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

Observe como você está recebendo um elemento do array especificando um deslocamento de memória exata (i). Isto contrasta com hashtables, que lhe permitem armazenar pares de chave / valor, mais tarde, recuperando o valor com base na chave:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

Com a tabela acima, podemos fazer a seguinte chamada:

int n = table.get("Chris");

... e ter a certeza de que n será avaliado em 18.

Eu acho que isso provavelmente irá responder a maioria das suas perguntas. A implementação de uma tabela hash é um tema bastante interessante, um quais endereços Wikipédia razoavelmente bem .

"Eu estou mais interessado na maneira Hash Tables procurar a chave e como a chave é gerada."

Hashing transforma um objeto chave para um número. Isso é chamado de "hash" - faz um hash fora do objeto. Consulte função Hash . Resumindo os bytes de um texto, por exemplo, é uma técnica de hash padrão. Você calcular a soma modulo 2 ³² para manter o hash a um tamanho administrável. Hash sempre dá a mesma resposta. Este é O (1).
O número dá-lhe uma "fenda" no HashTable. Dado um objeto chave arbitrária, o valor de hash calcula um valor hash. O valor de hash, em seguida, dá-lhe o slot na tabela. Normalmente mod( hash, table size ). Este é O (1), também.

Essa é a solução geral. Dois cálculos numéricos e você fomos de objeto arbitrária como chave para o objeto arbitrário como valor. Poucas coisas podem ser tão rápido.

A transformação do objeto para o valor de hash acontece em uma dessas maneiras comuns.

Se é um objeto "primitivo" de 4 bytes, então o valor nativo do objeto é um número.
O endereço do objecto é de 4 bytes, em seguida, o endereço do objecto pode ser utilizado como um valor de hash.
Um simples função hash (MD5, SHA1, qualquer que seja) acumula os bytes de o objectivo de criar um número de 4 bytes. Os hashes avançadas não são somas simples de bytes, uma soma simples não reflete todos os bits de entrada originais bastante suficiente.

A ranhura na tabela hash é mod (número, tamanho da tabela).

Se esse slot tem o valor desejado, você está feito. Se isso não é o valor desejado, você precisa procurar em outro lugar. Existem vários algoritmos populares de sondagem para procurar um local livre na tabela. Linear é uma busca simples para o próximo local livre. Quadrática é um não-linear pulando por aí procurando um slot livre. Um gerador de número aleatório (com uma semente fixo) pode ser usado para gerar uma série de sondas que vão espalhar uniformemente dados mas arbitrariamente.

Os algoritmos de sondagem não são O (1). Se grande o suficiente da tabela, as chances de colisão são baixos, e sondas não importam. Se a tabela é muito pequena, então as colisões acontecem e sondagem acontece. Nesse ponto, torna-se uma questão de "tuning e ajustes" ao equilíbrio sondagem e tamanho da tabela para otimizar o desempenho. Normalmente, nós apenas fazer a tabela maior.

Hash Table .

Algo que eu não vi ainda especificamente observou:

O ponto de usar uma tabela hash sobre uma disposição é o desempenho.

iteração através de uma matriz que tipicamente ter lugar a partir de O (1) a O (x) em que x é o número de itens na matriz. No entanto, o tempo para encontrar o seu item será extremamente variável , especificamente se estamos a falar de centenas de milhares de itens na matriz.

A tabela hash devidamente ponderada normalmente tem quase constante tempo de acesso de pouco mais de O (1), não importa quantos itens estão na tabela de hash.

Você não gostaria de usar uma tabela hash para 100 números gerados aleatoriamente.

Uma boa maneira de pensar sobre tabelas hash é pensar em pares de valores. Os alunos usam deixou-nos, e dizer toda a gente tem um número de identificação do aluno. Em seu programa você armazenar informações sobre os alunos (nomes, números de telefone, contas, etc). Você quer encontrar todas as informações sobre um estudante que usa apenas as informações básicas (nome ou estudante ID, por exemplo).

Vamos dizer que você tem 10.000 estudantes. Se você armazená-los todos em uma matriz, então você tem que percorrer toda a matriz comparando carteira de estudante de cada entrada com o que você está procurando.

Se, em vez disso, você "haxixe" (veja abaixo) o seu número de identificação de estudante para uma posição na matriz, então você só tem que procurar estudante é quem está números têm o mesmo hash. Muito menos trabalho para encontrar o que queria.

Neste exemplo, digamos que IDs de estudante são apenas 6 dígitos números. Nossa função hash pode ser usado apenas o fundo de 3 dígitos do número que o "chave de hash". Assim 232145 é hash para o local de matriz 145. Então você só precisa de um conjunto de 999 elementos (cada elemento sendo uma lista de alunos).

Isso deve ser um bom começo para você. Você deve, é claro, ler um livro de texto ou wikipedia para este tipo de informação. Mas eu suponho que você já fez isso e está cansado de leitura.

Aqui está, em suma, como uma tabela hash obras.

Imagine que você tem uma biblioteca, cheia de livros. Se você fosse para armazenar os livros em uma matriz, você iria colocar cada livro em um ponto em uma prateleira, e então, quando alguém lhe pediu para encontrar um livro, você iria olhar através de todas as prateleiras - muito lento. Se alguém disse "livro # 12345", você pode encontrá-lo muito facilmente, no entanto.

Vamos digamos vez que você diz, se o título do livro começa com 'A', que vai na linha 1. Se a segunda letra é 'B', que vai na linha 1, rack 2. Se a terceira carta é 'C ', ele vai na linha 1, rack 2, prateleira 3 ... e assim por diante até que você identificar a posição livro. Então, com base no título do livro, você pode saber exatamente onde deveria estar.

Agora, existem alguns problemas no algoritmo simplista "hashing" que eu descrevi - algumas prateleiras vão ser maneira sobrecarregado enquanto outros estão vazias, alguns livros serão designados para o mesmo slot .. então as funções reais de hash são cuidadosamente construída para tentar evitar tais problemas.

Mas esta é a idéia básica.

Eu vou responder a essa parte sobre a diferença entre uma tabela hash e uma série ... mas desde que eu nunca implementado um algoritmo de hash de qualquer importação antes, eu vou deixar isso para alguém mais entendido:)

Uma matriz é apenas uma lista ordenada de objetos. O objeto em si realmente não importa ... o que é importante é que se você deseja listar os objetos em ordem de inserção, é sempre o mesmo (o que significa que o primeiro elemento sempre tem um índice de 0).

Como para uma tabela hash, que é indexado por chaves, não fim ... Eu acho que uma pesquisa básica em algoritmos de hash lhe dará muito mais conhecimento do que eu posso ... Wikipedia tem um muito decente ... que determina "balde" que as chaves entrar para recuperação rápida de objetos arbitrários utilizados como chaves.

Quanto a vantagens: Se ordem de inserção é importante, uma matriz ou algum tipo de lista ordenada é necessário. Se rápido look-up pela chave arbitrária (chaveado por várias funções hash) é importante, em seguida, uma tabela hash faz sentido.

[Esta é a resposta a um comentário feito por me.yahoo.com/a acima]

Isso depende de sua função hash. Vamos supor que a sua função hash hashes uma palavra de acordo com a duração da sua palavra, a chave para chris será 5. Da mesma forma, chave para yahoo também será 5. Agora, ambos os valores (chris e Yahoo) irá sob 5 (ie num 'balde' keyed por 5). Desta forma, você não tem que fazer uma série igual ao tamanho de seus dados.

A questão, creio eu, é respondida com clareza e de muitas maneiras diferentes até agora.

Eu gostaria apenas de acrescentar uma outra perspectiva (que pode confundir um novo leitor também)

Em um nível de menos abstração, matrizes são apenas bloco contíguo de memória. Dado o endereço inicial (startAddress), tamanho (sizeOfElement) eo index de um único elemento, o endereço do elemento é calculado como:

elementAddress = startAddress + sizeOfElement * index

A coisa interessante notar aqui é que matrizes podem ser abstraída / visto como tabelas de hash com index como chave e a função acima como uma função hash que calcula a localização de um valor em O (1)

tabela de Hash é uma estrutura de dados que é criado para olhar rápido para cima.

As tabelas hash não são eficazes quando o número de entradas são muito pequenas.

referência

Alguns exemplos:

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

Output:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow