// This is a memory efficient hashtable class.
//
// A typical hashtable associates a key with a reference.
// The key is hashed to obtain a hashkey which is then mapped
// to an array, often with a modulus function.
//
// With an array of size n, the hashkey will be mapped to:
// hashkey % n
// If that array location is null, a list will be added there,
// containing the hashkey & reference, if a list is already at
// that array location, the hashkey & reference will be concatenated
// to that list. After adding the hashkey, a count will be incremented,
// if that count is greater than the load factor times the array size,
// a new array will be created of typically size 2n + 1 and all the
// hashkey & reference pairs will be added from the old array. The old
// array and all its associated lists is then deleted, either
// explicitly or it is eventually garbage collected.
//
// The problem with this is that there are many small pieces of memory
// allocated for each list in the array, which is an inefficient way
// of storing data. Also, deleting the array and the many associated
// lists takes considerable CPU time and / or memory one way or
// another.
//
// Another way of implementing a hashtable once you have a hashkey is
// to have an array of size n and successive arrays of size
// 2 * the preceding array size + 1. When adding a hashkey & reference,
// the hashkey is mapped to the size of the largest array:
// hashkey % ( largest array size )
// If that array location is null, the hashkey & reference is added
// there. If a hashkey & reference is already at that array location,
// the next largest array is checked. The hashkey is mapped to the
// size of the next largest array:
// hashkey % ( next largest array size )
// if that array location is null, the hashkey and reference is added
// there. If a hashkey & reference is already at that array location,
// if there is a next largest array is that is checked in turn in the
// same way. If there isn't a next largest array, then a new array of
// size 2 * ( largest array size ) + 1 is created. The hashkey &
// reference pair are added to this array. Then all the hashkey &
// reference pairs from the old arrays are added to this array, the
// hashkey & reference pairs from the smallest array being transfered
// first.
//
// This way, as the hashtable grows, nothing need be deleted only
// transfered. All the arrays will still be used, no matter how many
// hashkey & reference pairs are added. Also, relatively few arrays
// or lists will be created in the first place, roughly log( n )
// arrays will be allocated, versus the roughly n arrays allocated
// in the typical hashtable. Finally, when a hashkey & reference is
// added, a count doesn't need to be incremented, only when another
// array has to be created is anything done other than seeing if
// there is a place, then adding the hashkey & reference. For these
// reasons, the hashtable is quite fast, roughly twice as fast as
// the typical java hashtable. Unfortunately, I'm running on Linux
// now and don't have a java environment so can't benchmark here.
//
// I'd like to know if this kind of hashtable has been implemented
// before August 1999 and if it hasn't been, this algorithim is
// hereby in the public domain with no patent restrictions and the
// code is under the GPL. I'd appreciate it if someone were to
// benchmark this and port it over to C / C++. I can be reached
// at perez_enrique@yahoo.com
//

package qlaw.math;

import java.util.Enumeration;

/**
 * This class is meant to be used within IntHashtable
 */

public class LastIntTable
{
 public final static int cNeverNumber = - 1234567899;

 public int m_ArraySize;

 public int m_IntArray[];

 public LastIntTable m_DeeperTable;

 public Object m_ObjectArray[];

 public
 LastIntTable()
 {
 }

 public void
 add( int inKey, Object inObject )
 {
  int arrayIndex = getArrayIndex( inKey );

  if ( m_ObjectArray[ arrayIndex ] == null || m_IntArray[ arrayIndex ] == inKey ) {
   m_IntArray[ arrayIndex ] = inKey;
   m_ObjectArray[ arrayIndex ] = inObject;

   return;
  }

// create new IntHashtable and attach it to outer IntHashtable

  IntHashtable intHashtable = new IntHashtable(
   m_DeeperTable.m_ArraySize,
   m_DeeperTable.m_IntArray,
   m_DeeperTable.m_DeeperTable,
   m_DeeperTable.m_ObjectArray );

  int doubledSize = getDoubledSize( m_DeeperTable.m_ArraySize );

  m_DeeperTable.setSizeAndArraysTable(
   doubledSize, new int[ doubledSize ], intHashtable, new Object[ doubledSize ] );

// transfer

  m_DeeperTable.add( inKey, inObject );
  intHashtable.transfer( m_DeeperTable );
 }

 public Object
 get( int inKey )
 {
  int arrayIndex = getArrayIndex( inKey );

  if ( m_IntArray[ arrayIndex ] == inKey ) {
   return m_ObjectArray[ arrayIndex ];
  }

  return null;
 }

 public int
 getArrayIndex( int inKey )
 {
  return ( inKey & 0x7FFFFFFF ) % m_ArraySize;
 }

 public int
 getDoubledSize( int inSize )
 {
  return 2 * inSize + 1;
 }

 public Object
 remove( int inKey )
 {
  int arrayIndex = getArrayIndex( inKey );

  Object outObject = m_ObjectArray[ arrayIndex ];

  m_IntArray[ arrayIndex ] = cNeverNumber;
  m_ObjectArray[ arrayIndex ] = null;

  return outObject;
 }

