o que é hash table

[eduardo_souza]

O que é hash table e como usá-la em c++?

[Baderous]

http://en.wikipedia.org/wiki/Hash_table

[zecapistolas]

As hashtables com uma boa função de hash para evitar colisões, etc, para mim são a melhor coisa que existe para guardar/pesquisar dados no meio de uma grande quantidade de informação....

cumps  🙂

[Ferreira]

Excepto se precisares de manter os dados ordenados. 🙂

[fnds]

Excepto se precisares de manter os dados ordenados. 🙂

Podes sempre adicionar um campo "índice" e quando precisares de eles ordenados ires buscar os dados pela forma normal.

[zecapistolas]

Podes sempre adicionar um campo "índice" e quando precisares de eles ordenados ires buscar os dados pela forma normal.

Exacto.... Na altura que utilizei hash_tables utilizava como função de hash o id dos clientes (tratava-se de uma instituição bancária)....

cumps 🙂

[eduardo_souza]

Quando falei sobre a duvida de hash table, eu queria saber como usar e nao o que era. Não me interesso em saber o que, quero saber como usa isso.

[Guest id194]

Com essa atitude não vais longe...

E eu questiono-me, não te interessa saber o que é porque já tens conhecimento ou simplesmente não interessa? Porque se for a segunda, estás no mal caminho...

[pedrosorio]

Quando falei sobre a duvida de hash table, eu queria saber como usar e nao o que era. Não me interesso em saber o que, quero saber como usa essa m****

http://en.wikipedia.org/wiki/Hash_table#Uses

[fnds]

Quando falei sobre a duvida de hash table, eu queria saber como usar e nao o que era. Não me interesso em saber o que, quero saber como usa essa m****

O que é hash table e como usá-la em c++?

Bem eu sei que o meu português não é o melhor mas eu acho que "o que é hash table?" responde-se "hash table é". Recomendo-te moderação na linguagem "m****" não é apropriado para um forum deste.

[mogers]

Podes sempre adicionar um campo "índice" e quando precisares de eles ordenados ires buscar os dados pela forma normal.

Explica melhor como é que consegues obter os dados ordenados de uma forma eficiente sff. Este "campo índice" parece-me muito vago.

O que tinha pensado (e acho que se costuma usar) é uma árvore auxiliar com esta informação.

[bruno1234]

Existem umas colecções q ordem logo na inserção e são extremamente eficientes.

No caso do C# tens por exemplo o SortedSet, em java tb há um set q faz isso.

Em c++ não me lembro, mas pesquisa por Set em c++, pode ser q encontres alguma coisa.

[pedrotuga]

Uma hashtable é uma estrutura de dados, não é um propriamente uma peça de software. Uma implementação de uma hashtable que inclua coisas como índices numéricos e afins, deixa de ser uma hashtable para ser tambem outra coisa.

Outra coisa que acho curiosa é que quando se fala nestes temas vem sempre o pessoal com a questão da performance e dos microsegundos que se podem poupar ou de algumas dezenas de bytes por se usar esta ou aquela estrutura de dados.

Têm noção que em 95%+ dos casos, o que se ganha em termos de facilidade de implementação é ridiculamente mais significativo que esses milisegundos?

Exemplo, se quiseres por exemplo manipular dados com índices literais, podes usar uma hashtable para tornares o código mais claro e mais facil.

Exemplo

$calorias[pera] = 40000;
$calorias[chocolate] = 15000;
$calorias[agua] = zero

$alimento = 'chocolate'

print "o alimento ".$alimento." tem ". $calorias[$alimeto] . "calorias.";

acho que isto é bem mais claro do que andar com índices numéricos para trás e para a frente. Se é mais rápido, tenho que chamar ou o flash ou o super-homem e perguntar-lhes.

[mogers]

Existem umas colecções q ordem logo na inserção e são extremamente eficientes.

No caso do C# tens por exemplo o SortedSet, em java tb há um set q faz isso.

Em c++ não me lembro, mas pesquisa por Set em c++, pode ser q encontres alguma coisa.

Em C++ existe a classe set da STL. É eficiente, mas pode não ser suficiente. Uma hash table é muito mais eficiente para inserções e pesquisas (e.g. para dicionários), mas, a meu ver, não para obter os elementos ordenados.

Outra coisa que acho curiosa é que quando se fala nestes temas vem sempre o pessoal com a questão da performance e dos microsegundos que se podem poupar ou de algumas dezenas de bytes por se usar esta ou aquela estrutura de dados.

Pedrotuga, isso depende sempre o tamanho do problema. Para problemas relativamente pequenos pode ser irrelevante usar uma ou outra coisa. Claro que se deve optar pelo mais simples possível. No entanto, considerando um dicionário, se tiveres 100.000 ou 1.000.000 palavras a diferença não é simplesmente de milisegundos e pode condicionar a tua aplicação.

edit:  já agora, aproveito para recordar um post de um empregado da google, onde disse que tava a procurar formas de melhorar um algoritmo de O(N log N) para O( N ). Desta forma, poupariam 1 mês!! de processamento 🙂

[pedrotuga]

Sim tudo bem, mas tipo, as hashtables são usadas em 99% dos casos por motivos de simplicidade de código como o que indiquei. Raríssimas são as vezes que questões de performance ditam a sua utilização. Eu uso hashtables diariament e não me lembro de uma vez que o tenha feito por motivos de performance. No entanto 90%+ das discussões são sobre a sua performance.

É falhar o alvo. Keep it simple, not fancy.