0
\$\begingroup\$

I implemented my own LinkedHashMap in java.

    public class LinkedHashMap<K,V> {
        private Entry<K,V>[] buckets;
        private int capacity=4;
        private Entry<K,V> head;
        private Entry<K,V>tail;
        static class Entry<K,V>
        {
            K key;
            V value;
            Entry<K,V>next;
            Entry<K,V>before;
            Entry<K,V>after;
            public Entry(K key ,V value,Entry<K,V> next)
            {
                this.key=key;
                this.value=value;
                this.next=next;
            }   
        }
        public LinkedHashMap()
        {
            buckets=new Entry[capacity];    
        }
        public void put(K key,V value)
        {
            if(key==null)//not allow null key
            {
                return;
            }
            boolean replace=false;
            int hash=hash(key);
            Entry<K,V> newEntry = new Entry<K,V>(key, value, null);
            //insert in bucket
        //  maintainOrderAfterInsert(newEntry);  
            Entry<K,V>curr=buckets[hash];

            if(curr==null)
            {
              buckets[hash]=newEntry;
            }
            else
            {
                Entry<K,V> prev=null;
            while(curr!=null)
            {
                if(curr.key.equals(key))
                {
                    replace=true;
                    curr.value=value;
                    break;
                }
                prev=curr;
                curr=curr.next;
            }
             if(prev!=null)
             prev.next=newEntry;
            }
            //newEntry.next=curr;
            //buckets[hash]=newEntry;
            if(replace==false)
            insertInList(newEntry);
            //buckets[hash]=newEntry;
        }
        private void insertInList(Entry<K,V> newEntry)
        {
            if(head==null)
            {
                head=newEntry;
                tail=newEntry;
            }
            else
            {
              tail.after=newEntry;
              newEntry.before=tail;
              tail=newEntry;
            }
        }
        public V get(K key)
        {   
            int hash=hash(key);
            Entry<K,V> curr=buckets[hash];
            while(curr!=null)
            {
                if(curr.key.equals(key))
                {
                    return curr.value;
                }
                curr=curr.next;
            }
            return null;
        }

        public void print()
        {
            Entry<K,V>curr=head;
            while(curr!=null)
            {
              System.out.println("key is "+ curr.key+"val is "+ curr.value+"->");   
              curr=curr.after;
            }
        }   
        private int hash(K key){
            return Math.abs(key.hashCode()) % capacity;
        }

        public void remove(K key)
        {
            int hash=hash(key);
            Entry<K,V>curr=buckets[hash];
            if(curr==null)//no exist
            {
                return;
            }
            Entry<K,V>p=null;
            Entry<K,V>n;
            while(curr!=null)
            {
                n=curr.next;
                if(curr.key.equals(key))
                {
                   if(p==null)//first
                   {
                       buckets[hash]=buckets[hash].next;
                   }
                   else
                   {
                       p.next=n;
                   }
                   //adjust Linked List
                   adjustList(curr);
                   break;
                }
                p=curr;
                curr=n;
            }

        }
        private void adjustList(Entry<K,V> curr)
        {
            if(curr==head)
            {
                head=head.after;
                if(head==null)
                {
                    tail=null;
                }
            }
            else if (curr==tail)
            {
                tail=tail.before;
                tail.after=null;
            }
            else
            {
                curr.before.after=curr.after;
                curr.after.before=curr.before;
            }
        }
        public void deleteAll()
        {
            head=null;
            tail=null;
            for(int i=0;i<capacity;i++)
            {
                buckets[i]=null;
            }   
        }
    }

Null key is not allowed. If the same key appears,value is updated. In every bucket,new element added at the end. I want to review how optimal are the functions ,especially deleteAll().

In a language like C++, I have to explicitly free memory .

In JAVA,just setting references to null will work?

Any suggestions on any other function ??

\$\endgroup\$
1
  • \$\begingroup\$ shouldn't deleteAll be named more aptly clear? deleteAll implies you give it a collection of elements, all of which you want to delete from this map. \$\endgroup\$ Commented Jun 7, 2018 at 8:36

1 Answer 1

0
\$\begingroup\$
  1. yes, setting a variable to null will make it eligible for garbage collection (which is invoked implicitly by the run time platform) this is also true when a variable becomes out of scope (for example all local variables become eligible for garbage collection when the method exits).

  2. in put() you do not allow null key, but you do not alert the client in any way. You should consider raising an exception and then the client may choose to regard or disregard it. you can make a custom checked exception (to force clients to catch it) or use the predefined unchecked IllegalArgumentException.

  3. regrding print(): this is considered bad practice becasue it predetermines the destination of the print operation. clients may want to print to stderr or to a file or to an HTTP response etc. it is better to implement toString() and let the client decide where it goes.

  4. regrding remove(): you should consider returning the deleted value. This serves two purposes: it indicates if key was found and it supports stack's pop() (or queue's pull()) that does "get and remove".

  5. there are several additional functionalities you can add like test if key exists, put only if key is absent, iterate on keys, on values. why don't you take a look at Map interface. and perhaps consider implementing it?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.