Thread: vector

whenever you try to add an element to this hash table, it will return false if a duplicate is found. Note that a duplicate is compared by .equals method of Object. Should be almost O(n) running time, unless there are large clusters.

public class HashTable<E>
{
    int                     size;
    ArrayList<ArrayList<E>> hash;
 
    /**
     * Creates an empty hash table with a given size
     * 
     * @param size
     */
    public HashTable (int size)
    {
        this.size = size;
        hash = new ArrayList<ArrayList<E>>();
        hash.ensureCapacity(size);
        for (int i = 0; i < size; i++)
        {
            hash.add(new ArrayList<E>());
        }
    }
 
    /**
     * Adds an element to the hash table.<br>
     * 
     * @param element
     * @return true if successfully added, false otherwise (duplicate)
     */
    public boolean add (E element)
    {
        if (hash.contains(element))
        {
                return false;
        }
        hash.get(hashFunction(element.toString())).add(element);
        return true;
    }
 
    /**
     * Determines if an element is in the hash table.
     * 
     * @param element
     * @return true if found, false otherwise
     */
    public boolean contains (E element)
    {
        // get a list of those that hash to the same value
        ArrayList<E> list = hash.get(hashFunction(element.toString()));
        for (int i = 0; i < list.size(); i++)
        {
            // try to find the element from the list
            if (list.get(i).equals(element))
            {
                return true;
            }
        }
        // didn't find element
        return false;
    }
 
    /**
     * Gets an element from the hash, if it exists.<br>
     * If duplicates (toString() matches), the first is returned.
     * 
     * @return the item (null if none)
     */
    public E get (E element)
    {
        // get a list of those that hash to the same value
        ArrayList<E> list = hash.get(hashFunction(element.toString()));
        for (int i = 0; i < list.size(); i++)
        {
            // find one who's to string matches, remove and return
            if (list.get(i).equals(element))
            {
                return list.get(i);
            }
        }
        // didn't find any, return
        return null;
    }
 
    /**
     * Removes an element from the hash, if it exists.<br>
     * If duplicates (toString() matches), the first is removed.
     * 
     * @return the removed item (null if none)
     */
    public E remove (E element)
    {
        // get a list of those that hash to the same value
        ArrayList<E> list = hash.get(hashFunction(element.toString()));
        for (int i = 0; i < list.size(); i++)
        {
            // find one who's to string matches, remove and return
            if (list.get(i).equals(element))
            {
                return list.remove(i);
            }
        }
        // didn't find any, return
        return null;
    }
 
    /**
     * @return the size of the hash table array
     */
    public int size ()
    {
        return size;
    }
 
    /**
     * Takes a string representation of an object and hashes it.
     * 
     * @param str
     * @return
     */
    private int hashFunction (String str)
    {
        int hashval = 0;
        for (int i = 0; i < str.length(); i++)
        {
            hashval = 37 * hashval + str.charAt(i);
        }
        hashval %= size;
        if (hashval < 0)
            hashval += size;
        return hashval;
    }
}