Ayuda con hashtable

[kiko's]

Hola amigos.

Soy estudiante de informática y no soy capaz de resolver un problema presente en una de mis prácticas. Intentaré resumirlo lo mejor posible.

La práctica consiste en dada un URL inicial, una palabra y un grado máximo, mirar si esta palabra aparece en alguna de las urls generadas. Se utiliza la técnica de backtracking por recurrencia. Está claro que esto genera una serie de nodos (urls) en forma de árbol y este árbol crecerá verticalmente hasta llegar al grado máximo dado.

Bien, mi problema consiste en que debo tener en cuenta las urls visitadas en ciertos grados. Por ejemplo, si visito la web "marca.com" en el grado 1, no debería visitarla de nuevo en el grado 2. Pero si la visito en el grado 2, entonces si debería visitarla en el grado 1 de nuevo.

Para resolver el problema de las urls visitadas no debería utilizar un vector, pues en el peor de los casos la complejidad del algoritmo aumenta considerablemente.

Para ello me han propuesto utilizar un hashtable o hashmap, y éste es el problema, que hoy es la primera vez que utilizo una estructura de estas características y no tengo ni idea.

Lo que he hecho ha sido lo siguiente, pero no sé si es correcto:

Código:

    [..]
    public int mihashCode(String url, int gradoActual) {
        int hash = 3;
        hash = 43 * hash + (url != null ? url.hashCode() : 0);
        hash = 43 * hash + gradoActual;
        return hash;
    }

     private boolean urlVisitada(String url, int gradoActual){
         for(int i = 0; i<=gradoActual; i++){
             if(hashtable.containsKey(mihashCode(url, i))){
             return true;
             }else{
                 hashtable.put(mihashCode(url, gradoActual), 0);
                 return false;
             }
         }
         return false;
     [..]

Lo que hago es comprobar si la url pasada por parámetro ha sido visitada en un nivel superior o no. Si ha sido visitada entonces devuelvo true, sino false.

No sé si voy en buen camino y lo que más me preocupa es el método miHashCode que tal y como está definido podría asignar el mismo valor a claves distintas, aunque desconozco el nivel de probabilidad de que esto ocurra.

Gracias.

[kiko's]

Hola amigos.

Finalmente quedó resuelta con el siguiente código:

Código:

     private boolean urlVisitada(String ur, int gradoActual){
         if(hashmap.containsKey(ur)){
             if((Integer)hashmap.get(ur)<=gradoActual){
                 return true;
             }else{
                 hashmap.remove(ur);
                 hashmap.put(ur, gradoActual);
                 return false;
             }
         }else{
             hashmap.put(ur, gradoActual);
             return false;
         }
     }

Este código define una función bijectiva, resolviendo así mi problema de que existía la probabilidad de que distintas claves pudieran tener el mismo valor, tal que así:
URL - > gradoActual(que siempre será el grado mínimo en el que se haya encontrado una URL)

Este tipo de estructuras permite la búsqueda de la relación entre clave-valor con un coste de complejidad O(1) en la mayoría de los casos, sin duda un excelente sustituto de vectores asociativos, pues la búsqueda de un elemento en un vector no ordenado supondría un coste, en el peor de los casos, O(n). Es decir, en un vector de 1 millon de elementos la búsqueda tardaría 1 millón de unidades de tiempo, frente a 1 unidad de tiempo, de media, que se tardaría con una estructura hash.

Comparto esta información para todos aquellos que les pueda resultar útil.

Si encuentran algún fallo en mi explicación les ruego que me corrijan.

HashMap en Java: http://download.oracle.com/javase/1....l/HashMap.html

Gracias :)