    All Packages  Class Hierarchy  This Package  Previous  Next  Index

# Class DataStructures.ProbingHashTable

    java.lang.Object
        |
        +----DataStructures.ProbingHashTable

public abstract class ProbingHashTable
extends Object
implements HashTable

Probing table implementation of hash tables. This is an abstract class that must be extended to implement a particular probing algorithm, such as quadratic probing. Note that all "matching" is based on the equals method.

##

array
  The array of elements.

##

ProbingHashTable()
  Construct the hash table.

##

find(Hashable)
  Find an item in the hash table.
findPos(Hashable)
  Abstract method that performs collision resolution.
hash(String, int)
  A hash routine for String objects.
insert(Hashable)
  Insert into the hash table.
makeEmpty()
  Make the hash table logically empty.
remove(Hashable)
  Remove from the hash table.

##

array

    protected HashEntry[] array

  The array of elements.

##

ProbingHashTable

    public ProbingHashTable()

  Construct the hash table.

##

findPos

    protected abstract int findPos(Hashable x)

  Abstract method that performs collision resolution. Each class must override this method only.

  Parameters:
    x - the item to search for.
  Returns:
    the position where the search terminates.

insert

    public final void insert(Hashable x)

  Insert into the hash table. If the item is already present, then replace it with the new item.

  Parameters:
    x - the item to insert.

remove

    public final void remove(Hashable x) throws ItemNotFound

  Remove from the hash table.

  Parameters:
    x - the item to remove.
  Throws: ItemNotFound
    if no item that matches x can be found in the hash table.

find

    public final Hashable find(Hashable x) throws ItemNotFound

  Find an item in the hash table.

  Parameters:
    x - the item to search for.
  Returns:
    the matching item.
  Throws: ItemNotFound
    if no item that matches x can be found in the hash table.

makeEmpty

    public final void makeEmpty()

  Make the hash table logically empty.

hash

    public static final int hash(String key,
                                 int tableSize)

  A hash routine for String objects.

  Parameters:
    key - the String to hash.
    tableSize - the size of the hash table.
  Returns:
    the hash value.

    All Packages  Class Hierarchy  This Package  Previous  Next  Index