import java.util.*;

public class LinearBinaryHash{
    private final int count = 100000;
    private Integer[] array = new Integer[count];
    private TreeSet<Integer> binaryTree = new TreeSet<Integer>();
     private Hashtable<Integer, Integer> hashTable = new Hashtable<Integer, Integer>();
    
    public LinearBinaryHash(){
        Random rand = new Random();
        for(int i = 0; i< array.length; i++){
             array[i] = rand.nextInt(count);
            binaryTree.add(array[i]);
            hashTable.put(array[i], array[i]);
        }
            
        long startTime, stopTime;
        
        startTime = System.currentTimeMillis();
         for(int i = 0; i< count; i++)
            linearSearch(new Integer(i));
        stopTime = System.currentTimeMillis();
        System.out.println("Linear search takes " + (stopTime-startTime) + "ms.");
         
        startTime = System.currentTimeMillis(); 
        for(int i = 0; i< count; i++)
            binaryTree.contains(new Integer(i));
        stopTime = System.currentTimeMillis();
        System.out.println("Binary search takes " + (stopTime-startTime) + "ms."); 
        
        startTime = System.currentTimeMillis(); 
        for(int i = 0; i< count; i++)
            hashTable.containsKey(new Integer(i));
        stopTime = System.currentTimeMillis();
        System.out.println("Hash table takes " + (stopTime-startTime) + "ms."); 
    }
    
    public boolean linearSearch(Integer obj){
        boolean found = false;
        for(int i = 0; i < array.length; i++)
            if(array[i].equals(obj))
                return true;
                 
        return false;
    }
    
    public static void main(String args[]){
        new LinearBinaryHash();
    }
    
}