Results 1 to 3 of 3
  1. #1
    bap2 is offline Member
    Join Date
    Oct 2010
    Posts
    20
    Rep Power
    0

    Default Need help with hashtable chain

    I need help with the remove and rehash methods. Here is my code

    Java Code:
    import java.util.*;
    public class HashtableChain<K , V>
    {
        private LinkedList<Entry<K, V>>[] table; //the hash table
        private int numKeys; //the number of elements within hash table
        private static final int INITIAL_CAPACITY = 101; // the size of the table
        private static final double LOAD_THRESHOLD = 3.0; //the max load factor
    
        private static class Entry<K, V>
        {
            private K key;
            private V value;
    
            public Entry(K key, V value)
            {
                this.key = key;
                this.value = value;
            }
    
            public K getKey()
            {
                return key;
            }
    
            public V getValue()
            {
                return value;
            }
    
            public V setValue(V val)
            {
                V oldVal = value;
                value = val;
                return oldVal;
            }
        }
    
        public HashtableChain() //constructor
        {
            table = new LinkedList[INITIAL_CAPACITY];
        }
    
        /**
         * Method get for class HashtabelChain
         * @param key The key being sought
         * @return the value associated with this key if found; otherwise, null
         */
        public V get(K key)
        {
            int index = key.hashCode() % table.length;
    
            if(index < 0)
            {
                index += table.length;
            }
    
            if(table[index] == null)
            {
                return null; //key is not in table
            }
    
            //Search the list at table[index] to find the key
            for(Entry<K, V> nextItem : table[index])
            {
                if(nextItem.key.equals(key))
                    return nextItem.value;
            }
    
            //Key is not in the table
            return null;
        }
    
        /**
         * Method put for class HashtableChain.
         * post: This key-value pair is inserted in the table and numKeys is incremented.
         *       If the key is already in the table, its value is changed to the argument
         *       value and numKeys is not changed.
         * @pram key The key of the item being inserted
         * @pram value The value for this key
         * @return The old value associated with this key if found; otherwise, null
         */
        public V put(K key, V value)
        {
            int index = key.hashCode() % table.length;
    
            if(index < 0)
            {
               index += table.length;
            }
    
            if(table[index] == null)
            {
               table[index] = new LinkedList<Entry<K, V>>();  //Create a new linked list at table[index]
            }
    
            //Search the list at table[index] to find the key.
            for(Entry<K, V> nextItem : table[index])
            {
                //If search is successfu, replace the old value.
                if(nextItem.key.equals(key))
                {
                    //Replace value for this key
                    V oldVal = nextItem.value;
                    nextItem.setValue(value);
                    return oldVal;
                }
            }
    
            //Key is not in table, add new item
            table[index].addFirst(new Entry<K, V>(key , value));
            numKeys++;
            if(numKeys > (LOAD_THRESHOLD * table.length))
            {
                rehash();
            }
            return null;
        }
    
        public V remove(K key)
        {
            int index = key.hashCode() % table.length;
            
            //If index is negative, add table.lenght
            if(index < 0)
            {
                index += table.length;
            }
    
            if(table[index] == null)
            {
                return null; //Key is not in the list
            }
    
            
        }
    
        /**
         * Method rehash for class HashtableChin
         * Here are the three main steps for the rehash method.
         *  1. Allocate a new hash table that is double the size and has an odd length.
         *  2. Rest the number of keys to 0.
         *  3. Reinsert each table entry in the new hash table.
         */
        private void rehash()
        {
            LinkedList<Entry<K, V>>[] oldTable = table;
    
            //double capacity of this table and add 1
            table = new LinkedList[2*oldTable.length+1];
    
            //reset numkeys to 0
            numKeys = 0;
    
            //Reinsert all items in oldTable into expanded tabel
            for(int i = 0; i < oldTable.length; i++ )
            {
                if(oldTable[index] != null)
                {
                   
                }
            }
        }
    }
    Thanks

  2. #2
    RichWade is offline Member
    Join Date
    Nov 2010
    Posts
    33
    Rep Power
    0

    Default

    It might help if you could be more specific about the problem and what you need help with. Seems like you are saying "here is my code, somebody make it work" - a bit too general.

  3. #3
    bap2 is offline Member
    Join Date
    Oct 2010
    Posts
    20
    Rep Power
    0

    Default

    For the remove method I can't figure out how I should search the list at table[index] to find the key, and if the search is successful remove the entry with this key and decrement numKeys.

    For the rehash method I can't figure out how I should reinsert all the items in the old table in to the new expanded table.

    All I need is some one to point me in the right direction and I should be fine.

    Thanks

Similar Threads

  1. log4j how can stop inheritage chain?
    By zzFrizz in forum New To Java
    Replies: 0
    Last Post: 03-11-2010, 04:45 PM
  2. hashtable
    By vijayabaskar in forum Java Servlet
    Replies: 0
    Last Post: 04-06-2009, 09:20 AM
  3. hashtable
    By vijayabaskar in forum Advanced Java
    Replies: 2
    Last Post: 04-06-2009, 09:05 AM
  4. Hashtable
    By angelicsign in forum New To Java
    Replies: 6
    Last Post: 02-05-2009, 05:30 PM
  5. Hashtable example
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 02-15-2008, 09:43 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •