Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   HashTable class (http://www.programmingforums.org/showthread.php?t=14349)

xeric Nov 6th, 2007 1:00 PM
HashTable class
 
Hi.. I'm writing this HashTable class and I'm not sure what this error is from. I get it when I run this short little test program with more than two calls to put. Any help would be greatly appreciated. Note: The Pair<K,V> class is just basically a K key and V value with getKey and getVal methods.

The Error

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size:
2
at java.util.ArrayList.RangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at HashTable.put(HashTable.java:77)
at HashTest.main(HashTest.java:9)

The Test Program That Produces The Error

:
  1. public class HashTest {
  2.         public static void main (String[] args) {
  3.                 HashTable<String,Float> hash = new HashTable<String,Float>();
  4.                 hash.put("Tim", new Float(100.50));
  5.                 hash.put("Jeff", new Float(94.30));
  6.                 hash.put("Ben", new Float(10.73));
  7.                 hash.put("Page", new Float(18.94));
  8.         }
  9. }

The HashTable class

:
  1. import java.util.*;
  2.  
  3. public class HashTable<K,V> /*implements Map<K,V>*/ {
  4.  
  5.         private int size;
  6.         private int count;
  7.         private ArrayList<ArrayList<Pair<K,V>>> hashArray;
  8.  
  9.         //Default Constructor
  10.         public HashTable() {
  11.                 size = 16;
  12.                 count = 0;
  13.                 hashArray = new ArrayList<ArrayList<Pair<K,V>>>(16);
  14.                 try {
  15.                         for (int i = 0; i <= size; i++) {
  16.                                 hashArray.add(i, new ArrayList<Pair<K,V>>());
  17.                         }
  18.                 }
  19.                 catch (IndexOutOfBoundsException e) {
  20.                         e.printStackTrace();
  21.                 }
  22.         }
  23.  
  24.         //Constructor that sets the size
  25.         public HashTable(int s) {
  26.                 size = s;
  27.                 count = 0;
  28.                 hashArray = new ArrayList<ArrayList<Pair<K,V>>>(size);
  29.                 for (int i = 0; i <= size; i++) {
  30.                         hashArray.add(i, new ArrayList<Pair<K,V>>());
  31.                 }
  32.         }
  33.  
  34.         public int hash(Object k) {
  35.                 int i = k.hashCode() % size;
  36.                 return i;
  37.         }
  38.  
  39.         public V put(K k, V value) {
  40.                 Pair<K,V> p1 = new Pair<K,V>(k, value);
  41.                 int hsh = hash(k);
  42.                 hashArray.get(hsh).add(p1);
  43.                 count++;
  44.  
  45.                 if (hashArray.get(hsh).size() <= 1)
  46.                         return null;
  47.                 else
  48.                         return hashArray.get(hsh).get(size() - 1).getVal();                
  49.         }
  50.  
  51.         public V get(Object k) {
  52.                 int hsh = hash(k);
  53.                 for (int i = 0; i <= hashArray.get(hsh).size(); i++) {
  54.                         Pair<K,V> p1 = hashArray.get(hsh).get(i);
  55.                         if (p1.getKey() == k || p1.getKey().equals(k))
  56.                                 return p1.getVal();
  57.                 }
  58.                 return null;
  59.         }
  60.  
  61.         public boolean isEmpty() {
  62.                 return (count == 0);
  63.         }
  64.  
  65.         public int size() {
  66.                 return count;
  67.         }
  68.  
  69.         public void clear() {
  70.                 for(int i = 0; i < hashArray.size(); i++) {
  71.                         hashArray.get(i).clear();
  72.                 }
  73.         }
  74.  
  75.         public boolean containsKey(Object ky) {
  76.                 int hsh = hash(ky);
  77.                 for (int i = 0; i <= hashArray.get(hsh).size(); i++) {
  78.                         K k1 = hashArray.get(hsh).get(i).getKey();
  79.                         if (k1 == ky || k1.equals(ky))
  80.                                 return true;
  81.                 }
  82.                 return false;
  83.         }
  84.  
  85.         public boolean containsValue(Object value) {
  86.                 for (int i = 0; i <= hashArray.size(); i++) {                        
  87.                         for (int j = 0; j <= hashArray.get(i).size(); j++) {
  88.                                 V v1 = hashArray.get(i).get(j).getVal();
  89.                                 if (v1 == value || v1.equals(value))
  90.                                         return true;
  91.                         }
  92.                 }
  93.                 return false;
  94.         }

Narue Nov 6th, 2007 2:35 PM
Re: HashTable class
 
Start your debugging quest by realizing that indices in Java are based on a half-open range. In an array of size N, the valid indices are 0 to N - 1.

Harakim Nov 12th, 2007 12:16 AM
Re: HashTable class
 
Look at <, <=

null_ptr0 Nov 21st, 2007 9:15 PM
Re: HashTable class
 
<= would mean that local variable i would be equal to or less then, which is not what you're aiming for.
What you're aiming for is actually:
:
  1. public boolean containsKey(Object key) {
  2.         for(Pair<K, V> pair : hashArray.get(hash(key)))
  3.                 if(pair.getKey().equals(key))
  4.                         return true;
  5.         return false;
  6. }
It uses a foreach loop instead of a for loop so it seems more simple.
Oh, and Object.equals(Object) return Object == Object, but equals(Object) is overridden in special cases so there is no need for pair.getKey() == key.


All times are GMT -5. The time now is 3:24 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC