dblopenadrhashtableuos.java

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

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

package dslib.hashtable;

/**	A HashTable dictionary that uses double open addressing. */
public class DblOpenAdrHashTableUos extends OpenAdrHashTableUos
{    
	
	/**	Create hash table structure with at least size locations. 
		(dummyItem is an artifical impossible item) <br>
		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 DblOpenAdrHashTableUos(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 ((Math.abs(y.hashCode()) / capacity() + (Math.abs(y.hashCode()))) % (capacity() -1)) + 1;
	}

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