I'm testing a method that adds a linked list of hash pairs inside a vector. Although, I'm running into a IndexOutOfBounds but I'm having trouble understanding where the problem exists.
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);
}
}
My compiler says that the problem is here:
LinkedList<HashPair<K, E>> onelist = table.get(i);
From what I understand is that I'm trying to get the table index of i which is a hash value generated from the hash(K key) method. So in my main method if I set the key to 0 as an example? Why is the index out of range?
Here is the exception
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)
The problem here is that you are considering the capacity of a vector to be the number of elements in the vector. This is not what capacity of a collection represents.
The capacity of a collection in the standard Java libraries is the size of the internal array used by that collection. The number of elements in the collection, however, is represented by size.
Whenever an element is added to/removed from such a collection, the size property is modified. This does not affect the capacity of the collection unless the internal array needs to be resized.
The solution: modify hash() to the following:
private int hash(K key) {
return Math.abs(key.hashCode() % table.size());
}
And make sure that the table vector contains at least one element before calling hash and table.get.
I presume that you are creating an implementation of a HashMap with buckets. If you are, then ponder this: How can you go about storing a value in a bucket if there aren't any buckets? You need to have at least one bucket before trying to get a bucket.
It seems your code is getting stuck at line 748, which is:
LinkedList<HashPair<K, E>> onelist = table.get(i);
The description Array index out of range: 0 means you're trying to get an object at slot '0', when there is no such slot available at the time. In short: your vector is empty. And by looking at your code, the reason becomes pretty evident. The only treatment this Vector called table receives before Test4.put() is called gets down to this at line 15:
table = new Vector<LinkedList<HashPair<K, E>>>(tableSize);
So, yes, you're properly creating an object and initializing a variable, you are even specifying a default capacity, but you never added something into your brand new Vector, and both lists and vectors do require to be filled manually with stuff first. Keep on mind that this "capacity" refers to how much stuff is this Vector supposed to hold without need to resize the array it uses internally. It gives me the impression you are trying to create a class whose objects have a behavior like HashMaps, but I can't wrap my mind around the need of using a Vector of LinkedLists of KeyPairs when just a single collection of KeyPairs should be enough unless... wait, what is that hash() method doing? Oh... ohh... oh, I see what you did there.
So, right, the solution. As your Vector is properly created but empty, you need to fill it with whatever it is supposed to hold. In this case, it holds LinkedLists of KeyPairs, so let's fill it with just enough of them to hold the capacity you set through the constructor. This modification to the constructor should do the thing:
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>>());
}
}
And that's pretty much it. I even tested it here just to be sure it worked fine after my patch.
Hope this helps you.
PS: Splitting your structure in n pieces to speedup search/store? I like the idea.