How Hashset works and the importance of equals and hashcode in hashset ?

Internally Hashset maintains buckets as given in the following diagram
Internally hashset maintains an array...
and each element points to list of objects
bucket[0] or bucket1 --- contains list of objects
bucket[1] or bucket2 ---contains list of objects.

Go through below content and then you will understand better about the bucket
concept I am talking about.









Internally storing an object in to hashset involves following steps

1)Generate hashcode of the object
2)And find the bucket to which the object to be inserted with following formula
    This is only an example to show how hashset internally works....
    Formula:
        hashcode mod no of buckets
        Example if hashcode of object is 11 and no of buckets is 5
        11 modulus operator  5 = 1
 3)Suppose if the generated bucket no for the object is 5.Hashset will check in bucket 5,
      if there is any duplicate object using equals method.
4)If the equals method returns true on any existing object that means there is similar object
   already and the object won't be added to set
5)Otherwise object gets added to set.


Important Points to remember for the rest of the discussion:
-------------------------------------------------------------
1)If you don't override the hashcode every object generates unique hashcode.
2)If you don't override the equals method equals method checks if the hashcode
of the objects are equal or not and returns true or false based on hashcode. 


We will see an example with Student class

class Student{
        String sname;
        public Student(String sname){
                    this.sname = sname;
       }
       public Student(int sid){

       }
        

}

Suppose we want to store 5 student objects in to hashset.
There are 2 students with same sid 1 in the below example.As you know we never want
want to add duplicate students (students having same sid) in to set.
Only one student with sid1 should be stored in hashset.

Student st1 = new Student(1); --Assume hashcode is 6

 The bucket to in to which this object need to be stored is
  hashcode mod noofbuckets = 6/5 =1.Calculate the bucket for the rest 
  using the same formula

Student st2 = new Student(2) -- Assume hashcode is 7
7/5 = second bucket

Student st3= new Student(3)-- Assume hashcode is  8
8/5=3 bucket


Student st4= new Student(4) -- Assume hashcode is 9
9/5=4th bucket

Student st5 = new Student(1)-- Assume hashcode is11
11/5 = 1st bucket

Now remember the process that happens while adding an object in
to hashset and place in to buckets.

Bucket1
   St1 need to be stored here as per above formula    


Bucket2
st2 lands here

Bucket3
st3 lands here

Bucket4
st4 lands here

Now the interesting question comes ?

st5 need to be stored in to hashset or not.Ideally it should not get stored
because st5 has sid 1 and is same as st1's sid in bucket1.

But as per the rules to add we will try to see if hashset prevents adding duplicate
student with same sid 1.

As per the first rule generate hashcode for st5,assume hashcode generated is 11,
so its bucket is 11 mod 5 =1st bucket

Next we have to see in first bucket if there is any object which is equal to
st5 using equals method.As you know since we didn't override
the equals method equals method checks hashcode of the st5 and the
existing object s1 in the bucket one
  As st1 hashcode is 6 and st5 hashcode is 11 as they are not equal
 poor hashset allows insertion of.... st5 which is same as st1 object


Oops................ Now you might have understood the importance of equals method
So..... You have to override the equals method in student such that....when 2 students
are having same sid it returns true...If you don't override equals,default equals mehod checks
the hashcode which is unique per object even if student ids are same.

 public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final StudentTo other = (StudentTo) obj;
        if (this.sid != other.sid) {
            return false;
        }
        return true;
    }

After adding equals method in to Student Class
Now we will try to add student5(new Student(1)) in to bucket1 and see if it allows or not

First step find hashcode of student5.We assumed it is 11.
Find the bucket using hashcode mod noofbuckets 11 mod 5 =1

Second step check the st5 with st1 using equals method to check if
any equal object exists already or not...

Now the overridden equals method checks if sid in st1 and st5 is equal or
not.As both st5 and st1 are having same sid 1,equals method returns true and
hashset rejects insertion of st5 object.

Conclusion about importance of equals method:
-------------------------------------------------
If equals method is not overriden.. hashset couldn't find the duplicates
with equals because default equals method checks hashcodes and as
hashcode is unique for every object, equals method cant' find duplicate.
So we have to override the equals method to check based on student
name not based on hashcode so that equals method can find if any
duplicate student object in the bucket

2)Steps involved to find an object from HashSet:
-------------------------------------------------------------
1)Calculate hashcode
2)Calculate bucket from hashcode using formula hashcode mod noofbuckets
3)Check if there is any duplicate already in that bucket using
    equals method.



