linopenadrhashtableuos.java

国外的数据结构与算法分析用书

/* LinOpenAdrHashTableUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.hashtable;

/**	A HashTable dictionary that uses open addressing with linear
	probing.  Its methods include insert, delete, obtain, search,
	has, and frequency.  There are also the iterator functions
	goFirst, goForth, before, and after.  The table can be set
	to grow as needed. */
public class LinOpenAdrHashTableUos extends OpenAdrHashTableUos
{    
	/**	Create hash table structure with at least size locations. <br>
		(dummyItem is an artificial impossible item.) 
		Analysis: Time = O(size*size) 
		@param size size of the hash table is at least this large 
		@param dummyItem object used to mark deletions; should not be possible to
		be inserted as a normal item */
	public LinOpenAdrHashTableUos(int size, Object dummyItem)
	{
		super(size, dummyItem);
	}

	/**	The step size for the probe sequence. <br>
		Analysis : Time = O(1) 
		@param y item for which the hashing displacement is to be found */
	public int hashCodeDisplacement(Object y)
	{
		return 1;
	}

	/**	A new instance of a LinOpenAdrHashTableUos. <br>
		Analysis: Time = O(1) */
	public OpenAdrHashTableUos newInstance(int newSize, Object dummyItem)
	{
		return new LinOpenAdrHashTableUos(newSize, dummyItem);
	}
}