chainedhashtableuos.java

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

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

package dslib.hashtable;

import dslib.exception.*;
import dslib.list.*;
import dslib.base.*;

/**	A HashTable dictionary that uses chaining.  Items can be 
	inserted, deleted, obtained, and searched for by hashValue.  
	An iterator is included, with functions goFirst, goForth, 
	before, and after */
public class ChainedHashTableUos extends HashTableUos
{ 
	/**	Array to store linked lists for separate chaining. */
	protected LinkedListUos[] hashArray;
  
	/**	Position of the current item in its list. */
	protected LinkedIteratorUos itemListLocation;
  
	/**	Create a new hash list for a new chain. <br>
		Analysis: Time = O(1)  */
	protected LinkedListUos newChain()
	{
		LinkedListUos result = new LinkedListUos();
		result.compareContents();
		return result;
	}

	/**	Construct hash table strucuture with at least newSize locations. <br> 
		Analysis: Time = O(newSize^2)
		@param newSize size of the hash table is at least this large */
	public ChainedHashTableUos(int newSize)
	{
		compareContents();
		hashArray = new LinkedListUos[higherPrime(newSize)];
		count = 0;
		itemListLocation = null;
	}

	/**	Size of the hash table. <br> 
		Analysis: Time = O(1) */
	public int capacity()
	{
		return hashArray.length;	
	}	
  
	/**	Is the hash table full?. <br>  
		Analylsis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	Is there a current item?. <br>  
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return (itemListLocation!=null) && (itemListLocation.itemExists());
	}
    
	/**	The current item. <br>  
		Analysis: Time = O(1) <br> 
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item that does not exist.");
			
		return itemListLocation.item();
	}
  
	/**	Does the hash table contain y?. <br>  
		Analysis: Expected time = time for search 
		@param y item being sought */
	public boolean has(Object y)
	{
		LinkedIteratorUos saveListLocation;
		if(itemListLocation != null)
			saveListLocation = (LinkedIteratorUos)itemListLocation.clone();
		else
			saveListLocation = null;
		search(y);
		boolean result = itemExists();
		itemListLocation = saveListLocation;
		return result;
	}
  
	/**	Insert y. <br>  
		Analysis: Time = O(1) 
		@param y item to insert in the hash table */
	public void insert(Object y) 
	{
		int itemHashLocation = hashPos(y);
		if (hashArray[itemHashLocation]==null)
			hashArray[itemHashLocation] = newChain();
		
		hashArray[itemHashLocation].insert(y);
		count++;
	}
  
	/**	Remove the entry y from the table. <br> 
		Analysis: Expected Time = O(1 + loadFactor/2) <br> 	
		PRECONDITION: <br>
		<ul>
			has(y) 
		</ul> 
		@param y item to delete from the hash table */
	public void delete(Object y) throws ItemNotFoundUosException
	{           
		if (!has(y)) 
			throw new ItemNotFoundUosException("Cannot delete item because it is not in the table.");
		
		if (itemExists() && membershipEquals(y, item()))
			deleteItem();
		else
		{
			hashArray[hashPos(y)].delete(y);
			if ( (itemExists()) && (hashPos(y) == hashPos(itemListLocation.item())))
				search(item()); // deletion might have messed up item list location
			count--;
		}
	}
  
	/**	Delete the current item and move to the next item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		Object deleteItem = item();
		goForth(); // deletion should cause a move to the next item.
		hashArray[hashPos(deleteItem)].delete(deleteItem);
		if (itemExists())
			search(item()); // the deletion probably destroyed prev. reference.
		count--;     
	}

	/**	Move to item y (the next occurrence if searchesContinue). <br> 
		Analysis: Successful Average Time   = O(1 + loadFactor/2) <br>	
			       Unsuccessful Average Time = O(loadFactor + e^-loadFactor) 
		@param y item being sought */
	public void search(Object y) 
	{
		int itemHashLocation = hashPos(y);
		if (searchesContinue && itemListLocation!=null)
			goForth();
		else
		{
			if (hashArray[itemHashLocation]==null)
				hashArray[itemHashLocation] = newChain();
			itemListLocation = (LinkedIteratorUos)hashArray[itemHashLocation].iterator();
		}
		while (!itemListLocation.after() && !membershipEquals(y, itemListLocation.item()))
			itemListLocation.goForth();
	}
  
