hashtabledictionary.java

Java数据结构开发包

	  return toret;
	  /*
	  // find(key) checks for invalid keys.
	  HashtableData toRemove = (HashtableData)(find(key));
	  
	  if (toRemove != NO_SUCH_KEY) {
	      // link the chain around the removed node.
	      if (toRemove.prev() != null)
		  (toRemove.prev()).setNext(toRemove.next());
	      if (toRemove.next() != null)
		  (toRemove.next()).setPrev(toRemove.prev());
	      // make the locator uncontained.
	      toRemove.setContainer(null);
	      size_--;
	      // trim the size if it is excessive.
	      downhash(); // downhash performs the size << capacity check.
	      // structure has changed. clear all caches
	      clearCaches();
	  }
	  return toRemove;
	  */
    }


    /**
      * O(1) expected, O(N) if insertion pushes the size above the
      * rehashing threshhold.
      */
    public Locator insert(Object key, Object value) 
      throws InvalidKeyException {
	checkKey(key);
	rehash(); // rehash performs size >= capacity check.
	int index = dataIndex(key);
      
	// We want to allow multiple elements with the same
	// key. always insert a new one.
	HashtableData toInsert = 
	  new HashtableData(key, value, this, data_[index], null);
 
	data_[index] = toInsert;
	size_++;
	// structure has changed. clear all caches
	clearCaches();
	return toInsert;
    }

    /**
      * O(1) -- expected, O(N) worst case with excessive chaining.
      */
    public Locator find (Object key) 
      throws InvalidKeyException {
      checkKey(key);
      int index=dataIndex(key);
      HashtableData current=data_[index];
      while(current!=null) {
	if(comp_.isEqualTo(current.key(),key))
	  return current;
	current=current.next();
      }
      return NO_SUCH_KEY;
    }
     
    /**
      * O(N+C) Returns an array of all the Locators in this hashtable.
      */
    private HashtableData[] data() {
      if(size()==0) return new HashtableData[0];
      HashtableData[] toRet=new HashtableData[size()];
      HashtableData current;
      int index=0;
      int curcap=capacity();
      for(int i=0;i<curcap;i++) {
	current=data_[i];
	while(current!=null) {
	  toRet[index++]=current;
	  current=current.next();
	}
      }
      return toRet;
    }

    /** 
      * O(1) Gets the capacity of this hashtable.  The capacity is
      * cached to avoid accessing data_.length many times.  
      */
    private int capacity() {
      return capacity_;
    }

    /**
     * O(N) this method increases the capacity of the hashtable when
     * the current capacity is reached and rehashes all of the
     * elements into the larger hashtable.  
     */
    private void rehash() {
      if(size_==0) {
	initEmpty();
      } 
      else if (nextPrime_ >= PRIMES.length) {
	throw new FullContainerException("Hashtable cannot hold any more data elements");
      }
      else if (size() >= capacity()){
	rebuildTable();
      }
    }

    /**
     * O(N+C) This method reduces the capacity of the hashtable when
     * the size becomes sufficiently small.  
     */
    private void downhash() {
      if(size_==0) {
	initEmpty();
      }
      else {
	// get the 1st prime larger than the size of the container
	int currPrime;
	for (currPrime = 0;PRIMES[currPrime] < size();currPrime++);
	// if currPrime = nextPrime_-1, the same table will be
	// created.  if currPrime = nextPrime_, a larger table will be
	// created.  if currPrime > nextPrime_, duck and cover, thes
	// baby's about to blow.
	if (currPrime < nextPrime_ -1) {
	  nextPrime_ = currPrime +1;// ensure capacity != size + (a
	                            // small constant)
	  rebuildTable();
	}
      }
    }
    
    /** 
     * O(N+C) This method rebuilds the hashtable with capacity
     * PRIMES[nextPrime_], and increments nextPrime_ in anticipation
     * of the next increase in capacity. 
     */
    private void rebuildTable() {
      // get the current state
      int currSize             = size();
      HashtableData currData[] = data();
      HashtableData toInsert; // temporary storage in the for loop
      int index; // the table slot at which to insert the datum.

      // build the new state
      capacity_ = PRIMES[nextPrime_++];
      data_     = new HashtableData[capacity_];
      size_     = 0;
      for(int i=0; i<currSize; i++) {
	// simple insertion code 
	toInsert = currData[i];
	index = dataIndex(toInsert.key());
	toInsert.setNext(data_[index]);
	if (data_[index] != null)
	  data_[index].setPrev(toInsert); 
	toInsert.setPrev(null); // chain is null terminated at both ends
	data_[index] = toInsert;
	size_++;
      }
      // structure has changed. clear all caches
      clearCaches();
    }

    /**
      * Writes a HashtableDictionary out to a serialized form.
      *
      *@exception java.io.IOException
      */
    private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {
      // output the size of the hashtable
      s.writeInt(size());
        
      if(size()==0) return;
        
      // output all the <key,element> pairs
      HashtableData data[] = data();

      for(int i=0; i<size(); i++) {
	s.writeObject(data[i].key());
	s.writeObject(data[i].element());
      }
    }

    /**
      * Reads a HashtableDictionary in from a serialized form.
      *
      *@exception java.io.IOException
      *@exception java.lang.ClassNotFoundException
      */
    private void readObject(java.io.ObjectInputStream s) 
      throws java.io.IOException,ClassNotFoundException {
      // read the actual size
      int size=s.readInt();

      if(size==0) {
	initEmpty();
	return;
      }
      else {
	for(int nextPrime_ = 0; PRIMES[nextPrime_]<size; 
	    nextPrime_++);
	capacity_= PRIMES[nextPrime_];

	// allocate the table, fill it.
	data_=new HashtableData[capacity_];
	for(int i=0;i<size;i++) {
	  insert(s.readObject(),s.readObject());
	}
      }
    }

    /** 
      * Convenience method to test if a given accessor is contained
      * within this data structure.
      *
      *@exception InvalidAccessorException
      */
    private HashtableData checkContained(Accessor acc)
      throws InvalidAccessorException {
	HashtableData toCast = castData(acc);
	if (toCast.container() != this)
	  throw new InvalidAccessorException("Accessor is contained in another data structure.");
	return toCast;
    }

    /** 
      * Convenience method to test if a given accessor is of the
      * appropriate type for this here hashtable.
      *
      *@exception InvalidAccessorException
      */
    private HashtableData castData(Accessor acc)
      throws InvalidAccessorException {
	if (acc==null)
	  throw new InvalidAccessorException("Accessor is null.");
	else if (acc instanceof HashtableData) {
	  return (HashtableData)acc; 
	}
	else 
	  throw new InvalidAccessorException("Accessor must extend HashtableData.");
    }

    /** 
      * Convenience method to test if a given key is of the
      * appropriate type for this here hashtable.
      *
      *@exception InvalidKeyException
      */
    private void checkKey(Object key) {
      if (!(comp_.isComparable(key)))
	throw new InvalidKeyException("Key is of inappropriate type.");   
    }
  
    /** 
      * O(N) human readable description of the contents of this
      * dictionary, conforming to the Collections spec for key-element
      * structures.  
      */
    public String toString() {
      return ToString.stringfor(this);
    }

    /**
      * O(1) this method clears all of the caches used in Iterator
      * generation and should be called after every structural change
      * to the Container.  
      */
    private void clearCaches() {
      locatorCache_ = null;
      keyCache_ = null;
      elementCache_ = null;
    }

    /** 
      * O(1) this method clears the element cache. it should be called
      * after replaceElement(.)  
      */
    private void clearElementCache() {
      elementCache_ = null;
    }

    /**
      * O(1) computes the hash value of the object with the
      * HashComparator and reduces it modulo the size of the
      * underlying array.  
      */
    private int dataIndex(Object key) {
      return (comp_.hashValue(key)%capacity());
    }


  // nested class(es)
  
  /** 
   * This is the implementation of the Locator interface used
   * within the hashtable.  
   */
  private static class HashtableData implements Locator{
    /**
     * The key.  
     */
    private Object iKey;
    /**
     * The element.
     */
    private Object iElement;
    /**
     * The next node in the chain.
     */
    private HashtableData iNext;
    /**
     * The previous node in the chain.
     */
    private HashtableData iPrev;
    /** 
     *The jdsl.core.api.Container in which this Locator resides 
     */
    private Container iContainer;
    /**
     * constructs a new node with no successor or predecessor.
     */
    HashtableData(Object key, Object element, Container cont) {
      this(key,element,cont,null, null);
    }
    /**
     * Constructs a new node with a successor and a predecessor.
     */
    HashtableData(Object key, Object element, Container cont, 
		  HashtableData next, HashtableData prev) {
      iKey=key;
      iElement=element;
      iContainer=cont;
      iNext=next;
      if (iNext != null)
	iNext.setPrev(this);
      iPrev=prev;
      if (iPrev != null)
	iPrev.setNext(this);
    }
    
    /**
     * O(1) accessor for the key held by this Locator
     */
    public Object key() {return iKey;}
    
    /**
     * O(1) accessor for the element held by this Locator
     */
    public Object element() {return iElement;}
    
    /**
     * O(1) accessor for the Container which holds Locator
     */
    private Container container() {return iContainer;}
    
    /**
     * O(1) accessor for the next Locator in the chain
     */
    private HashtableData next() {return iNext;}
    
    /**
     * O(1) accessor for the previous Locator in the chain
     */
    private HashtableData prev() {return iPrev;}
    
    
    /**
     * O(1) mutator for the key held by this Locator
     */
    private void setKey(Object newKey) {iKey = newKey;}
    
    /**
     * O(1) mutator for the element held by this Locator
     */
    private void setElement(Object newElement) {iElement = newElement;}
    
    /**
     * O(1) mutator for the next Locator in the chain
     */
    private void setNext(HashtableData newNext) {iNext = newNext;}
    
    /**
     * O(1) mutator for the previous Locator in the chain
     */
    private void setPrev(HashtableData newPrev) {iPrev = newPrev;}
    
    /**
     * O(1) mutator for the Container which holds Locator
     */
    private void setContainer(Container newCont) {iContainer = newCont;}
    
    
    /** 
     * O(1) human readable description of the contents of this
     * locator, conforming to the Collections spec for key-element
     * structures.  
     */
    public String toString () {
      return ToString.stringfor(this);
    }
  }
}