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:
PS: Ja fiz o rehash de varias maneiras, uma delas, foi usar um iterador mas nao resolveu o problema. Vejam se podem ajudar .
Cumps
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 .
Cumps