Tabela hash - Problema com Chave duplicada

13 de junho de 2007 5 respostas

hugomalta 13 de junho de 2007

Tenho que fazer um trabalho onde tenho que ler um arquivo de pares de palavras. Só que pode haver a situação onde a primeira palavra pode vir em duas linhas. Quando tento mapear usando Hashtable ou Map não aceita dois mapeamentos com mesma chave.

Segue exemplo:

Hashtable m1 = new Hashtable();
		
	    m1.put("A", "Um");
	    m1.put("B", "Dois");
	    m1.put("C", "Tres");
	    m1.put("B", "Quatro");

	    System.out.println(m1.toString());
	    //Saída: {A=Um, C=Tres, B=Quatro}
	    //"B" foi sobrescrevido

Alguem pode me indicar alguma direção ?

Obrigado!

5 Respostas

ViniGodoy 13 de jun. de 2007

E é justamente para isso que um HashMap serve.

A alternativa é você fazer um HashMap associado a um list.

Map&lt;String, List&lt;String&gt;&gt m1 = new HashMap&lt;String, List&gt;&lt;String&gt;&gt();

List&lt;String&gt; linhas = m1.get("A");
if (linhas == null) {
   linhas = new ArrayList&lt;String&gt;();
   m1.put("A", linhas);
}

linhas.put("UM");

Assim, você cria um mapa que associa a palavra a uma lista de linhas. :)

thingol 13 de jun. de 2007

Em C++ há o template map&lt&gt (correspondente ao java.lang.TreeMap&lt&gt) e o template multimap&lt&gt (que não tem correspondente). O problema do multimap é que ele é um pouco "desajeitado". Comparando o multimap com o Map<String, List><String>&gt apresentado pelo Vinigodoy, prefiro a opção Java. Dou um exemplo depois.

hugomalta 13 de jun. de 2007

Valeu pelas dicas pessoal!

Neste momento estou no trabalho e meu horário de almoço já acabou.

Assim que tiver oportunidade eu vou fazer os testes!

Caso eu encontre dificuldades eu passo para os próximos itens do trabalho, assim eu não fico parado em um problema sendo que o restante eu consigo fazer!

Abraço!

ViniGodoy 13 de jun. de 2007

Eu concordo com você. Também não tenho uma experiência das melhores com o multimap. Outra coisa que acho legal das Collections em relação a STL é o fato delas respeitarem uma hierarquia lógica de classes. As do C++ são pouco relacionadas, até porque um dos objetivos dela (bem atingido por sinal) era ter uma performance absurdamente rápida, com o menor footprint possível.

thingol 13 de jun. de 2007

As coisas esquisitas do multimap:

a) Você usa muito o template "pair" para representar uma estrutura de dados "chave, valor".
b) Você tem que usar um método chamado "equal_range", que volta um par de iteradores.
c) E só para deixar o exemplo um pouco mais enigmático: descubra as espécies de animais que usei para o exemplo. Wallabia bicolor é um simpático bichinho da Austrália (o wallaby), que lembra um canguru de brinquedo.

#include &lt;map&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
using namespace std;

typedef multimap&lt;string,string&gt; MMSS;
typedef pair&lt;string,string&gt; PAIR;

int main (int argc, char *argv[]) {
    MMSS mmss;
    //-- Inserindo no multimap
    mmss.insert (PAIR ("Macropodidae", "Aepyprymnus rufescens"));
    mmss.insert (PAIR ("Macropodidae", "Wallabia bicolor"));
    mmss.insert (PAIR ("Macropodidae", "Macropus agilis"));
    mmss.insert (PAIR ("Edentata", "Euphractus sexcinctus"));
    mmss.insert (PAIR ("Didelphidae", "Didelphis marsupialis"));
    mmss.insert (PAIR ("Didelphidae", "Philander opossum"));
    mmss.insert (PAIR ("Didelphidae", "Didelphis virginiana"));
    //-- Listando o "multimap". Isto é parecido com o seguinte código Java:
    // for (Map.Entry&lt;String,String&gt; entry : mmss.entrySet()) {
    //    System.out.println (entry.getKey() + "," + entry.getValue());
    // }
    // Você pode ver que o multimap é como se fosse um TreeMap &lt;String, ArrayList &gt;&lt;String&gt; &gt
    cout &lt&lt &quot;Listando o multimap&quot; &lt&lt endl;
    for (MMSS::const_iterator it = mmss.begin(); it != mmss.end(); ++it) {
        cout &lt&lt it-&gt first &lt&lt &quot;,&quot; &lt&lt it-&gt second &lt&lt endl;
    }
    cout &lt&lt &quot;.&quot; &lt&lt endl;
    //-- Listando os elementos da chave &quot;Macropodidae&quot;.
    cout &lt&lt &quot;Listando apenas os Macropodidae&quot; &lt&lt endl;
    pair&lt;MMSS::const_iterator, MMSS::const_iterator&gt; macropodidae = mmss.equal_range (&quot;Macropodidae&quot;);
    for (MMSS::const_iterator it = macropodidae.first; it != macropodidae.second; ++it) {
        cout &lt&lt it-&gt first &lt&lt &quot;,&quot; &lt&lt it-&gt second &lt&lt endl;
    }
    cout &lt&lt &quot;.&quot; &lt&lt endl;
    
}

Criado 13 de junho de 2007

Ultima resposta 13 de jun. de 2007

Respostas 5

Participantes 3

5 Respostas

Topicos relacionados