public class HashTable {

    EntryList[] arr;
    int size;
    
    /* A simple linked list of entries.
     */
    private class EntryList {
      	Object first;
      	EntryList rest;

      	EntryList( Object first, EntryList rest ) {
	          this.first = first;
      	    this.rest = rest;
       	}
    }
    
    /* Creates an empty hashtable with an array of length init.
     */
    public HashTable( int init ) {
    		arr = new EntryList[init];
    		size = 0;
    }

    /* Returns the size.
     */
    public int getSize() {
		    return size;
    }

    /* Adds x to the hashtable
     */
    public void add( Object x ) {
    
		    int ix = Math.abs(x.hashCode() % arr.length);
    		EntryList entLi = arr[ix];
	
		    if ( entLi != null ) {
		        while ( entLi.rest != null ) {
		        		if ( entLi.first.equals( x ) )
		        		    return;
        				entLi = entLi.rest;
		        }

      	    entLi.rest = new EntryList(x,null);
	      }
	      else
	          arr[ix] = new EntryList(x,null);
	          
	    	size++;
    }
    
    /* Checks if x is in the hashtable.
     */
    public boolean contains( Object x ) {

		    int ix = Math.abs(x.hashCode()) % arr.length;
	
		    for ( EntryList entLi = arr[ix]; entLi != null; entLi = entLi.rest )
		        if ( entLi.first.equals( x ) )
		          	return true;
	
		    return false;
		    
    }
    
    /* Removes x from the hashtable.
     */
    public void remove( Object x ) {
	
    		int ix = Math.abs(x.hashCode() % arr.length);
    		EntryList entLi = arr[ix];
	
    		if ( entLi != null ) {
		        while ( entLi.rest != null ) {
		        		if ( entLi.rest.first.equals( x ) ) {
		        		    entLi.rest = entLi.rest.rest;
		        		    size--;
		        		    return;
        				}
      		    	entLi = entLi.rest;
     		    }
		    }
    }
    
}