Now we will see importance of the hashcode:
---------------------------------------------

Now we will try to check if student with sid 1 contains in hashset.

Let us create a student with  sid 1 and try to find using
contains....

Student findStudent = new Student(1);
As you know if you don't override the hashcode method,hashcode generated will be unique for
every objet.Assume the hashcode generated is 13.

boolean isExisting= hset.contains(findStudent);--This will not find existing student with sid 1
in bucket1 because of the following.

Now recollect the 3 steps to find the object from hash set

1)Find the hashcode of the object you are trying to find...
   the hashcode of student is 13
2)Find the bucket using 13 mod 5 so bucket is 3
3)It will check if there is any student with sid 1exists in bucket3....
    and it won't find.....

OOPSSSSSSSSSSSSS

Eventhough there is student with sid 1  exists in bucket1,hashset find
procedure is unable to find becasue... the hashcode generated for findStudent
is generated as 13 and it lead to wrong bucket 13 mod 5 = 3.

So you have to override the hashcode such that.........
whenever 2 objects are equal it should return same hashcode.

Now override the hashcode such that it returns the same hashcode for
students which have same sid

  public int hashCode() {
        return this.sid *6;
    }

After adding above method 

repeat the steps to find the object

Find the hashcode of the findStudent now it will return hashcode as
6 using overridden hashcode method 1*6 = 6
2)Calculate the bucket with formula hashcode mod noofbuckets
   = 6 mod 5 = 1
3)Now hashset tries to find if any object is existing with sid 6
    using equals method....
    so.. findStudent.equals(st1)-- returns true because of overriden method
    so now the object will be found succesfully..


So finally 

If equals method is not overriden for equal objects hashset can't prevent duplicates

If you don't override hashcode properly for equal object 2 problems can occur

 1)object won't be found even if it is existing.
 2)duplicate objects can be added 
   
    because suppose student1 (new Student(1)) sid is added in to bucket1--
    Assume hashcode is 6.
    and if you are trying to add another duplicate student (new Student(1))
    with sid same as first student as you know while inserting,
    hashcode of the object is used to find the bucket in to which hashset need to store the object 
   and as you didn't override the hashcode for equal objects for the second object it will generate   another hashcode say 13 ,instead of 6 so hashset checks if the object with sid 1 exists or not in
  bucket2(13 mod 5) and couldn't find the duplicate student with sid in 3 and duplicate get added

If you override the hashcode for the second object the hashcode generated will be
1*6=6 so bucket will be mapped correctly to first bucket (6 mod 5=1) and as there is
student with sid 1 already in bucket1 hashset reject the insertion


3) Two non equal objects can be stored in the same bucket if the bucket number generated
     is same.In the following example you see that student1 and student2 can be stored in
    same bucket even if they are not equal.This is the reason hashset can't simply generate
     the bucket value for the object you are finding and return the object.It has to find the
     correct object using equals method.

   

     For example:

     new Student(1);   -- hashcode is 6(sid*6)
       bucket formula = 6 mod 5 =1
     so It will be stored in
     bucket1 if there are not students with sid 1.
    new Student(6);
     hashcode = 36(6*6)
      bucket = 36 mod 5 =1
   So it will be stored in bucket1 if there are no students with sid 1.

How to create our own HashSet Implementation in Java ?

