Slide SRCH-01


SEARCHING
 
  n = number of elements

Linear Search

     average number of comparisons = n/2

         n = 1,000   =====>   avg = 1000 / 2 = 500

         n = 1,000,000   ======>   avg = 500,000


Binary Search
       
     average number of comparisons = log n
                                        2
                     10                         10
        n = 1,000 = 2     =======>   avg = log 2   = 10
                                              2
                         20
        n = 1,000,000 = 2     ======>   avg = 20





                                                          Slide SRCH-02


Hashing

     tries to do searching with only one comparison

     when storing

                calculation
          key  ---------------> address (location)
                hash function

     when searching

               calculation
          key ---------------> address (location)
               hash function
  

Hash Functions
     
     Division Method

               key                               425
           ------------ ==> remainder           ------  ==> 25
            table size                           100


     Mid-Square Method

                2          -------
           (key)   =   - -|- - - -|- -
                           -------

                       2      ----
                  (key)  = 75|6378|09
                              ----





                                                          Slide SRCH-03


Hash Collision

             hash
     key 1 --------->
                         same address
             hash
     key 2 --------->

             425
            -----  ===> 25
             100

             225
            -----  ===> 25
             100


Resolving Hash Collision

     Linear Probing

          e.g., use next available one


                                         |  ...  |
                                         |-------|
                                      25 |  425  |
                                         |-------|
                                         |  225  |
                                         |-------|
                                         |  ...  |



          Linear probing is an example of a general method
          for resolving hash collisions called "rehashing" or
          "open addressing".





                                                          Slide SRCH-04


Chaining

        --------        -------
       |        | ---> |     | |
       |--------|       -------
       |  ...   |
       |--------|       -------        -------
    25 |        | ---> | 425 | | ---> | 225 | |
       |--------|       -------        -------
       |  ...   |
        --------
       Bucket Directory
       (Hash Index)


   if new nodes are added to the beginning of the linked list

        --------
       |        |
       |--------|
       |  ...   |
       |--------|       -------        -------
    25 |        | ---> | 225 | | ---> | 425 | |
       |--------|       -------        -------
       |  ...   |
        --------
       


  "good" hash functions have very few hash collisions



======================================================================