Quais são hashtables e HashMaps e seus casos de uso típicos?

Question

Tenho recentemente se deparar estes termos algumas vezes, mas estou bastante confuso como eles funcionam e quando eles são usualy implementado?

Answer 1

Bem, pense nisso desta maneira.

Se você usar uma matriz, uma estrutura de dados com base em índices simples, e preenchê-lo com coisas aleatórias, encontrar uma entrada específica chega a ser uma operação mais e mais caros como você preenchê-lo com dados, desde que você basicamente tem que iniciar a busca de um extremo para o outro, até encontrar o que deseja.

Se você deseja obter um acesso mais rápido aos dados, você typicall recorrer a classificação da matriz e usando uma pesquisa binária. Isso, no entanto, enquanto aumenta a velocidade de olhar para cima um valor existente, facilita a inserção de novos valores lento, como você precisa mover elementos existentes em torno de quando você precisa inserir um elemento no meio.

A hashtable, por outro lado, tem uma função associada que leva uma entrada, ea reduz a um número, uma chave hash. Este número é então utilizado como um índice para a matriz, e isso é onde você armazenar a entrada.

A gira hashtable em torno de um array, que começa inicialmente fora vazia. Vazio não significa comprimento zero, a matriz começa com um tamanho, mas todos os elementos na matriz não contém nada.

Cada elemento tem duas propriedades, dados e uma chave que identifica os dados. Por exemplo, uma lista de zip códigos dos EUA seria um zip-code -> tipo de nome da associação. A função reduz a chave, mas não considera os dados.

Assim, ao inserir algo na tabela de dispersão, a função reduz a chave para um número, o qual é usado como um índice para esta matriz (vazio), e esta é onde armazenar os dados, tanto a chave, e o associado dados.

Depois, mais tarde, você quer encontrar uma entrada específica que você sabe a chave para, então você executar a chave através da mesma função, obter seu hash-chave, e vai para aquele lugar especial na hashtable e recupera os dados lá.

A teoria é que a função que reduz a chave para uma chave de hash, esse número, é computacionalmente muito mais barato do que a busca linear.

Uma tabela hash típico não tem um número infinito de elementos disponíveis para o armazenamento, de modo que o número é tipicamente reduzido ainda mais para baixo a um índice que se encaixa no tamanho da matriz. Uma maneira de fazer isso é simplesmente ter o módulo do índice em comparação com o tamanho da matriz. Para uma disposição com um tamanho de 10, o índice de 0-9 vai mapear directamente a um índice, e índice de 10-19 irão mapear-se a 0-9 de novo, e assim por diante.

Algumas chaves serão reduzidos para o mesmo índice como uma entrada existente na tabela hash. Neste ponto, as chaves reais são comparados diretamente, com todas as regras associadas a comparação entre os tipos de dados da chave (ie. Comparação de string normal, por exemplo). Se houver um jogo completo, você quer ignorar os novos dados (que já existe) ou substituir (substituir os dados antigos para essa chave), ou adicioná-lo (hashtable vários valores). Se não houver correspondência, o que significa que, embora as chaves de hash era idêntico, as chaves reais não eram, normalmente você encontrar um novo local para armazenar esses dados de chave + em.

resolução

Collision tem muitas implementações, e o mais simples é apenas para ir para o próximo elemento vazio na matriz. Esta solução simples tem outros problemas, porém, assim que encontrar o algoritmo de resolução direito também é um bom exercício para hashtables.

Hashtables também podem crescer, se eles encher-se completamente (ou perto), e isso geralmente é feito através da criação de uma nova matriz do novo tamanho, e calcular todos os índices mais uma vez, e colocar os itens para a nova matriz em seus novos locais.

A função que reduz a chave para um número não produz um valor linear, ou seja. "AAA" torna-se 1, então "AAB" torna-se 2, de modo que o hashtable não é classificada por qualquer valor típico.

Há um artigo bom wikipedia disponível sobre o assunto, bem como, aqui .

Answer 2

A resposta de lassevk é muito bom, mas pode conter um pouco demais detalhes. Aqui é o sumário executivo. Estou omitindo intencionalmente certa relevantes informações que você pode ignorar 99% do tempo.

Existe nenhuma diferença importante entre tabelas de hash e de hash mapeia 99% do tempo.

As tabelas de hash são mágicos

A sério. É uma estrutura de dados mágico que todos, mas garante três coisas . (Há exceções. Você pode, em grande parte ignorá-los, apesar de aprendê-las algum dia pode ser útil para você.)

1) Tudo na tabela hash é parte de um par - há um tecla e valor . Você colocar em e sair de dados, especificando a chave que você está operando.

2) Se você está fazendo nada por uma única chave em uma tabela hash, é incrivelmente rápido . Isto implica que put(key,value), get(key), contains(key) e remove(key) são todos muito rápido.

3) tabelas de hash genérico falhar em fazer qualquer coisa que não constam do nº 2 ! (Por "falha", que significa que eles são incrivelmente lento.)

Quando usamos tabelas de hash?

Nós usamos tabelas hash quando a sua magia se encaixa em nosso problema.

Por exemplo, cache frequentemente acaba usando uma tabela hash - por exemplo, vamos dizer que tem 45.000 estudantes em uma universidade e algumas necessidades de processo para segurar registros para todos eles. Se você consultar rotineiramente para estudante por número de ID, em seguida, um cache ID => student faz excelente sentido. A operação que você está otimizando para este cache é rápida pesquisa .

Hashes também são extraordinariamente útil para armazenamento de relações entre dados quando você não querem ir porco inteiro e alterar os objetos em si. Por exemplo, durante a inscrição do curso, pode ser uma boa idéia para ser capaz de relacionar os alunos para as classes que estão tomando. No entanto, por qualquer motivo você não pode querer o objeto Student-se de saber sobre isso. Use um hash studentToClassRegistration e mantê-lo por perto enquanto você faz tudo o que você precisa fazer.

Eles também fazer uma bastante boa primeira escolha para uma estrutura de dados , exceto quando você precisa fazer um dos seguintes procedimentos:

Quando não usar tabelas de hash

iterar sobre os elementos . As tabelas de hash normalmente não fazem iteração muito bem. (Os genéricos, isto é. Implementações particulares, por vezes, contêm listas ligadas que são usados ??para fazer a iteração sobre eles sugam menos. Por exemplo, em Java, LinkedHashMap permite interagir sobre chaves ou valores rapidamente.)

Sorting. Se você não pode iterar, a triagem é uma dor real, também.

Indo de valor a tecla . Use dois tabelas de hash. Confie em mim, eu só salvou um monte de dor.

Answer 3

Se você está falando em termos de Java, ambos são coleções que permitem objetos adição, exclusão e updation e uso Hasing algoritmos internamente.

A diferença significativa no entanto, se falamos em referência ao Java, é que hashtables são inerentemente sincronizado e, portanto, são thread-safe, enquanto os mapas hash não são thread coleção de seguro.

Além da sincronização, o mecanismo interno para armazenar e recuperar objetos é hash em ambos os casos.

Se você precisa ver como hashing funciona, eu recomendo um pouco de googling em dados Structers e técnicas de hashing.

Answer 4

Hashtables / HashMaps associar um valor (chamado 'chave' para fins de desambiguação) com outro valor. Você pode pensar-los como uma espécie de dicionário (palavra: definição) ou um registro de banco de dados (chave: dados).