1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Problema com o rehash() em Java

Discussão em 'Programação' iniciada por solidforms, 15 de Novembro de 2008. (Respostas: 22; Visualizações: 2512)

Estado do Tópico:
Fechado a novas mensagens.
  1. solidforms

    solidforms Power Member

    Boas pessoal,

    Eu tenho um trabalho de programação para fazer em Java e para o seu desenvolvimento tiver que implementar uma estrutura de dados, uma tabela de dispersao aberta. Isto porque a prof deu a teoria e deixou os métodos por implementar.
    O problema é o seguinte, da-me a impressão que o meu rehash() nao esta a copiar todos os valores, do genero:

    Começa com 200, quando enche passa a 400 com o rehash(); mas ate aqui copia tudo.
    O meu acontece quando passa a 800 que, mais uma vez, copia tudo.
    Todavia, quando faz novo rehash() aos 800 (passa para 1600) ele ja nao copia tudo.

    Do género, se eu tiver a inserir strings sequencialmente, string1,..., string1200, quando ele faz o ultimo rehash() quando vou a fazer um find dessas strings, so diz que existem as que eu chamo a partir da string801, tudo o que deveria estar para tras ele diz que nao existe.
    Penso que seja no rehash() nao encontro mais nenhum problema :s.

    Eis o código:
    Código:
    [SIZE=2]
    [LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]protected[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Dictionary<K,V>[] [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2];
    
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] SepChainHashTable( )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][I][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]DEFAULT_CAPACITY[/I][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]);
    } 
    
    [/SIZE][SIZE=2][COLOR=#646464][SIZE=2][COLOR=#646464]@SuppressWarnings[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#2a00ff][SIZE=2][COLOR=#2a00ff]"unchecked"[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2])
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] SepChainHashTable( [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] capacity )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] arraySize = HashTable.[I]nextPrime[/I](([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]) 1.1 * capacity);
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = (Dictionary<K,V>[]) [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Dictionary[arraySize];
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]for[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ( [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] i = 0; i < arraySize; i++ )
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][i] = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] AVLTree<K,V>();
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = capacity;
    } 
    
     
    [/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Returns the hash value of the specified key.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]protected[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] hash( K key )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]return[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Math.[I]abs[/I]( key.hashCode() ) % [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2];
    }
    
     
    [/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Returns the value in the dictionary whose key is the specified key;[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// or null if no such entry exists. [/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] V find( K key )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]return[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][ [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].hash(key) ].find(key);
    }
    
    [/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Inserts the entry (key, value) in the dictionary.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// If the dictionary already contained an entry with the specified key,[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// returns the old value (which is replaced by the specified value);[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// otherwise, returns null.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] V insert( K key, V value )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]if[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].isFull())
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].rehash();
    V v = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][hash(key)].insert(key, value);
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]if[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]( v == [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]null[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2])
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]currentSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]++;
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]return[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] v;
    }
    
    [/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Removes the entry whose key is the specified key from the dictionary[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// and returns the associated value, if such entry exists.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Otherwise, returns null.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] V remove( K key )
    {
    V v = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][hash(key)].remove(key);
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]if[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2](v != [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]null[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2])
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]currentSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]--;
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]return[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] v;
    }
    
    [/SIZE][SIZE=2] 
    
    [/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]//increase the size of the table[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#646464][SIZE=2][COLOR=#646464]@SuppressWarnings[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#2a00ff][SIZE=2][COLOR=#2a00ff]"unchecked"[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2])
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]private[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]void[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] rehash()
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] * 2;
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] arraySize = HashTable.[I]nextPrime[/I](([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]) 1.1 * [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]);
    Dictionary<K,V>[] table_tmp = (Dictionary<K,V>[]) [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Dictionary[arraySize];
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]for[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] i = 0 ; i < [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ; i++){
    table_tmp[i] = [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][i];
    }
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]for[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] i = [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ; i < arraySize ; i++)
    table_tmp[i] = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] AVLTree<K,V>();
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]=table_tmp;[/LEFT]
    }
    [/SIZE]
    PS: Ja fiz o rehash de varias maneiras, uma delas, foi usar um iterador mas nao resolveu o problema. Vejam se podem ajudar :p.

    Cumps ;)
     
  2. solidforms

    solidforms Power Member

    Ninguem? :x.
    Entretanto ja alterei o rehash() mas continua na mesma :s :'(

    Código:
    [SIZE=2]
    [LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]//increase the size of the table[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][SIZE=2][COLOR=#646464][SIZE=2][COLOR=#646464]@SuppressWarnings[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#2a00ff][SIZE=2][COLOR=#2a00ff]"unchecked"[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2])
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]private[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]void[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] rehash()
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] * 2;
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] arraySize = HashTable.[I]nextPrime[/I](([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]) 1.1 * [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]maxSize[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]);
    Dictionary<K,V>[] table_tmp = (Dictionary<K,V>[]) [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Dictionary[arraySize];
    Iterator<Entry<K,V>> it;
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]for[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ( [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] i = 0; i < table_tmp.[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ; i++ )
    table_tmp[i] = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] AVLTree<K,V>();
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]for[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]( [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] i = 0 ; i < [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] ; i++)
    {
    it = [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][i].iterator();
    it.rewind();
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]while[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2](it.hasNext())
    {
    Entry<K,V> e = it.next();
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] hashKey = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].hash(e.getKey());
    table_tmp[hashKey].insert(e.getKey(), e.getValue());
    }
    }
    [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]=table_tmp;[/LEFT]
    }
    [/SIZE]
    Safem-me la ;D.
    Cumps ;)
     
  3. MadOnion

    MadOnion Folding Member

    Normalmente para rehashs em Open Hashtables, uso algo muito simples.
    Guardo a referencia para uma tabela auxiliar, duplicado o tamanho do atributo actual, e faço uma cópia/inserção dos mesmos elementos no atributo.

    Código:
    Dictionary<K,V>[] aux = table;
    int newLength = 2 * aux.length + 1;
    table = new Dictionary<K,V>[newLength];
    
    for (int i = 0; i < aux.length; i++)
    	    if (aux[i] != null) //normalmente uma tabela nao esta totalmente preenchida
                    insert(aux[i].getKey(), aux[i].getValue());
    
    Espero ter ajudado.
    Já agora, é suposto, numa hashtable aberta usar arvores equilibradas ou outro tipo de estruturas de dados em cada posição da tabela?
    Sempre usei isso, mas para hashtables encadeadas, mas também foi algo que usei em ambiente académico apenas.
    O código acima precisa de ser retificado por causa disso
     
  4. IComeFromBehind

    IComeFromBehind Power Member

    ?? mas aux é um dicionário como é que lhe fazes getKey e getValue?

    Para o TS, usar AVLs para entradas do array de uma tabela de dispersão costuma implicar uma perda de performance (a diminiução da complexidade no pior caso não compensa os factores constantes).

    Quanto à tua implementação, parece estar bem lol. Já verificaste as AVL?
     
  5. solidforms

    solidforms Power Member



    Hum, nao percebi, num dicionario podes sempre fazer o getKey() e o getValue(). No entanto, sim, penso que as AVL estão bem, porque no resto do programa tudo corre como previsto e os outputs estão bem. Quanto à perda de performance, nao devo usar uma AVLTree? a alternativa seria uma BinarySearchTree, na qual os inserts são piores que nas AVL (que procuram corrigir essa complexidade) em alternativa o que sugeres? usar uma lista ligada ordenada?

    Hum, portanto,... o meu código parece estar bem, certo? lol :x, preferia que houvesse um erro :p. Nao percebi bem a implementação do MadOnion :x, do género, nao deverias fazer um hash da chave? :p. Enfim, xD.

    E sim, de facto isto tem fins académicos ;). Mas nao estou a pedir o trabalho feito, hehe :P;). Odeio esta matéria, muita informação junta xD.

    Cumps ;).
    P.S.: mais sugestões bem-vindas porque so falta isto xD.
     
  6. Baderous

    Baderous Banido

    Penso que o que o IComeFromBehind quis dizer é que utilizar AVLs nos índices do array da Hash Table retira toda a vantagem da estrutura em termos de tempos de acesso (O(1)), introduzindo complexidade logarítmica das AVLs, quer na inserção, quer na procura. Penso que não se deve usar Hash Tables com AVLs. Normalmente uma hash table bem construída consegue dar conta do recado, mesmo no que toca a colisões (quer em chaining, quer open addressing). Se há muitas colisões, das duas uma: ou o algoritmo de hashing é fraco, ou o tamanho do array da tabela de hash é demasiado pequeno. Se houver necessidade de introduzir ordem nos elementos, então aí é caso para se pensar em AVLs, mas em separado.
     
  7. IComeFromBehind

    IComeFromBehind Power Member

    Um dicionário não tem getKey() nem getValue(), as entradas de um dicionário é que têm. De facto se a percentagem de ocupação da hash table for apropriada usar listas (ordenadas ou não) é bastante mais rápido que usar árvores.
     
  8. solidforms

    solidforms Power Member

    Baderous, mas das estruturas de dados que eu conheço, as AVL são as estruturas dinâmicas com melhor complexidade. Esta bem que uma open hashtable é constante mas não é dinamica.
    Entao o que me sugerem? usar uma lista lista em vez de uma BinarySearchTree ou AVL,...?

    Todavia, nao me resolve o problema de isto nao estar a copiar tudo devidamente :x :p.

    Cumps ;)
     
  9. Baderous

    Baderous Banido

    Dinâmica como? As Hash Tables também são dinâmicas, pois o tamanho do array pode ser aumentado, bem como as listas ligadas usadas em chaining são dinâmicas. Geralmente, referem-se 2 tipos de utilização de hashtables: com chaining ou open addressing. Dependendo do problema em questão opta-se por uma ou por outra. Normalmente usa-se open addressing quando se têm poucos dados a inserir e estes têm tamanho fixo, pois esta técnica implica que haja uma função de hash decente para evitar colisões sucessivas (e respectivo probing) e, quando há muitos dados a inserir, implica o resize do array (pois este fica cheio) que, no melhor caso, ocorre em tempo linear, mas ainda demora bastante pois é preciso recolocar os dados que já estavam inseridos na tabela. Se, pelo contrário, tiveres bastantes dados a inserir, então chaining será a melhor opção, pois as colisões são tratadas com inserções em listas ligadas, sendo raras as vezes que é necessário fazer o resize do array, pois, ao contrário do open addressing, aqui a tabela nunca fica cheia.
    Como a tua tabela é esparsa, a melhor solução será chaining. Agora porque é que eu recomendo listas em vez de AVLs? Porque com listas consegues tempos de inserção constantes, enquanto que na AVL são logarítmicos. Ocorrendo também poucas colisões (boa função de hashing e tamanho do array adequado), consegue-se atingir tempos de pesquisa constantes, enquanto que na AVL continuam a ser logarítmicos, bem como nas remoções. E, mesmo que existam colisões, utilizando uma hashtable bem construída, obtém-se listas de poucos elementos, logo, apesar das pesquisas em listas serem feitas em O(n), sendo n o nº de elementos, acaba por compensar relativamente às AVLs, pois o baixo nº de elementos, torna as pesquisas mais eficientes em listas do que AVLs, basta comparar os gráficos para tempos lineares e logarítmicos: para valores pequenos, o linear é melhor do que o logarítmico. E não te esqueças também de todo o overhead introduzido pelas AVLs no que toca a rotações e balanceamento.
    Como o propósito das hashtables não é manter os dados ordenados, mas criar uma indexação através de associações chave-valor, apenas em casos muito específicos como relatados neste último quote é que se devem usar AVLs como estruturas auxiliares de hashtables.

    http://en.wikipedia.org/wiki/Hash_table
    http://en.wikipedia.org/wiki/Associative_array#Efficient_representations
     
    Última edição: 16 de Novembro de 2008
  10. solidforms

    solidforms Power Member

    Obrigado Baderous, pela explicação. Elucidaste-me bastante :p;).

    Sim, de facto, necessito de uma chain hashtable, para um dos casos o maximo de inserções são 1000 e no outro 10000.
    Eu posso colocar aqui a função de hash():
    Código:
    [SIZE=2]
    [LEFT][/SIZE][SIZE=2][COLOR=#3f7f5f][SIZE=2][COLOR=#3f7f5f]// Returns the hash value of the specified key.[/LEFT]
    [/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2][LEFT][/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]protected[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]int[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] hash( K key )
    {
    [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]return[/B][/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] Math.[I]abs[/I]( key.hashCode() ) % [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]table[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]length[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2];
    }[/LEFT]
    [/SIZE]
    Serve? :p.

    Sim, quando estudei a matéria de facto falavam em listas ligadas, todavia quando ia a implementar esta ED surgiu-me um problema, isto é um dicionário e a lista ligada nao é, quando inicializava cada posição da tabela com uma linked list dava barraca :P.

    O que sugeres, adaptar a minha lista ligada para poder usa-la aqui? ou seja, dizer que implementa um dicionário deveria resultar. Se pudesses ajudar :p.

    Todavia, nao encontras nenhum possivel erro de raciocinio lógico que te leve a dizer porque não esta a copiar tudo a partir do 2ºrehash?
    Eu inicializo com 400, o primeiro rehash() é para 800 e depois nao copia mais nada >(.

    Sim, penso que esta minha implementação esta a fazer isso. Ao fazer o hash da chave, mesmo que seja uma colisao ele insere. Ate aqui estou a fazer tudo bem nao estou? xD.

    Cumps ;).;)
     
  11. Baderous

    Baderous Banido

    Parece-me uma função aceitável para o nível académico, no entanto penso que ficaria melhor se lhe fosse acrescentada um peso que seja número primo, isto é, multiplicar o key.hashCode() por um nº primo. Podes ver outras funções de hashing (de strings) aqui: http://www.cse.yorku.ca/~oz/hash.html . Podes ler também um artigo sobre hashing com nºs primos onde podes ver a relação entre funções de hash como a tua e o facto de se usar, por isso, um tamanho do array que seja nº primo: http://www.concentric.net/~Ttwang/tech/primehash.htm

    Quanto ao teu código, mal olhei para ele porque não estou com tempo para isso. Só reparei que estás a usar um Dictionary que é uma classe obsoleta:
     
    Última edição: 16 de Novembro de 2008
  12. solidforms

    solidforms Power Member

    Hum, sim eu estou a multiplicar pelo nextPrime() que ves o primo seguinte à dimensao da tabela.
    Em relação ao dicionário, sim, de facto é so abstracto. O que implementa o dicionario sao estas tabelas de dispersao aberta ou fechada. Para o dicionario ordenado tenho as binary search tree, avls e vermelhas/pretas :x.

    O complicado aqui é que para o trabalho ter mais que 15 nao posso usar o java.util :mad:. Logo tudo o que usar tenho que ter em codigo. Portanto so mesmo este Dicionario deve ser implementado.

    Ermmm, é que so falta mesmo isto >(.
    Enfim, continuem ;D.

    Cumps ;)
     
  13. syqe

    syqe Power Member

    O teu primeiro rehash estava errado pois estavas a copiar as entradas duma tabela para a outra, o que é errado pois, como as tabelas têm tamanhos diferentes, uma key vai "calhar" numa posição diferente nas tabelas, ou seja, depois de fazer rehash nunca irias voltar a encontrar um elemento pela key certa utilizando o teu find(key).

    Quanto ao segundo, realmente também estou de acordo ao que respeita as AVL's, uma open hashtable não precisa de AVL's para as colisões, pois devem ser sempre minimas, uma lista ligada dupla chega.

    A unica alteração que faria ao teu código é em vez de teres um ciclo a pedir iteradores pela tabela, por que não pedes o this.iterator?, é mais fácil digo eu. ([edit] dando uma segunda leitura ao teu código e se aquela é a tua classe completa, ainda não tens o iterator da hashtable, e realmente és obrigado a usar o teu método, talvez alterar no futuro? [/edit])
    Mesmo assim o teu código deveria funcionar no rehash(), esta segunda versão continua com o mesmo comportamento?

    Parece-me que não percebeste bem o objectivo daquele método, parece-me que a sua função é saber a posição de uma key na tabela, daí estar o %table.length e não para calcular um hash em si.
     
    Última edição: 18 de Novembro de 2008
  14. syqe

    syqe Power Member

    Lol pela descrição que tás a dar, tás na FCT com a Mamede não?
     
  15. solidforms

    solidforms Power Member

    loool, ya xD. tambem estas a fazer AED ou ja fizeste? :P.

    Entretanto ja consegui resolver o problema. Tinha a ver com o hash que estava a fazer, ou seja, eu estava a fazer o hash à tabela antiga que tinha uma dimensão inferior. Quando o que eu deveria fazer era um hash à dimensao nova. Agora está tudo sobre rodas xD :p.

    Resta-me apenas verificar a minha implementação de rotação nas AVL quando se remove. Sim porque a prof nao nos deu isso >(:p lol.

    O programa ja está todo bem, tenho que verificar a serialização, nao sei porque mas quando faço o store nao guarda nada :x.
    O store() tem que ser chamado a cada output que faça? é que nao parece fazer sentido, eu tenho um store() no final do programa, ou seja, quando termina com o ctrl+z :confused:.

    Cumps ;)
     
  16. syqe

    syqe Power Member

    Já fiz há uns anos, mas a Mamede não muda nunca.

    Quanto à serialização não sei o que é pedido, mas por norma o store é feito ao terminar a aplicação.
     
  17. solidforms

    solidforms Power Member

    Hum, acredito que não :p, lol.

    Eles querem o serialize para guardar estados de execução para serem repostos e acedidos numa execução currente.
    O problema é que no primeiro load() ele lança uma excepção quando o ficheiro esta vazio de EOF:


    E se eu aldrabar isto, do genero, chamar o store() logo a seguir a criar o objecto e dps o load() ele ja nao estoira. Mas ainda assim, dps de eu fazer ctrl+z para sair do ciclo while(hasNextLine()), correr novamente o store() e terminar, ele nos loads seguintes nao recupera o estado >(.
    Codigo do load e store:
    Código:
    [SIZE=2][COLOR=#7f0055]
    
    [B][SIZE=2][COLOR=#7f0055]public
    [/COLOR][/SIZE][/B][/COLOR][/SIZE][LEFT][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]class[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2][COLOR=#000000] AcademyIO [/COLOR][/SIZE]
    [LEFT][SIZE=2]{[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]private[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] IAcademy [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]academy[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2];[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]private[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] String [/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]filename[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2];[/SIZE][/LEFT]
     
    [LEFT][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] AcademyIO(Academy a, String file)[/SIZE]
    [SIZE=2]{[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]academy[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = a;[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]this[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2].[/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]filename[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = file;[/SIZE]
    [SIZE=2]}[/SIZE][/LEFT]
     
    [LEFT][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/COLOR][/SIZE][/COLOR][/SIZE][/B][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]void[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] load()[/SIZE]
    [SIZE=2]{[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]try[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] {[/SIZE]
    [SIZE=2]ObjectInputStream file = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] ObjectInputStream([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] FileInputStream([/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]filename[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]));[/SIZE]
    [SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]academy[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2] = (IAcademy) file.readObject();[/SIZE]
    [SIZE=2]file.close();[/SIZE]
    [SIZE=2]} [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]catch[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] (FileNotFoundException e) {[/SIZE]
    [SIZE=2]e.printStackTrace();[/SIZE]
    [SIZE=2]} [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]catch[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] (IOException e) {[/SIZE]
    [SIZE=2]e.printStackTrace();[/SIZE]
    [SIZE=2]} [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]catch[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] ( ClassNotFoundException e ) {[/SIZE]
    [SIZE=2]e.printStackTrace();[/SIZE]
    [SIZE=2]}[/SIZE]
    [SIZE=2]}[/SIZE][/LEFT]
     
    [LEFT][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]public[/COLOR][/SIZE][/COLOR][/SIZE][/B][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]void[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] store()[/SIZE]
    [SIZE=2]{[/SIZE]
    [B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]try[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] {[/SIZE]
    [SIZE=2]ObjectOutputStream file = [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] ObjectOutputStream([/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]new[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] FileOutputStream([/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]filename[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]));[/SIZE]
    [SIZE=2]file.writeObject([/SIZE][SIZE=2][COLOR=#0000c0][SIZE=2][COLOR=#0000c0]academy[/COLOR][/SIZE][/COLOR][/SIZE][SIZE=2]);[/SIZE]
    [SIZE=2]file.flush();[/SIZE]
    [SIZE=2]file.close();[/SIZE]
    [SIZE=2]} [/SIZE][B][SIZE=2][COLOR=#7f0055][SIZE=2][COLOR=#7f0055]catch[/COLOR][/SIZE][/COLOR][/SIZE][/B][SIZE=2] (IOException e) {[/SIZE]
    [SIZE=2]e.printStackTrace();[/SIZE]
    [SIZE=2]}[/SIZE]
    [SIZE=2]}[/SIZE][/LEFT]
    
    No main:
    academy = new Academy();
    academyIO = new AcademyIO(academy, "state_preservation");
    academyIO.load();

    Scanner input = new Scanner(System.in);



    output = new PrintWriter(System.out, true);
    // To compare with other output test files
    // try {
    // output = new PrintWriter("output.out");
    // } catch (FileNotFoundException e) {
    // e.printStackTrace();
    // }


    inputData(input);

    Cumps ;)

    [/LEFT]
     
  18. syqe

    syqe Power Member

    A primeira vez que corres o programa é suposto dar o tal erro pois não existem dados em ficheiro e crias as estruturas de dados vazias.

    Se não me engano quando fazes CTRL+Z terminas o processo e ele nunca deve chegar a fazer o store. O que eu faria é teres um comando que termina o processo quit/exit qualquer coisa que faz o store() e depois termina
     
  19. solidforms

    solidforms Power Member

    não existe nenhum pedido de implementação que faça a leitura de um comando "sair" e ele terminar. Entretanto, o problema ja esta resolvido :p:009:.
    Meti o load() e retornar um objecto e quando inicializo no main faço Object o = ObjectIO.load();

    e no método load() aquando uma IOException em vez de estoirar faz um new Object() no catch.

    Ainda és aluno da FCT? ou ja deixaste isto? ;D.

    Cumps ;)
     
  20. syqe

    syqe Power Member

    Estou a tirar Mestrado, mas sou Trabalhador-Estudante só estou na FCT aos fins de semana :P
     
Estado do Tópico:
Fechado a novas mensagens.

Partilhar esta Página