aud.example.hash.SimpleHashtable< T > Class Template Reference

Base class for simple hash tables (mainly for demonstration). More...

Collaboration diagram for aud.example.hash.SimpleHashtable< T >:

Public Member Functions
	SimpleHashtable (int size, HashFunction< T > hash, CollisionHandler< T > onCollision)
	create new hash table More...
int	getNumEntries ()
	get number of entries More...
int	getTableSize ()
	get size of hash table More...
float	getLoadFactor ()
	get load factor More...
String	toString ()
void	beginRecording ()
	start recording of history More...
void	nextTimeStep ()
	advance one time step in history, e.g., after every insert More...
SVGViewer	showHistory ()
	show history More...

Static Public Member Functions
static void	main (String args[])

Detailed Description

Base class for simple hash tables (mainly for demonstration).

Note:This class is intended to visualize hash tables, it is not an efficient or particularly useful implementation of a hash table!

Parameters

<T>	table entry

Definition at line 17 of file SimpleHashtable.java.

Constructor & Destructor Documentation

SimpleHashtable()

aud.example.hash.SimpleHashtable< T >.SimpleHashtable	(	int	size,
		HashFunction< T >	hash,
		CollisionHandler< T >	onCollision
	)

create new hash table

Parameters

size	size of table (could be any "bad" size, "good" sizes are prime)
hash	hash function
onCollision	strategy for collision handling, a value null forces separate chaining

Definition at line 49 of file SimpleHashtable.java.

                                         {
    hash_=hash;
    onCollision_=onCollision;
 
    table_.reserve(size);
    for (int i=0;i<size;++i)
      table_.push_back(new SList<T>());
  }

Member Function Documentation

beginRecording()

void aud.example.hash.SimpleHashtable< T >.beginRecording

(

)

start recording of history

Definition at line 154 of file SimpleHashtable.java.

                               {
    history_=new SparseMatrix<Integer>();
    time_=1;
    history_.set(getTableSize(),1,0);
 
    for (int i=0;i<table_.size();++i) {
      SList<T> bucket=table_.at(i);
      if (!bucket.empty())
        history_.set(i,time_,bucket.size());
    }
  }

Referenced by aud.example.hash.SimpleHashtable< T >.main().

Here is the caller graph for this function:

getLoadFactor()

float aud.example.hash.SimpleHashtable< T >.getLoadFactor

(

)

get load factor

Definition at line 67 of file SimpleHashtable.java.

                               {
    return (float) n_/(float) table_.size();
  }

Referenced by aud.example.hash.SimpleHashtable< T >.toString().

Here is the caller graph for this function:

getNumEntries()

int aud.example.hash.SimpleHashtable< T >.getNumEntries

(

)

get number of entries

Definition at line 61 of file SimpleHashtable.java.

{ return n_; }

Referenced by aud.example.hash.SimpleHashtable< T >.toString().

Here is the caller graph for this function:

getTableSize()

int aud.example.hash.SimpleHashtable< T >.getTableSize

(

)

get size of hash table

Definition at line 64 of file SimpleHashtable.java.

{ return table_.size(); }

Referenced by aud.example.hash.SimpleHashtable< T >.toString().

Here is the caller graph for this function:

main()

static void aud.example.hash.SimpleHashtable< T >.main ( String  args[] )

static

Definition at line 186 of file SimpleHashtable.java.

                                         {
    SimpleHashtable<Integer> h=
        new SimpleHashtable<Integer>(37,
              new HashFunction<Integer>() {
          public long hash(Integer i) { return i*13+7; }
              },null
              );
 
    h.beginRecording();
    for (int i=0;i<100;++i) {
      h.nextTimeStep();
      h.insert(i);
    }
    h.showHistory();
  }

References aud.example.hash.SimpleHashtable< T >.beginRecording(), aud.example.hash.SimpleHashtable< T >.nextTimeStep(), and aud.example.hash.SimpleHashtable< T >.showHistory().

Here is the call graph for this function:

nextTimeStep()

void aud.example.hash.SimpleHashtable< T >.nextTimeStep

(

)

advance one time step in history, e.g., after every insert

Definition at line 167 of file SimpleHashtable.java.

                             {
    // copy previous row
    Vector<Integer> cnt=history_.getColumnEntries(time_);
    int[] ri=history_.getColumnRowIndices(time_);
    ++time_;
 
    int i=0;
    for (Integer c : cnt)
      history_.set(ri[i++],time_,c);
  }

Referenced by aud.example.hash.SimpleHashtable< T >.main().

Here is the caller graph for this function:

showHistory()

SVGViewer aud.example.hash.SimpleHashtable< T >.showHistory

(

)

show history

Definition at line 179 of file SimpleHashtable.java.

                                 {
    return history_.spy(
        "size m="+getTableSize()+", n="+getNumEntries()+
        ", n/m="+getLoadFactor()+" ("+time_+" time steps)",
        new ColormapCount());
  }

Referenced by aud.example.hash.SimpleHashtable< T >.main().

Here is the caller graph for this function:

toString()

String aud.example.hash.SimpleHashtable< T >.toString

(

)

Definition at line 130 of file SimpleHashtable.java.

                                     {
    String s=
      "SimpleHashTable [m="+getTableSize()+
      ", n="+getNumEntries()+", n/m="+getLoadFactor()+", counted "+nCollisions_+
      " collisions]\n";
    for (int i=0;i<table_.size();++i) {
      SList<T> bucket=table_.at(i);
      s+=i+": ";
      if (!bucket.empty())
        s+=bucket.toString();
      s+="\n";
    }
    return s;
  }

References aud.example.hash.SimpleHashtable< T >.getLoadFactor(), aud.example.hash.SimpleHashtable< T >.getNumEntries(), and aud.example.hash.SimpleHashtable< T >.getTableSize().

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• SimpleHashtable.java