Arrays and String - Comman Techniques

HashTables -
    Data Structures mapping keys to the values for highly efficient lookup.
   
    2 parts - An underlying array
              A hash()
    A hash() maps keys to an integer , which indicates index in the array . The object is stored at that index.
   
    Trivial Style  -
        Create an array equal to the size of all possible key such that object allocation takes on index generated by hash(key)

    Pitfalls -
        Requires unique hash values for all keys to prevent overwrite
        To prevent "collisions" arrays need to be extremely large
   
    Optimal Solutions -
        Linked List -
                 Store objects in a linked list at index generated by  (  hash(key) % array_length  ) .
                 To get object at a particular key , we must search linked list at that index for this key
        BST -
                 Guarrantees O( log n ) lookup time , since we can keep a tree balanced .
                 Additionally we may use less space , since a large array no needs to be allocated in the very beginning.
                 Creating a BST at each bucket of ours HashMap ,instead of linked lists for degenerate hash(key) % array_length values , can bring
                 down total complexity  -
                Using LinkedList -  O(1) + O(n) - to search in the linked list
                Using BST -  O(1) + O(log n)
       
example  -
            public HashMap< Integer , Student > buildMap( Student[] students )
            {
                HashMap<Integer , Student> map =  new HashMap<Integer , Student>();
                for(Student s : students) map.append(s.getId() , s );
                return map;
            }
               

ArrayList -
            A dynamically resizing array , resizing when needed and still providing O(1) access .
            The array doubles in size , when it is full  taking O(n) time which is so rare such that amortized time is still O(1)
           
        eg. -
        public ArrayList<String> merge ( String[] words , String[] more )
        {
            ArrayList<String> sentence = new ArrayList<String>();
            for(String s : words) sentence.add(s);
            for(String s : words) sentence.add(s);
            return sentence;
        }
   
   
StringBuffer -

    A trivial style of concatanating the string is as follows , what would be its running time
    assuming all strings in array are of length x and there are n strings  -
    public String joinWords(String words[])
    {
        String sentence = "";
        for(String w : words)
        {
            sentence = sentence + words ;
        }
        return sentence;
    }
   
    On each concatanation a new copy of the string is created and two strings are copied character by character.
    First iteration -  x characters copied
    Second iteration - 2x characters copied
    .....
    ........
    ..........
    Total copying instances (assighnments) = x ( 1 + 2 + 3.. n ) = x * ( n*(n+1)/2 ) = O(x * n^2)
   
While StringBuffer can avaoid this problem as it simply creates an array of all the strings , copying them back to a string only when necessary

        public String joinWords(String words[])
    {
        StringBuffer sentence = "";
        for(String w : words)
        {
            sentence.append(w);
        }
        return sentence.toString();
    }