Estoy probando un método que agrega una lista enlazada de pares hash dentro de un vector. Aunque me encuentro con un IndexOutOfBounds pero tengo problemas para entender dónde existe el problema.
import java.util.*; class HashPair<K, E> { K key; E element; } public class Test4<K, E> { private Vector<LinkedList<HashPair<K, E>>> table; public Test4(int tableSize) { if (tableSize <= 0) throw new IllegalArgumentException("Table Size must be positive"); table = new Vector<LinkedList<HashPair<K, E>>>(tableSize); } public E put(K key, E element) { if (key == null || element == null) throw new NullPointerException("Key or element is null"); int i = hash(key); LinkedList<HashPair<K, E>> onelist = table.get(i); ListIterator<HashPair<K, E>> cursor = onelist.listIterator(); HashPair<K, E> pair; E answer = null; while (cursor.hasNext()) { pair = cursor.next(); if (pair.key.equals(key)) { answer = pair.element; pair.element = element; return answer; } } pair = new HashPair<K, E>(); pair.key = key; pair.element = element; onelist.addFirst(pair); return answer; } private int hash(K key) { return Math.abs(key.hashCode() % table.capacity()); } public static void main(String[] args) { Test4<Integer, Integer> obj = new Test4<Integer, Integer>(10); obj.put(0, 10); } }Mi compilador dice que el problema está aquí:
LinkedList<HashPair<K, E>> onelist = table.get(i);Por lo que entiendo, estoy tratando de obtener el índice de la tabla de i, que es un valor hash generado a partir del método hash (clave K). Entonces, en mi método principal, si configuro la clave en 0 como ejemplo. ¿Por qué el índice está fuera de rango?
Aquí está la excepción
Exception in thread "main" 0java.lang.ArrayIndexOutOfBoundsException: Array index out of range: 0 at java.util.Vector.get(Vector.java:748) at Test4.put(Test4.java:24) at Test4.main(Test4.java:55)El problema aquí es que estás considerando que la capacity de un vector es el número de elementos en el vector. Esto no es lo que representa la capacity de una colección.
La capacity de una colección en las bibliotecas Java estándar es el tamaño de la matriz interna utilizada por esa colección. Sin embargo, el número de elementos de la colección está representado por el size .
Cada vez que se agrega o elimina un elemento de dicha colección, la propiedad de size se modifica. Esto no afecta la capacity de la colección, a menos que sea necesario cambiar el tamaño de la matriz interna.
La solución: modificar hash() a lo siguiente:
private int hash(K key) { return Math.abs(key.hashCode() % table.size()); } Y asegúrese de que el table de la tabla contenga al menos un elemento antes de llamar a hash y table.get .
Supongo que está creando una implementación de un HashMap con cubos. Si es así, reflexione sobre esto: ¿Cómo puede almacenar un valor en un cubo si no hay cubos ? Debe tener al menos un balde antes de intentar get un balde.
Parece que su código se está atascando en la línea 748, que es:
LinkedList<HashPair<K, E>> onelist = table.get(i); La descripción Array index out of range: 0 significa que está tratando de obtener un objeto en la ranura '0', cuando no hay tal ranura disponible en ese momento. En resumen: su vector está vacío. Y al mirar su código, la razón se vuelve bastante evidente. El único tratamiento que recibe esta table llamada Vector antes de llamar a Test4.put() se reduce a esto en la línea 15:
table = new Vector<LinkedList<HashPair<K, E>>>(tableSize); Entonces, sí, está creando correctamente un objeto e inicializando una variable, incluso está especificando una capacidad predeterminada, pero nunca agregó algo a su nuevo Vector , y tanto las listas como los vectores deben llenarse manualmente con cosas primero. Tenga en cuenta que esta "capacidad" se refiere a la cantidad de cosas que se supone que debe contener este Vector sin necesidad de cambiar el tamaño de la matriz que usa internamente. Me da la impresión de que está tratando de crear una clase cuyos objetos tienen un comportamiento como HashMap s, pero no puedo entender la necesidad de usar un Vector de LinkedList s de KeyPair s cuando solo una colección de KeyPair s debería ser suficiente a menos que... espera, ¿qué está haciendo ese método hash() ? Oh... ohh... oh, ya veo lo que hiciste allí.
Entonces, correcto, la solución. Como su Vector se creó correctamente pero está vacío , debe llenarlo con lo que se supone que debe contener. En este caso, contiene LinkedList s de KeyPair s, así que llenémoslo con los suficientes para mantener la capacidad que estableció a través del constructor. Esta modificación al constructor debería hacer la cosa:
public Test4(int tableSize) { if (tableSize <= 0) throw new IllegalArgumentException("Table Size must be positive"); table = new Vector<LinkedList<HashPair<K, E>>>(tableSize); //Prepare the fast lookup table (at least that's what I think it could be called) for (int i = 0; i < tableSize; i++) { table.add(new LinkedList<HashPair<K, E>>()); } }Y eso es todo. Incluso lo probé aquí solo para asegurarme de que funcionó bien después de mi parche.
Espero que esto te ayude.
PD: ¿Dividir su estructura en n partes para acelerar la búsqueda/almacenamiento? Me gusta la idea.