Java - Data Structure (Hash Tables)

A hash table is a data structure that offers very fast insertion and searching. No matter how many data items there are, insertion and searching( and sometimes deletion) can take close to constant time: O(1) in Big O notation.

class DataItem
{ // (could have more data)
public int iData; // data item (key)
public DataItem(int ii) // constructor
{ iData = ii; }
} // end class DataItem


nonItem = new DataItem(-1); // deleted item key is -1
DataItem[] hashArray; // array holds hash table

private int hashFunc(int key){
return key % arraySize; // linear probe
}

public void insert(DataItem item) {
int key = item.iData; //extract key
//hash the key
int hashVal = hashFunc(key);

//until empty cell or -1(nonitem for deleted items)
while(hashArray[hashVal] != null && hashArray[hashVal]l.iData != -1){
++hashVal;
hashVal %= arraySize; // wrap around if necessary
} // end while

hashArray[hahVal] = item;
}// end insert()

public DataItem find(int key){
  int hashVal = hashFunc(key);

 //until empty cell
  while(hashArray[hashVal] != null){
   if(hashArray[hashVal].iData == key)
      return hashArray[hashVal];
   ++ hashVal;
  // wrap around if necessary
 hashVal %= arraySize;
  }
  return null;
}

public DataItem delete(int key){
int hashVal = hashFunc(key);
while(hashArray[hashVal] != null){
if(hashArray[hashVal].iData == key){
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = nonItem; // nonitem- special data item,which is perfdefined with a key of -1
}
}
}