1)CustomHashSet.java

   package customhashset;

   import java.util.Iterator;
   import java.util.NoSuchElementException;
 
   /**
      This class implements a hash set using separate chaining.
   */
   public class CustomHashSet
   {
     private Node[] buckets;
     private int currentSize;

     /**
        Constructs a hash table.
        @param bucketsLength the length of the buckets array
     */
     public CustomHashSet(int bucketsLength)
     {
        buckets = new Node[bucketsLength];
        currentSize = 0;
     }

     /**
        Tests for set membership.
        @param x an object
        @return true if x is an element of this set
     */
     public boolean contains(Object x)
     {
        int h = x.hashCode();
        if (h < 0) { h = -h; }
        h = h % buckets.length;

        Node current = buckets[h];
        while (current != null)
      {
           if (current.data.equals(x)) { return true; }
           current = current.next;
        }
        return false;
     }

     /**
        Adds an element to this set.
        @param x an object
        @return true if x is a new object, false if x was
        already in the set
     */
     public boolean add(Object x)
     {
        int h = x.hashCode();
        if (h < 0) { h = -h; }
        h = h % buckets.length;

        Node current = buckets[h];
        while (current != null)
        {
           if (current.data.equals(x)) { return false; }
              // Already in the set
           current = current.next;
        }
        Node newNode = new Node();
        newNode.data = x;
        newNode.next = buckets[h];
        buckets[h] = newNode;
        currentSize++;
        return true;
     }

     /**
        Removes an object from this set.
        @param x an object
        @return true if x was removed from this set, false
        if x was not an element of this set
     */
     public boolean remove(Object x)
     {
        int h = x.hashCode();
        if (h < 0) { h = -h; }
        h = h % buckets.length;

        Node current = buckets[h];
        Node previous = null;
        while (current != null)
        {
           if (current.data.equals(x))
           {
              if (previous == null) { buckets[h] = current.next; }
              else { previous.next = current.next; }
              currentSize--;
              return true;
           }
           previous = current;
           current = current.next;
        }
        return false;
     }

     /**
        Returns an iterator that traverses the elements of this set.
       @return a hash set iterator
    */
    public Iterator iterator()
    {
       return new HashSetIterator();
    }

    /**
       Gets the number of elements in this set.
       @return the number of elements
    */
    public int size()
    {
       return currentSize;
    }

    class Node
    {
       public Object data;
       public Node next;
    }

    class HashSetIterator implements Iterator
    {
       private int bucketIndex;
       private Node current;

       /**
          Constructs a hash set iterator that points to the
          first element of the hash set.
       */
       public HashSetIterator()
       {
          current = null;
          bucketIndex = -1;
       }

       public boolean hasNext()
       {
          if (current != null && current.next != null) { return true; }
          for (int b = bucketIndex + 1; b < buckets.length; b++)
          {
             if (buckets[b] != null) { return true; }
          }
          return false;
       }

       public Object next()
       {
          if (current != null && current.next != null)
          {
             current = current.next; // Move to next element in bucket
          }
          else // Move to next bucket
          {
             do
             {
                bucketIndex++;
                if (bucketIndex == buckets.length)
                {
                   throw new NoSuchElementException();
                }
                current = buckets[bucketIndex];
             }
             while (current == null);
          }
          return current.data;
       }

       public void remove()
       {
          throw new UnsupportedOperationException();
       }
    }
 }


2)HashSetDemo.java

package customhashset;
import java.util.Iterator;

  /**
     This program demonstrates the hash set class.
  */
  public class HashSetDemo
  {
     public static void main(String[] args)
      {
       CustomHashSet names = new CustomHashSet(101);

       names.add("Harry");
       names.add("Sue");
       names.add("Nina");
       names.add("Susannah");
       names.add("Larry");
       names.add("Eve");
       names.add("Sarah");
       names.add("Adam");
       names.add("Tony");
       names.add("Katherine");
       names.add("Juliet");
       names.add("Romeo");
       names.remove("Romeo");
       names.remove("George");

       Iterator iter = names.iterator();
       while (iter.hasNext())
       {
          System.out.println(iter.next());
       }
    }
 }

How to create our own LinkedList implemenatation in java ?

1)LinkedList.java

package llist;
import java.util.NoSuchElementException;

/**
   A linked list is a sequence of nodes with efficient
   element insertion and removal. This class
   contains a subset of the methods of the standard
   java.util.LinkedList class.
*/
public class LinkedList
{ 
   private Node first;
  
   /**
      Constructs an empty linked list.
   */
   public LinkedList()
   { 
      first = null;
   }
  
   /**
      Returns the first element in the linked list.
      @return the first element in the linked list
   */
   public Object getFirst()
   { 
      if (first == null) { throw new NoSuchElementException(); }
      return first.data;
   }

   /**
      Removes the first element in the linked list.
      @return the removed element
   */
   public Object removeFirst()
   { 
      if (first == null) { throw new NoSuchElementException(); }
      Object element = first.data;
      first = first.next;
      return element;
   }

   /**
      Adds an element to the front of the linked list.
      @param element the element to add
   */
   public void addFirst(Object element)
   { 
      Node newNode = new Node();
      newNode.data = element;
      newNode.next = first;
      first = newNode;
   }
  
   /**
      Returns an iterator for iterating through this list.
      @return an iterator for iterating through this list
   */
   public ListIterator listIterator()
   { 
      return new LinkedListIterator();
   }
  