 public void
 setSizeAndArraysTable(
  int inSize, int inLongArray[], LastIntTable inLastIntTable, Object inObjectArray[] )
 {
  m_ArraySize = inSize;

  m_IntArray = inLongArray;
  m_ObjectArray = inObjectArray;

  m_DeeperTable = inLastIntTable;
 }

 public void
 transfer( LastIntTable inLastIntTable )
 {
  for ( int index = 0; index < m_ArraySize; index++ ) {
   if ( m_ObjectArray[ index ] != null ) {
    int oldInt = m_IntArray[ index ];

    Object oldObject = m_ObjectArray[ index ];

    m_IntArray[ index ] = cNeverNumber;
    m_ObjectArray[ index ] = null;

    inLastIntTable.add( oldInt, oldObject );
   }
  }
 }
}

public class IntHashtable extends LastIntTable
{
 final static int cInitialSize = 23;

 public
 IntHashtable()
 {
  initialize( cInitialSize );
 }

 public
 IntHashtable( int inInitialSize )
 {
  initialize( inInitialSize );
 }

 public
 IntHashtable(
  int inSize,
  int inIntArray[],
  LastIntTable inLastIntTable,
  Object inObjectArray[] )
 {
  setSizeAndArraysTable( inSize, inIntArray, inLastIntTable, inObjectArray );
 }

 public void
 add( int inKey, Object inObject )
 {
  int arrayIndex = getArrayIndex( inKey );

  if ( m_ObjectArray[ arrayIndex ] == null || m_IntArray[ arrayIndex ] == inKey ) {
   m_IntArray[ arrayIndex ] = inKey;
   m_ObjectArray[ arrayIndex ] = inObject;

   return;
  }

  m_DeeperTable.add( inKey, inObject );
 }

 public Object
 get( int inKey )
 {
  int arrayIndex = getArrayIndex( inKey );

  if ( m_IntArray[ arrayIndex ] == inKey ) {
   return m_ObjectArray[ arrayIndex ];
  }

  return m_DeeperTable.get( inKey );
 }

 public Enumeration
 getEnumerator()
 {
  return new IntEnumerator( this );
 }

 public void
 initialize( int inInitialSize )
 {
  LastIntTable lastResortTable = new LastIntTable();

  int doubleSize = getDoubledSize( inInitialSize );

  setSizeAndArraysTable(
   doubleSize, new int[ doubleSize ], lastResortTable, new Object[ doubleSize ] );

  lastResortTable.setSizeAndArraysTable(
   inInitialSize, new int[ inInitialSize ], this, new Object[ inInitialSize ] );
 }

 public Object
 remove( int inKey )
 {
  if ( m_IntArray[ getArrayIndex( inKey ) ] == inKey ) {
   super.remove( inKey );
  }

  return m_DeeperTable.remove( inKey );
 }

 public void
 transfer( LastIntTable inLastIntTable )
 {
  m_DeeperTable.transfer( inLastIntTable );

  super.transfer( inLastIntTable );
 }
}

/**
 * An IntEnumerator enumerator class.  This class should remain opaque
 * to the client. It will use the Enumeration interface.
 */
public class IntEnumerator implements Enumeration {
 final static protected int cNeverNumber = - 10;

 protected int m_Index = 0;

 protected LastIntTable m_LastIntTable;
 protected LastIntTable m_OriginalTable;

 public
 IntEnumerator( LastIntTable inLastIntTable ) {
  m_OriginalTable = inLastIntTable;
  m_LastIntTable = m_OriginalTable;
 }

 public boolean
 hasMoreElements() {
  if ( m_Index == cNeverNumber ) {
   return false;
  }

  while ( true ) {
   if ( m_LastIntTable.m_ObjectArray[ m_Index ] != null ) {
    return true;
   }

   m_Index++;

   if ( m_Index >= m_LastIntTable.m_ArraySize ) {
    m_LastIntTable = m_LastIntTable.m_DeeperTable;

    if ( m_LastIntTable == m_OriginalTable ) {
     m_Index = cNeverNumber;

     return false;
    }
    else {
     m_Index = 0;
    }
   }
  }
 }

 public Object
 nextElement() {
  if ( m_Index == cNeverNumber ) {
   return null;
  }

  while ( true ) {
   Object outObject = m_LastIntTable.m_ObjectArray[ m_Index ];

   m_Index++;

   if ( outObject != null ) {
    if ( m_Index >= m_LastIntTable.m_ArraySize ) {
     m_LastIntTable = m_LastIntTable.m_DeeperTable;

     if ( m_LastIntTable == m_OriginalTable ) {
      m_Index = cNeverNumber;
     }
     else {
      m_Index = 0;
     }
    }

    return outObject;
   }

   if ( m_Index >= m_LastIntTable.m_ArraySize ) {
    m_LastIntTable = m_LastIntTable.m_DeeperTable;

    if ( m_LastIntTable == m_OriginalTable ) {
     m_Index = cNeverNumber;

     return null;
    }
    else {
     m_Index = 0;
    }
   }
  }
 }

 public void
 reset() {
  m_LastIntTable = m_OriginalTable;
  m_Index = 0;
 }
}
 
 
 

Feedback   Free Electronic Nation Home    Invention   GNU Free Documentation License