	/**	Return item y from the hash table. <br> 
		Analysis: Successful Average Time = O(1 + loadFactor/2) <br>
		               Unsuccessful Average Time = O(loadFactor + e^-loadFactor) <br>
		PRECONDITION: <br>
		<ul>
			has(y) 
		</ul>
		@param y item to obtain from the hash table */
	public Object obtain(Object y) throws ItemNotFoundUosException
	{
		if (!has(y))
			throw new ItemNotFoundUosException("Cannot return an item that does not exist");
	
		return hashArray[hashPos(y)].obtain(y);
	}

	/**	Are we before the first item in the hash table?. <br> 
		Analysis: Time = O(1) */
	public boolean before() 
	{
		return (itemListLocation==null) || (itemListLocation.before());
	}
  
	/**	Are we after the last item in the hash table?. <br>
		Analysis: Time = O(1) */  
	public boolean after()
	{
		return (itemListLocation!=null) && (itemListLocation.after());
	}

	/**	Advance one item in the data structure. <br> 
		Analysis: Time = O(capacity()) - worst case <br>
		PRECONDITION: <br>
		<ul>
			!after() 
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot goForth() when at the end of the table");

		if (itemListLocation==null || itemListLocation.before())
			goFirst();
		else
		{
			int itemHashLocation = hashPos(item());
			itemListLocation.goForth();
			if (itemListLocation.after())
				findNextItem(itemHashLocation + 1);
		}
	}

	/**	Go to first item of the data structure (if it exists). <br> 
		Analysis: Time = O(capacity()) - worst case */
	public void goFirst()
	{
		findNextItem(0);
	}
 
	/**	Move to prior to the first item. <br>
		Analysis: Time = O(capacity()) - worst case */ 
	public void goBefore() 
	{
		itemListLocation.goBefore();
	}

	/**	Move to after the last item. <br> 
		Analysis: Time = O(1) */
	public void goAfter() 
	{
		itemListLocation = (LinkedIteratorUos)hashArray[hashArray.length-1].iterator();
		itemListLocation.goAfter();
	}

	/**	Go to the first item of the next non-empty list,
		starting at index, or goAfter() if none found. <br> 
		Analysis: Time = O(capacity()) - worst case.
		@param index first hash value to search to find the next item */
	protected void findNextItem(int index)
	{
		int itemHashLocation = index;
		while ((itemHashLocation<=(hashArray.length-1))
			 && ((hashArray[itemHashLocation]==null) || (hashArray[itemHashLocation].isEmpty())))
		{	  
			itemHashLocation++;
		}
		if (itemHashLocation<hashArray.length)
		{
			itemListLocation = (LinkedIteratorUos) hashArray[itemHashLocation].iterator();
			itemListLocation.goFirst();
		}
		else if (itemListLocation==null)
			itemListLocation = new LinkedIteratorUos(new LinkedBasicListUos());
	}  

	/**  	An iterator at the current position. <br> 
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{        
		if(itemListLocation != null) 
        		return (LinkedIteratorUos)itemListLocation.clone();
        	else
        		return null;
   	}

   	/**	Go to the position in the hash array specified by pos. <br> 
       		Analysis: Time = O(1)
       		@param pos position to which to move */
   	public void goPosition(CursorUos pos) 
   	{
   		if(pos != null) 
        		itemListLocation = (LinkedIteratorUos)((LinkedIteratorUos)pos).clone();
		else
			itemListLocation = null;
   	}

	/**	String representation of all the items in the hash table. <br> 
		Analysis: Time = O(capacity + count) */
	public String toString()
	{
		String result = new String();
		for (int i=0; i<capacity(); i++)
			if (hashArray[i]!=null)
				result += "\n" + i + ": " + hashArray[i].toString();
		return result;	
	}
    
	/**	Remove all items from the hash table. <br>
		Analysis: Time = O(capacity()) */
	public void wipeOut()
	{
		for (int i=0; i<capacity(); i++)
			hashArray[i]=null;
		count = 0;
		itemListLocation = null;
	}

}