   class Node
   { 
      public Object data;
      public Node next;
   }

   class LinkedListIterator implements ListIterator
   { 
      private Node position;
      private Node previous;
      private boolean isAfterNext;

      /**
         Constructs an iterator that points to the front
         of the linked list.
      */
      public LinkedListIterator()
      { 
         position = null;
         previous = null;
         isAfterNext = false;
      }
     
      /**
         Moves the iterator past the next element.
         @return the traversed element
      */
      public Object next()
      { 
         if (!hasNext()) { throw new NoSuchElementException(); }
         previous = position; // Remember for remove
         isAfterNext = true;

         if (position == null)
         {
            position = first;
         }
         else
         {
            position = position.next;
         }

         return position.data;
      }
     
      /**
         Tests if there is an element after the iterator position.
         @return true if there is an element after the iterator position
      */
      public boolean hasNext()
      { 
         if (position == null)
         {
            return first != null;
         }
         else
         {
            return position.next != null;
         }
      }
     
      /**
         Adds an element before the iterator position
         and moves the iterator past the inserted element.
         @param element the element to add
      */
      public void add(Object element)
      { 
         if (position == null)
         {
            addFirst(element);
            position = first;
         }
         else
         { 
            Node newNode = new Node();
            newNode.data = element;
            newNode.next = position.next;
            position.next = newNode;
            position = newNode;
         }

         isAfterNext = false;
      }
     
      /**
         Removes the last traversed element. This method may
         only be called after a call to the next() method.
      */
      public void remove()
      { 
         if (!isAfterNext) { throw new IllegalStateException(); }

         if (position == first)
         {
            removeFirst();
         }
         else
         { 
            previous.next = position.next;
         }
         position = previous;
         isAfterNext = false;
      }

      /**
         Sets the last traversed element to a different value.
         @param element the element to set
      */
      public void set(Object element)
      {
         if (!isAfterNext) { throw new IllegalStateException(); }
         position.data = element;
      }
   }
}


2)ListIterator.java

/**
   A list iterator allows access of a position in a linked list.   
   This interface contains a subset of the methods of the
   standard java.util.ListIterator interface. The methods for
   backward traversal are not included.
*/
package llist;
public interface ListIterator
{ 
   /**
      Moves the iterator past the next element.
      @return the traversed element
   */
   Object next();
     
   /**
      Tests if there is an element after the iterator position.
      @return true if there is an element after the iterator position
   */
   boolean hasNext();
     
   /**
      Adds an element before the iterator position
      and moves the iterator past the inserted element.
      @param element the element to add
   */
   void add(Object element);
     
   /**
      Removes the last traversed element. This method may
      only be called after a call to the next() method.
   */
   void remove();

   /**
      Sets the last traversed element to a different value.
      @param element the element to set
   */
   void set(Object element);
}


3)ListDemo.java

/**
   A program that demonstrates the LinkedList class
*/
package llist;
public class ListDemo
{ 
   public static void main(String[] args)
   { 
      LinkedList staff = new LinkedList();
      staff.addFirst("Tom");
      staff.addFirst("Romeo");
      staff.addFirst("Harry");
      staff.addFirst("Diana");
     
      // | in the comments indicates the iterator position

      ListIterator iterator = staff.listIterator(); // |DHRT
      iterator.next(); // D|HRT
      iterator.next(); // DH|RT

      // Add more elements after second element
     
      iterator.add("Juliet"); // DHJ|RT
      iterator.add("Nina"); // DHJN|RT

      iterator.next(); // DHJNR|T

      // Remove last traversed element

      iterator.remove(); // DHJN|T
    
      // Print all elements

      iterator = staff.listIterator();
      while (iterator.hasNext())
      {
         System.out.print(iterator.next() + " ");
      }
      System.out.println();
   }
}

Hello world Reflection Example to get the methods and constructors declared in class

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package reflection;

import java.lang.reflect.Constructor;
import java.lang.reflect.Method;

/**
 *
 * @author Rishitha
 */
public class ReflectionExample {

