Skip to main content

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
}
}
}

Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Spring - Operations with jdbcTemplate

This class manages all the database communication and exception handling using a java.sql.Connection that is obtained from the provided DataSource. JdbcTemplate is a stateless and threadsafe class and you can safely instantiate a single instance to be used for each DAO.


Use of Callback Methods
JdbcTemplate is based on a template style of programming common to many other parts of Spring. Some method calls are handled entirely by the JdbcTemplate, while others require the calling class to provide callback methods that contain the implementation for parts of the JDBC workflow. This is another form of Inversion of Control. Your application code hands over the responsibility of managing the database access to the template class. The template class in turn calls back to your application code when it needs some detail processing filled in. These callback methods are allowed to throw a java.sql.SQLException, since the framework will be able to catch this exception and use its built-in excepti…