    public void requestConstuctors() throws ClassNotFoundException {
        Class cl;
        Constructor con[];
        Method meth[];
        try {
           //You can pass another class name to find out the methods
           //and constructors declared in that class.Provide packagename.classname
           cl = Class.forName("reflection.Test");
            con = cl.getDeclaredConstructors();
            for (int x = 0; x < con.length; x++) {
                System.out.println("Constructor " + x + " = " + con[x]);
            }

            meth = cl.getDeclaredMethods();
            for (int x = 0; x < meth.length; x++) {
                System.out.println("Method " + x + " = " + meth[x]);
            }

        } catch (Exception e) {
           
        e.printStackTrace();
    }    
     }      
       
        

    public static void main(String args[]) throws ClassNotFoundException {
        ReflectionExample req = new ReflectionExample();
        System.out.println("hello ");
        req.requestConstuctors();
    }
}

 class Test{
   
    public Test(){
       
    }
    public Test(String s ){
       
    }
    public String sayHello(){
        return "hello";
    }
    public int getInt(){
        return 1;
    }
   
}

ShellSort Programme in Java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package genericspro;

/**
 *
 * @author Rishitha
 */
public class ShellSort {

    public static void main(String args[]) {

        int arr[] = {15, 14, 13, 12, 11, 10, 9,8,7,6,5,4,3,2,1};
        int num = 15;
        int tmp;
        System.out.println("Before Sorting ");
        for (int k = 0; k < num; k++) {
            System.out.println(" " + arr[k] + "\n");
        }

        for (int i = num / 2; i > 0; i = i / 2) {
            for (int j = i; j < num; j++) {
                for (int k = j - i; k >= 0; k = k - i) {
                    //System.out.println("i:"+i+" j: "+j+" k: "+k);
                    if (arr[k + i] >= arr[k]) {
                       //System.out.println(" "+arr[k+i] +">= "+arr[k]);
                        break;
                    } else {
                        //System.out.println(" "+arr[k+i] +"not >= "+arr[k]);
                        tmp = arr[k];
                        arr[k] = arr[k + i];
                        arr[k + i] = tmp;
                    }
                }
            }
        }
        System.out.println("\t**** After Shell Sorting ****\n");
        for (int k = 0; k < num; k++) {
            System.out.println(" " + arr[k] + "\n");
        }

    }

}

How to configure Datasource in Weblogic Server and example code to lookup datasource configured through JNDI ?

Following steps are in weblogic 12c.Screens may vary in another versions but everything
should be same as below.

1)Go to weblogic console

    http://localhost:7001/console

2)Click on DataSources link

3)Click on New->GenericDatasource

4)Provide testDs in name text field and jndiName text field

5)Choose Database Type as oracle(If you want another database
    choose that database name)

6)Choose oracle's driver thin

7)Click next next

8)Provide Database Name,hostname,port,username and password



9)Click TestConfiguration,you should get connection test succeded

10)Click next and don't forget to check the checkbox in the Servers section.
     This step is very important don't forget



11)Click Finish


Now we see the code to get the datasource from weblogic jndi tree using JNDI code

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package hibex;

import java.sql.SQLException;
import java.util.Hashtable;
import javax.naming.Context;
import javax.naming.InitialContext;
import javax.naming.NamingException;
import javax.sql.DataSource;

/**
 *
 * @author Rishitha
 */
public class InitialContextEx {

    private static InitialContext ctx = null;

    public static void main(String args[]) throws NamingException, SQLException {

        Hashtable env = new Hashtable();
        env.put(Context.INITIAL_CONTEXT_FACTORY,
                "weblogic.jndi.WLInitialContextFactory");
        //If your weblogic is not running on 7001 provide that port
        //no instead of 7001
        env.put(Context.PROVIDER_URL,
                "t3://localhost:7001");
        ctx = new InitialContext(env);
        //The string argument is jndi name for the datasource
        //If you have provided another name for the datasource
        //change testDs to the name you have given while configuring
        //the datasource
        DataSource ds = (DataSource) ctx.lookup("testHr");
        System.out.println("Connection From JNDI DS: " + ds.getConnection());
    }

}
Note:

1)provider_url:This specifies the the URL of the server whose jndi tree we want to
    access.
   Simply,it is the place where your datasource is configured.In our example
   since we configured datasource in weblogic we have to provide the
   port where weblogic is runnin.t3://localhost:7001.

2)INIITAL_CONTEXT_FACTORY:While connecting to weblogic it is
weblogic.jndi.WLInitialContextFactory.For other servers this class name
will change

3)Add weblogic.jar to classpath.weblogic.jar contains class WLInitialContextFactory.



And finally call getConnection on DataSource to get the jdbcconnection and from here
onwards everything is same....