This website is not affiliated with, sponsored by, or approved by SAP AG.

0016 - Internal Tables

Moderators: Snowy, thx4allthefish, Rich, ilya

0016 - Internal Tables

Postby Rich » Thu Mar 26, 2009 12:00 pm

Internal Table Types.

ABAP contains the concept of internal tables. These can be thought of as an array or a multi-dimensional structure. Internal tables can be defined as various types of tables:
  • Standard
  • Sorted
  • Hashed
  • Index
  • Any
These all have their various uses from just storing data extracted from a database to being used as lookup tables. In general, tables are defined like so:

Code: Select all
Types: Upload_Table        Type Standard table of Upload_row
                                initial size 0,
       So_Line_Item_Table  Type Hashed table of So_Line_Item_row
                                initial size 0
                                with unique key Vbeln Posnr,
       Error_Table         Type Sorted table of Results_row
                                initial size 0
                                with header line
                                with non-unique key Error_Code.


Note that you can include a header line (ie an in built work area) into the table definition, but my own preference is to use discrete work areas which allow easier use when reading and handling multiple rows from the same table, or updating a table of the same structure from a source table.

Standard Tables

Standard tables are effectively just a list of rows either extracted from a database or compiled during a program run. The order of the rows within a standard table are basically in entry order. Ie the first row inserted into the table occupies the first row, the second the second and so forth. This ordering can be changed using the SORT command to sort the table into any arbitrary order based upon the values of any field in the table structure. A READ TABLE command on a standard table results in a sequential search of the table from start to end until the required record is found. If the table has been sorted using the SORT command then faster binary searches can be used to read the table if required.

Sorted Tables

Sorted tables specify either a unique or a non-unique key. This key is used to impose an ordered sequence on the records that are inserted into the table and can consist of multiple fields from the table structure. Obviously if the key is unique then there can "be only one". In the case of a non-unique key when the table is read using the READ TABLE command, the first occurance of the key is returned. Sorted tables enable the use of a binary search routine enabling faster access to the various rows of the table.

How Does A Binary Search Work

Binary Searches (or more descriptively Binary Chops) work by repeatedly dividing an ordered (sorted) list in two until either the required record is found or the top and bottom of the list meet and the required record is not found.

This can be shown graphically by the following diagram. In this case, the order list consists of the numbers 1 to 36. The number we are looking for is 34. The red blocks show the current range of numbers that are being considered. The grey blocks show the numbers that have already been discarded. The Yellow block shows the mid-point of the search area and finally the green block what we are looking for.

Image

Bear in mind that although we are using numbers here, strings can also be used in the same way. What actually happens is this:

The program calculates the length of the list and from that can calculate the mid point of the list. The value of the mid point record is then compared to the value that is being looked for. If the value is less than the value being looked for then the entire lower half of the list can be discarded (as it’s an ordered list….). Likewise if the value is more then the top half of the list can be discarded. This ‘discarding’ can be achieved by moving the calculated mid-point to either the top or bottom pointers into the list.

The mid-point is then recalculated again and the whole process is run through again. Eventually either the record being looked for will be found or the top and bottom pointers will meet in which case the value being searched for does not exist.

Whilst SAP has kindly provided the tools to perform a binary search, here it is in ABAP along with a comparison of the other binary searches coded by SAP:

Code: Select all
************************************************************************
*
*       Program:       Z_Binary_Chop
*
*       Purpose:       A program to demonstrate how a binary chop works
*                      showing a comparison between a sequential search,
*                      a programmed binary chop and SAP's internal
*                      binary chop
*
*       Creation Date: 15/04/2004
*
*       Requested By:
*
*       Reference Doc:
*
*       Author:        R Harper
*
*       Modification History:
*
*   Date    Reason                             Transport     Who
*
************************************************************************
Report Z_Binary_Chop
       Message-id 38
       Line-Size  80
       Line-Count 0
       No Standard Page Heading.
*
Types: Max_Rec      type i,
       Char_Key(10) type c,
*
       Begin of Table_Row,
             Key_Value type Char_Key,
       End of Table_Row,
*
       Value_Table  type Standard table of Table_Row
                         initial size 0,
       Sorted_Table type Sorted table of Table_Row
                         initial size 0
                         with unique key Key_Value.
*
Parameters: p_NumRec type Max_Rec    obligatory,
            p_Key    type Char_Key   obligatory.
*
Start-Of-Selection.
*
   Data: t_Standard type Value_Table,
         t_Sorted   type Sorted_Table.
*
   Perform Fill_Tables using p_NumRec Changing t_Standard t_Sorted.
   Perform Binary_Chop using p_Key t_Standard.
   Skip 1.
   Perform Seq_Search  using p_Key t_Standard.
   Skip 1.
   Perform Bin_Search  using p_Key t_Standard.
   Skip 1.
   Perform Sort_Search using p_Key t_Sorted.
*Eject
***********************************************************************
*
*       Procedure           :Fill_Tables
*
*       Purpose             :Fills the standard and sorted tables with
*                            a string starting at 'A' being incremented
*                            by 'one' each time to the total number of
*                            records specified
*
*       Entry               :Total number of records to create
*       Entry               :Standard type table
*                           :Sorted type table
*
*       Exit                :
*
*       Called By           :Perform Fill_Tables using Number
*                                             changing Standard_Table
*                                                      Sorted_table
*
*       Calls               :
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Fill_Tables using pu_Max_Recs   type Max_Rec
              changing t_Stdrd_Table type Value_Table
                       t_Sortd_Table type Sorted_Table.
*
     Data: Begin of w_Char,
                 Asc type x,
           End of w_Char,
           w_Key     type Table_Row,
           w_Ins_Key type Table_Row,
           w_Klen    type i,
           w_Kpos    type i.
*
     Move 'A' to w_Key.
     Do pu_Max_Recs times.
        Move w_Key to w_Ins_Key.
        Shift w_Ins_Key right deleting trailing ' '.
        Append w_Ins_Key to t_Stdrd_Table.
        Insert w_Ins_Key into table t_Sortd_Table.
*
*       Increment the key....
*
        Compute w_Klen = Strlen( w_Key ).
        Compute w_Kpos = w_Klen - 1.
        Do w_Klen times.
           Move w_Key+w_Kpos(1) to w_Char.
           Add 1 to w_Char-Asc.
           If w_Char <= 'Z'.
              Move w_Char to w_Key+w_Kpos(1).
              Exit.
           Else.
              Move 'A' to w_Key+w_Kpos(1).
              If w_Kpos = 0.
                 Concatenate w_Key 'A' into w_Key.
                 Exit.
              EndIf.
           EndIf.
           Subtract 1 from w_Kpos.
         EndDo.
     EndDo.
EndForm.
*Eject
***********************************************************************
*
*       Procedure           :Binary_Chop
*
*       Purpose             :Performs a programmed binary chop on a
*                            sorted standard table, displaying the
*                            number of iterations, time and whether the
*                            key was found or not
*
*       Entry               :Key value to search for
*       Entry               :Table of values to search
*
*       Exit                :
*
*       Called By           :Perform Binary_Chop using Search_Key Values
*
*       Calls               :
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Binary_Chop using pu_Key        type Char_Key
                       t_Stdrd_Table type Value_Table.
*
     Data: w_Bottom        type syTabix,          " Base record
           w_MidPoint      type syTabix,          " Mid point record
           w_Top           type syTabix,          " Top record
           w_Its           type i,                " # of iterations
           w_tvalue        type Table_Row,
           w_padded        type Char_Key,
           w_Runtime_start type i,
           w_RunTime       type i,
           w_nr_mid        type i.
*
     Move pu_Key to w_Padded.
     Shift w_Padded right deleting trailing ' '.
     Translate w_Padded to upper case.
*
*    Calculate the starting point for the search
*
     Move 1 to w_Bottom.
     Describe table t_Stdrd_Table lines w_Top.
     Compute w_MidPoint = w_Bottom + ( ( w_Top - w_Bottom ) / 2 ).
*
     Clear w_Its.
     Get Run Time Field w_RunTime_start.
     Read table t_Stdrd_Table into w_Tvalue index w_MidPoint.
     While ( w_Tvalue <> w_Padded ) and ( w_Top <> w_Bottom ).
           Write :/ w_Bottom, w_Midpoint, w_Top, w_TValue, w_Padded.
*
*          Calculate the next midpoint
*
           If w_Tvalue > w_Padded.
              Move w_MidPoint to w_Top.
           Else.
              Move w_MidPoint to w_Bottom.
           EndIf.
           Compute w_MidPoint = w_Bottom + ( ( w_Top - w_Bottom ) / 2 ).
           Read table t_Stdrd_Table into w_Tvalue index w_MidPoint.
*
           Add 1 to w_Its.
*
*           Sometimes the search will flip between the last two
*           locations.  Check that we haven't been here before.
*
           If W_Midpoint = W_Bottom Or
              W_Midpoint = W_Top.
              Add 1 To w_Nr_Mid.
              If w_Nr_Mid > 1.
                 Exit.
              Endif.
           Endif.

     EndWhile.
*
     Get Run Time Field w_RunTime.
     Compute w_RunTime = w_RunTime - w_Runtime_Start.
     Write :/ 'Binary Chop searching for ', pu_Key.
     If w_Tvalue = w_Padded.
        Write:/ '    Found'.
     Else.
        Write:/ 'Not Found'.
     EndIf.
     Write: 'After ', w_Its, 'Iterations and ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
*       Procedure           :Seq_Search
*
*       Purpose             :Performs a sequential search on a
*                            sorted standard table, displaying the
*                            time and whether the
*                            key was found or not
*
*       Entry               :Key value to search for
*       Entry               :Table of values to search
*
*       Exit                :
*
*       Called By           :Perform Seq_Search using Search_Key Values
*
*       Calls               :
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Seq_Search using pu_Key        type Char_Key
                      t_Stdrd_Table type Value_Table.
*
     Data: w_tvalue        type Table_Row,
           w_padded        type Char_Key,
           w_RunTime_Start type i,
           w_RunTime       type i.
*
     Move pu_Key to w_Padded.
     Shift w_Padded right deleting trailing ' '.
     Translate w_Padded to upper case.
     Get Run Time Field w_RunTime_Start.
     Read table t_Stdrd_Table
          into w_Tvalue
          with key Key_Value = w_Padded.
     Get Run Time Field w_RunTime.
     Compute w_RunTime = w_RunTime - w_RunTime_Start.
     Write :/ 'Sequential search for ', pu_Key.
     If w_Tvalue = w_Padded.
        Write:/ '    Found'.
     Else.
        Write:/ 'Not Found'.
     EndIf.
     Write: 'After ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
*       Procedure           :Bin_Search
*
*       Purpose             :Performs a binary search on a
*                            sorted standard table, displaying time and
*                            whether the key was found or not
*
*       Entry               :Key value to search for
*       Entry               :Table of values to search
*
*       Exit                :
*
*       Called By           :Perform Seq_Search using Search_Key Values
*
*       Calls               :
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Bin_Search using pu_Key        type Char_Key
                      t_Stdrd_Table type Value_Table.
*
     Data: w_tvalue        type Table_Row,
           w_padded        type Char_Key,
           w_RunTime_Start type i,
           w_RunTime       type i.
*
     Move pu_Key to w_Padded.
     Shift w_Padded right deleting trailing ' '.
     Translate w_Padded to upper case.
     Get Run Time Field w_RunTime_Start.
     Read table t_Stdrd_Table
          into w_Tvalue
          with key Key_Value = w_Padded
          Binary Search.
     Get Run Time Field w_RunTime.
     Compute w_RunTime = w_RunTime - w_RunTime_Start.
     Write :/ 'SAP Binary search for ', pu_Key.
     If w_Tvalue = w_Padded.
        Write:/ '    Found'.
     Else.
        Write:/ 'Not Found'.
     EndIf.
     Write: 'After ', w_RunTime, 'Microsecs'.
EndForm.
*Eject
***********************************************************************
*
*       Procedure           :Bin_Search
*
*       Purpose             :Performs a binary search on a
*                            Sorted table, displaying time and whether
*                            key was found or not
*
*       Entry               :Key value to search for
*       Entry               :Table of values to search
*
*       Exit                :
*
*       Called By           :Perform Sort_Search using Search_Key Stable
*
*       Calls               :
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Sort_Search using pu_Key        type Char_Key
                       t_Sortd_Table type Sorted_Table.
*
     Data: w_tvalue        type Table_Row,
           w_padded        type Char_Key,
           w_Runtime_Start type i,
           w_RunTime       type i.
*
     Move pu_Key to w_Padded.
     Shift w_Padded right deleting trailing ' '.
     Translate w_Padded to upper case.
     Get Run Time Field w_RunTime_Start.
     Read table t_Sortd_Table
          into w_Tvalue
          with table key Key_Value = w_Padded.
     Get Run Time Field w_RunTime.
     Compute w_RunTime = w_RunTime - w_RunTime_Start.
     Write :/ 'SAP Sorted search for ', pu_Key.
     If w_Tvalue = w_Padded.
        Write:/ '    Found'.
     Else.
        Write:/ 'Not Found'.
     EndIf.
     Write: 'After ', w_RunTime, 'Microsecs'.
EndForm.


To run this program, after you've done the usual copy and paste excercise, enter the number of records that you want in your internal table (300000 will do....), and then enter the key that you wish to find. Keys are generated starting at 'A' then 'B' ..... 'AA', 'AB' etc for a maximum of 10 characters (Rosie.... :-;).

Now, when I first ran this and compared the various times, I thought I had made a mistake somewhere as the binary chop that I had coded was just slightly faster (even with the WRITE statement in the middle of it) than SAP's own Binary search. So I spent a few fruitless hours checking it out. No mistake.... or so I thought. Thanks to Rouge for pointing out that each subsequent call to the GET RUNTIME statement takes the run time from the first call, rather than as I interpreted it as every other call reset the counter to zero, and corrrecting a bug whereby the code looped in certain circumstances with a non existant key..

Below is the output from the sorts:

Code: Select all
         1     150,001     300,000        HMWG         RH         
         1      75,001     150,001        DFXQ         RH         
         1      37,501      75,001        BCLI         RH         
         1      18,751      37,501        AASE         RH         
         1       9,376      18,751         MVP         RH         
         1       4,689       9,376         FXI         RH         
         1       2,345       4,689         CLE         RH         
         1       1,173       2,345         ASC         RH         
         1         587       1,173          VO         RH         
         1         294         587          KH         RH         
       294         441         587          PY         RH         
       441         514         587          ST         RH         
       441         478         514          RJ         RH         
       441         460         478          QR         RH         
       460         469         478          RA         RH         
       469         474         478          RF         RH         
Binary Chop searching for  RH                                     
    Found After          16  Iterations and         660  Microsecs
                                                                 
Sequential search for  RH                                         
    Found After         165  Microsecs                           
                                                                 
SAP Binary search for  RH                                         
    Found After           8  Microsecs                           
                                                                 
SAP Sorted Binary search for  RH                                 
    Found After       1,059  Microsecs                           


Hashed Tables

Hashed tables are similar to sorted tables in that an order is imposed on the data being inserted into the table, however this order is the result not of the lexical or alphabetical ordering of the keys, but is essentially a number generated by a algorithm that calculates the row number where the record is to be inserted. Obviously great care has to be used when constructing the algorithm as you could get cases where different keys produce the same record number. Where collisions do occur there are various ways round them from recalculating the hash value using a different algorithm to using the initial value as a starting point in the table and then using a sequential search from that point on.

Due to the fact that generally the number of steps that the hashing algorithm has to take to generate the hash number is the same for any key, the access time for a hashed table is the same for any record in the table, generally only changing if a collision is involved.

The program below handles a demonstration hash table, calculating the relevant hash codes and so forth. The hashing algorithm in the program will return a hash number between 1 and 65336 (ie 0-65535). The algorithm is not particularly elegant and neither is the collision handling procedure. They are primarily there for demonstration purposes.

The program allows you to insert and search for records, whilst displaying a graphic showing the density of the records in the table. This is quite important as a hash table works most efficiently when the table is sparsely populated. The denser the number of occupied records in the table means that the chance of hitting another record becomes quite high.

Notice how fast the table is when there are perhaps 10,000 records in it when compared to how slow it gets when there are 50,000 plus records.

Code: Select all
************************************************************************
*
*       Program:       Z_Hash_It
*
*       Purpose:       A short program to show how a hashing algorithm
*                      works
*
*       Creation Date: 15/04/2004
*
*       Requested By:
*
*       Reference Doc:
*
*       Author:        R Harper
*
*       Modification History:
*
*   Date    Reason                             Transport     Who
*
************************************************************************
Report Z_Hash_It
       Message-id 38
       Line-Size  80
       Line-Count 0
       No Standard Page Heading.
*
Type-Pools: col.
*
Types: Hash_Key(10)      type c,
       Hash_Code         type i,
       Collison_Count    type i,
*
       Begin of Hash_Record,
             Key   type Hash_Key,
             Count type Collison_Count,
       End of Hash_Record,
*
       Hash_Table type standard table of Hash_Record
                  initial size 0.
*
Data: t_Hasht   type Hash_Table,
      g_Key     type Hash_Key,
      g_Add     type i,
      g_Msg     type NaTxt,
      g_Runtime type i.
*
At Line-Selection.
*
   Data: w_Num(10) type c.
*
   Clear g_Key.
   Clear g_Add.
   Clear g_Msg.
*
*  Search or add a key ??
*
   Read Line 1 field value g_Key into g_Key.
   If g_Key <> ''.
      Perform Search_Insert using g_Key
                                  t_Hasht
                         changing g_Runtime
                                  g_msg.
   EndIf.
*
*  More records ?
*
   Read Line 3 field value g_Add into w_Num.
   If w_Num <> ''.
*
*     Remove any commas from the number first
*
      Translate w_Num using ', '.
      Condense w_Num no-gaps.
      Move w_Num to g_Add.
      If g_Add > 0.
         Perform Populate_Table using t_Hasht
                                      g_Add
                             changing g_Msg
                                      g_Runtime.
      EndIf.
   EndIf.
   Clear g_Key.
   Clear g_Add.
   Perform Display_Report using t_Hasht g_Msg g_Runtime.
*
Start-Of-Selection.
*
      Clear g_Msg.
      Perform Populate_Table using t_Hasht 10000
                          changing g_Msg
                                   g_Runtime.
      Perform Display_Report using t_Hasht g_Msg g_Runtime.
*Eject
***********************************************************************
*
*       Procedure:     Calculate_Hash
*
*       Purpose:       Using the table of hash codes created and the
*                      current key,  this routine calculates the hash
*                      code for the given key by calculating the initial
*                      record and then checking for collisions.  A
*                      collision is where a key hashes to a specific
*                      row in the table that is already occupied by a
*                      different key.
*
*       Entry:         Key string to generate hash for.
*                      Table of existing hash records
*
*       Exit:          Hash code the specified key maps to or
*                      zero if no available record can be found
*
*                      Run time of the hash search.
*
*       Called By:     Perform Calculate_Hash using w_Hash_Key t_Hasht
*                                          Changing w_Hash_Code.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Calculate_Hash Using pu_Key       type Hash_Key
                          t_Hash_Table type Hash_Table
                 Changing pc_Hash_Code type Hash_Code
                          pc_Runtime   type i.
*
     Data: w_Hash_Record type Hash_Record,
           w_Key         type Hash_Key,
           w_Hash        type Hash_Code,
           w_Start       type i,
           w_End         type i.
*
*    Calculate the initial key and check for a collision.  If no
*    collision is found then leave the hash as it is,  otherwise
*    handle the collision.
*
     Get Run Time Field w_Start.
     Move pu_Key to w_Key.
     Translate w_Key to upper case.
     Perform Calculate_Initial_Hash using w_Key changing w_Hash.
*
*    Check for a collision
*
     Read Table t_Hash_Table index w_Hash into w_Hash_Record.
     If sy-subrc = 0.
        If w_Hash_Record-Key <> w_Key.
           Perform Hash_Collision using w_Key w_Hash t_hash_table
                               changing w_Hash.
        EndIf.
     EndIf.
*
     Get Run Time field w_End.
     Compute pc_Runtime = w_End - w_Start.
     Move w_Hash to pc_Hash_Code.
EndForm.
*Eject
***********************************************************************
*
*       Procedure:     Calculate_Initial_Hash
*
*       Purpose:       This procedure uses the Variable String
*                      Exclusive-or method to calculate the hash code
*                      for a variable length string.  The table t_Masks
*                      is used to inject an element of randomness to the
*                      hash code as hash tables work better when they
*                      are sparsly populated.
*
*                      The procedure calculates two hash codes for a
*                      given string which when multiplied provide an
*                      address space of 0 to 65535.  This is adjusted by
*                      one to cope with the fact that index 0 on a table
*                      is an invalid index.
*
*                      This hashing algorithm can successfully
*                      distingush similar words, anagrams and
*                      palindromes.
*
*       Entry:         Key string to generate hash for.
*
*       Exit:          Hash code the specified key maps to.  This will
*                      be the initial start point for a sequential
*                      search if a collision occurs.
*
*       Called By:     Perform Calculate_Initial_Hash using w_Hash_Key
*                                                  Changing w_Hash_Code.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Calculate_Initial_Hash using pu_string changing pc_hash.
*
*    A simple macro to append records to a table. The parameter
*    &1 must be a string.
*
     Define Load_Table.
            Move &1 to w_Mask.
            Append w_Mask to t_Masks.
     End-Of-Definition.
*
     Statics: t_Masks type standard table of X
                      initial size 0.
*
     Data: Begin of w_Char,
                 Asc type x,
           End of w_Char,
*
           w_String type Hash_Key,
           w_Mask   type x,
           w_H      type x,
           w_H1     type x,
           w_H2     type x,
           w_Hash   type i,
           w_Pos    type i,
           w_Len    type i.
*
*    The t_Masks table contains a series of random numbers between 0 and
*    255.  These are used to calculate the hash number for a given
*    character.  As these need to be identical for each run,  they are
*    hard coded here.
*
*    As these are relevant to this procedure only,  rather than make
*    global and initialise them once,  make them static and still only
*    initialise them once.
*
     Read table t_Masks index 1 transporting no fields.
     If sy-subrc <> 0.
        Load_Table: '8C', 'F7', '5F', 'A0', '23', 'BD', 'B7', 'DF',
                    'D1', 'AA', '45', '73', '97', '12', '1E', 'F2',
                    '40', 'E0', '93', '32', 'DD', '36', '4E', '0C',
                    '72', '54', '9E', '5F', 'EF', 'BB', '10', '57',
                    '62', '92', '3F', 'EF', '6A', '48', 'ED', 'B4',
                    'EF', '7B', '52', 'CC', '10', '19', 'B3', '38',
                    '5D', 'C5', '37', '56', '47', '7C', 'F7', 'AA',
                    'D4', '78', '54', 'DD', '97', '54', '8D', '06',
                    'E0', '72', '90', '29', '30', '9A', '11', 'FD',
                    'F0', 'E3', 'DA', 'F3', '62', 'D7', '62', '73',
                    'D7', 'D2', 'A0', '69', '23', 'AB', '21', '00',
                    '4E', '96', '59', 'AD', '8C', '49', '36', '70',
                    '6F', '5E', 'FB', '57', '5C', 'F9', '4C', '43',
                    '3B', 'AA', '85', 'EE', '73', '95', '50', '2D',
                    '16', 'D0', '77', '73', '58', '0C', 'F6', '97',
                    '46', '78', '55', 'D7', 'B5', 'E2', '35', '1C',
                    '78', '1F', '28', '7F', 'D6', 'AE', 'C6', '0D',
                    '3A', '98', 'FD', 'C7', '2D', '9A', 'A8', 'ED',
                    '82', '86', '63', '7D', 'D0', 'E7', '9E', 'F6',
                    '25', 'E4', 'F1', '61', 'F9', '67', 'AF', '92',
                    '61', '7D', 'BE', 'AC', '85', '00', 'A6', 'E3',
                    '54', '74', 'E7', '86', '77', '30', '90', '3C',
                    '83', 'BE', '0D', '8D', '72', '84', '41', 'A5',
                    '54', 'A3', 'D4', '55', '42', '1F', 'CF', '5B',
                    '94', '40', '66', 'E3', '53', '39', '14', '4D',
                    'F1', '08', 'EE', '31', '38', '9D', '30', 'A1',
                    '81', '3E', '1D', 'AE', '26', '2A', '06', '2D',
                    '3A', '7D', 'A8', 'BA', '77', '53', 'BA', 'FE',
                    '77', '30', 'C7', '2E', '27', 'A0', '3A', 'D4',
                    '79', '1A', 'B7', 'D2', '5A', '2A', 'B2', 'A4',
                    'E4', 'CF', '3A', 'E5', 'D4', '22', '15', '15',
                    '3E', '39', '12', '99', '7F', '4B', '9B', '03'.
     EndIf.
     Move pu_String to w_String.
     Compute w_Len = Strlen( w_String ) - 1.
     Clear w_hash.
     If w_Len <> 0.
        Translate w_String to Upper Case.
        Move w_String+0(1) to w_Char.
        Move w_Char-Asc to w_H1.
        Compute w_H2 = w_H1 + 1.
        Move 1 to w_Pos.
        Do w_Len times.
           Move w_String+w_Pos(1) to w_Char.
           Move w_Char-Asc to w_H.
           Compute w_H1 = w_H1 Bit-Xor w_H.
           Read Table t_masks Index w_H1 into w_H1.
           Add 1 to w_h.
           Compute w_H2 = w_H2 Bit-Xor w_H.
           Read Table t_masks Index w_H2 into w_H2.
           Add 1 to w_Pos.
        EndDo.
     EndIf.
     Compute w_Hash = 1 + ( w_H1 * 256 ) + w_H2.
     Move w_Hash to pc_hash.
EndForm.
*Eject
***********************************************************************
*
*       Procedure:     Display_Report
*
*       Purpose:       Provides the input fields and a graphical display
*                      showing the distribution of the records inserted
*                      in the table in # Occupied rows per 100 rows.
*
*                      The report also has two input fields,  a key
*                      value field and a 'More Rows' field.
*
*                      Entering a value in the key value field and
*                      clicking the line-select button at the top of
*                      report searches for and adds or displays the
*                      record.
*
*                      Entering a number in the 'More Rows' field
*                      populates that many more rows.
*
*       Entry:         Table of hashed keys.
*                      Any message to print.
*                      Last Hash search runtime
*
*       Exit:          As above
*
*       Called By:     Perform Display_Report using t_Hash_Table.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Display_Report using t_Hash_Table type Hash_Table
                          pu_Msg       type NaTxt
                          pu_Runtime   type i.
*
     Define Output_Block.
*
*           Need a new line ?
*
            If w_Column > 75.
               Write sy-vline.
               Write :/c_Graphic_Start sy-vline no-gap.
               Compute w_Column = c_Graphic_Start + 1.
            EndIf.
            Format Color = w_Block_Col.
            Write '*' no-gap.
            Format Reset Intensified on.
            Add 1 to w_Column.
     End-Of-Definition.
*
     Constants: c_Graphic_Width type i value 73,
                c_Graphic_Start type i value 4,
                c_Block_Size    type i value 100,
                c_Max_Colours   type i value 7,
                c_Colour_Mod    type i value 8.

     Data: w_Hash_Record type Hash_Record,
           w_Rec_Count   type i,
           w_Occupied    type i,
           w_Col_Size    type i,
           w_Col         type i,
           w_Block_Col   type i,
           w_Column      type i,
           w_Blocks_Left type i,
           w_Start       type i,
           w_End         type i,
           w_Cur_Col     type i.
*
     Subtract 1 from sy-lsind.
     Write :/ 'Enter Key    :',g_Key input on.  Hide g_Key.
     Skip 1.
     Write :/ 'Add More Rows:',g_Add input on.  Hide g_Add.
     Skip 1.
     If pu_Msg <> ''.
        Write :/ pu_Msg.
        Skip 1.
     EndIf.
*
     Write:/ 'Longest Search Time:', pu_Runtime, 'Msecs'.
     Skip 1.
*
*    Display a schematic of the t_hash table where one block on the
*    screen represents the percentage of occupied rows in that block
*    of 100 records
*
*    7 colours by 2 intensities.....
*
     Compute w_Col_Size = Trunc( c_Block_Size / c_Max_Colours ).
*
     Move 0 to w_Rec_Count.
     Move 0 to w_Occupied.
     Write :/c_Graphic_Start sy-uline+0(c_Graphic_Width).
     Write :/c_Graphic_Start sy-vline no-gap.
     Compute w_Column = c_Graphic_Start + 1.
     Loop at t_Hash_Table Into w_Hash_Record.
          If w_Rec_Count = c_Block_Size.
*
*            Decide the colour to use for this block
*
             Compute w_Block_Col = w_Occupied Div w_Col_Size.
             Compute w_Block_Col = w_Block_Col Mod c_Colour_mod.
             Output_Block.
             Move 0 to w_Rec_Count.
             Move 0 to w_Occupied.
          EndIf.
          Add 1 to w_Rec_Count.
          If w_Hash_Record-Key <> ''.
             Add 1 to w_Occupied.
          EndIf.
     EndLoop.
*
*    Finish off the last block and then pad to 65535.
*
     Output_Block.
     Describe table t_Hash_Table lines w_Blocks_Left.
     Compute w_Blocks_Left = Trunc( ( 65535 - w_Blocks_Left )
                           div c_Block_Size ).
     Move 0 to w_Block_Col.
     Do w_Blocks_Left Times.
        Output_Block.
     EndDo.
     Write at 76 sy-vline.
     Write :/c_Graphic_Start sy-uline+0(c_Graphic_Width).
     Skip 1.
     Write :/ 'Key:'.
     Move 0 to w_Start.
     Move -1 to w_Cur_Col.
     Do 100 times.
        Compute w_Col = sy-Index Div w_Col_Size.
        If w_Col <> w_Cur_Col.
           If w_Cur_Col <> -1.
              Compute w_Block_Col =  w_Cur_Col Mod c_Colour_Mod.
              Compute w_End = sy-Index - 1.
              Format Color = w_Block_Col.
              Write :/ 'Occupied: From',w_Start,
                       'to', w_End,
                       'of the last', c_Block_size.
              Move sy-Index to w_Start.
           EndIf.
           Move w_Col to w_Cur_Col.
        EndIf.
     EndDo.
    Compute w_Col = 100 Div w_Col_Size.
    Compute w_Block_Col = w_Col Mod c_Colour_Mod.
    Compute w_End = 100.
    Format Color = w_Block_Col.
    Write :/ 'Occupied: From',w_Start,
             'to', w_End,
             'of the last', c_Block_size.
Endform.
*Eject
***********************************************************************
*
*       Procedure:     Hash_Collision
*
*       Purpose:       This procedure handles the situation where one
*                      key hashes to the row number of a different key.
*
*                      In this case the initial hash code is used as a
*                      starting place,  the table being searched
*                      in sequential fashion from that point onwards
*                      until either the key is found or  a blank record
*                      is found.
*
*                      The table is limited to 65535 entries so the
*                      count cycles at the top of the table,  ending
*                      when the original record is encountered again.
*
*                      If the top of the table is reached before row
*                      65535 then this is treated as a new record.
*
*       Entry:         Key string to generate hash for.
*                      Calculated Hash code
*                      Table of existing hash records
*
*       Exit:          Hash code the specified key maps to or
*                      zero if no available record can be found
*
*       Called By:     Perform Hash_Collision using w_Hash_Key
*                                                   w_Hash_Code
*                                                   t_Hasht
*                                          Changing w_Hash_Code.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Hash_Collision using pu_Key       type Hash_Key
                          pu_Code      type Hash_Code
                          t_Hash_Table type Hash_Table
                 Changing pc_Code      type Hash_Code.
*
     Define Increment_Hash.
            Add 1 to w_Hash_Code.
            If w_Hash_Code > 65535.
               Move 1 to w_Hash_Code.
            EndIf.
     End-Of-Definition.
*
     Data: w_Hash_Code   type Hash_Code,
           w_Hash_Record type Hash_Record.
*
     Move pu_Code to w_Hash_Code.
     Increment_Hash.
     Read Table t_Hash_Table index w_Hash_Code into w_Hash_Record.
     While w_Hash_Record-Key <> ''
           and w_Hash_Record-Key <> pu_Key
               and w_Hash_Code <> pu_Code
                   and sy-subrc = 0.
                       Increment_Hash.
                       Read Table t_Hash_Table index w_Hash_Code
                             into w_Hash_Record.
     EndWhile.
*
*    No Space ???
*
     If w_Hash_Code = pu_Code.
        Move 0 to w_Hash_Code.
     EndIf.
*
     Move w_Hash_Code to pc_Code.
EndForm.
*Eject
***********************************************************************
*
*       Procedure:     Insert_Row
*
*       Purpose:       This routine inserts a record in the hash table
*                      at the specified position.  If the position does
*                      not exist,  the table is extended until it does.
*
*       Entry:         Key value to insert
*                      Hash code (ie row number) to use
*                      Hash table to insert into
*
*       Exit:
*
*       Called By:     Perform Insert_Row using w_key w_code t_hash.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Insert_Row using pu_Key       type Hash_Key
                      pu_Code      type Hash_Code
                      t_Hash_Table type Hash_Table.
*
     Data w_Hash_Record type Hash_Record.
*
*    Does the record exist ?
*
     Read Table t_Hash_Table into w_Hash_Record index pu_Code.
     If sy-subrc <> 0.
*
*       Nope - Extend the table till it does
*
        While Sy-Subrc <> 0.
              Clear w_Hash_Record.
              Append w_Hash_Record to t_Hash_Table.
              Read Table t_Hash_Table index pu_Code into w_Hash_Record.
        EndWhile.
     EndIf.
*
*    And insert the values.
*
     Move pu_Key to w_Hash_Record-Key.
     Move 0      to w_Hash_Record-Count.
     Modify t_Hash_Table from w_Hash_Record index pu_Code.
EndForm.
*Eject
***********************************************************************
*
*       Procedure:     Populate_Table
*
*       Purpose:       This routine populates an internal table with
*                      a series of strings up to a max length of 10
*                      in their hashed positions to provide some data
*                      for testing the hashing function.
*
*       Entry:         Blank table of Hash Records
*
*       Exit:          Partially filled table of random strings.
*                      Runtime of last hash search.
*
*       Called By:     Perform Populate_Table using t_Hasht.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Populate_Table using t_Hash_Table type Hash_Table
                          pu_Add_Count type i
                 Changing pc_Msg       type NaTxt
                          pc_Runtime   type i.

     Data: w_ran_int     type i,
           w_Len         type i,             " Length of key to generate
           w_Key         type Hash_Key,      " Key string generated
           w_Hash        type Hash_Code,     " Hash code of key string
           w_Prcnt       type f,             " Progress
           w_Msg         type Natxt,         " Progress text
           w_Jog         type f,             " Boundary at which %'s
                                             " displayed
           w_Txt_Num(20) type c,             " Num->Text
           w_Runtime     type i.
*
*    Decide whether to display on 1's 10's 100's etc
*
     Move 1 to w_Jog.
     Move pu_Add_Count to w_Ran_Int.
     While w_Ran_Int > 0.
           Multiply w_Jog By 10.
           Divide w_Ran_Int by 10.
     EndWhile.
     Divide w_Jog by 100.
     If w_Jog > 10000.
        Move 10000 to w_Jog.
     EndIf.
*
     Do pu_Add_Count times.
*
*       How many long is the key ?
*
        w_Key = ''.
        Call Function 'QF05_RANDOM_INTEGER'
          Exporting
            Ran_Int_Max         = 10
            Ran_Int_Min         = 1
          Importing
            Ran_Int             = W_Len
          Exceptions
            Invalid_Input       = 0
            Others              = 0.
*
*       Generate the key
*
        Do w_Len times.
           Call Function 'QF05_RANDOM_INTEGER'
             Exporting
               Ran_Int_Max         = 25
               Ran_Int_Min         = 0
             Importing
               Ran_Int             = W_Ran_Int
             Exceptions
               Invalid_Input       = 0
               Others              = 0.
           Concatenate w_Key sy-ABCDE+w_Ran_Int(1) into w_Key.
        EndDo.
*
*       And put it in the table.
*
        Perform Calculate_Hash using w_Key t_Hash_Table
                            changing w_hash
                                     w_Runtime.
        If w_Runtime > pc_Runtime.
           Move w_Runtime to pc_RunTime.
        EndIf.
*
*       If the hash is zero then there's no place for it to go.....
*
        If w_Hash <> 0.
           Perform Insert_Row using w_Key w_Hash t_Hash_Table.
        Else.
           Exit.
        EndIf.
*
*       Show them we're still awake Every w_jog records
*
        Compute w_Prcnt = Trunc( sy-Index / w_Jog ) * w_Jog.
        If w_Prcnt = sy-Index.
           Write sy-Index to w_Txt_Num.
           Condense w_Txt_Num.
           Write pu_Add_Count to w_Msg.
           Condense w_Msg.
           Concatenate w_Txt_Num
                       'of'
                       w_Msg
                       'added.'
                  into w_Msg
             separated by ' '.
           Compute w_Prcnt = ( sy-Index / pu_Add_Count ) * 100.
           Call Function 'SAPGUI_PROGRESS_INDICATOR'
             Exporting
               Percentage       = w_Prcnt
               Text             = w_Msg.
        EndIf.
     Enddo.
*
*    Any message ?
*
     If w_Hash = 0.
        Move 'Table is full.' to pc_Msg.
     EndIf.
EndForm.
*Eject
***********************************************************************
*
*       Procedure:     Search_Insert
*
*       Purpose:       This routine searches for the specified key. If
*                      the key is not found the key is inserted in the
*                      table.
*
*       Entry:         Hash key to insert
*                      Hash table
*
*       Exit:          Key is found or inserted into table
*                      Runtime of last hash search.
*
*       Called By:     Perform Populate_Table using t_Hasht.
*
*       Calls:
*
*       Modification History:
*
*   Date    Reason                                         Version  Who
*
Form Search_Insert using pu_Key       type Hash_Key
                         t_Hash_Table type Hash_Table
                Changing pc_Runtime   type i
                         pc_Msg       type Natxt..
*
     Data: w_Hash_Record type Hash_Record,
           w_Key         type Hash_Key,
           w_Hash        type Hash_Code,
           w_Runtime     type i.
*
     Move pu_Key to w_Key.
     Translate w_Key to upper case.
     Perform Calculate_Hash using w_Key t_Hash_Table
                         changing w_hash
                                  w_Runtime.
     If w_Runtime > pc_Runtime.
        Move w_Runtime to pc_RunTime.
     EndIf.
*
*    If the hash is zero then there's no place for it to go.....
*
     If w_Hash <> 0.
        Read table t_Hash_Table into w_Hash_Record index w_Hash.
        If w_Hash_Record-Key = ''.
           Perform Insert_Row using w_Key w_Hash t_Hash_Table.
           Concatenate w_Key 'Inserted into table'
                  into pc_msg
             separated by ' '.
        Else.
           If w_Hash_Record-Key = w_Key.
              Write w_Runtime to pc_Msg.
              Condense pc_Msg.
              Concatenate w_Key 'Found in' pc_Msg 'Msecs'
                     into pc_Msg
                separated by ' '.
           Else.
              Move 'Whoops - problems here wrong key' to pc_Msg.
           EndIf.
        EndIf.
     Else.
        Move 'No table space.' to pc_Msg.
     EndIf.
EndForm.


Index Tables

Index tables are a generic name for the Standard and Sorted tables. The term index table is used in the declaration of a procedure or function module's arguments if the argument is a standard or sorted table and you have not declared a table type for the relevant table. There is however one downside to this in that you cannot use the READ TABLE command specifying a key. (The table has no structure....) You can however, loop round it quite happily, assigning a field symbol to the table structure.

For example, the procedure declaration:

Code: Select all
Form Seq_Search using pu_Key        type Char_Key
                      t_Stdrd_Table type Value_Table.


could be recorded as:

Code: Select all
Form Seq_Search using pu_Key        type Char_Key
                      t_Stdrd_Table type Index Table.


Any Table

Another declaration. This can be used in the same manner as Index tables to specify a generic table as a form parameter. The only operations (such as LOOP etc) that can be performed on a table declared as this type are those of the Hashed tables.

What use are the different tables.

The different table types are not provided just to make our lives difficult. They each have their own pros and cons. Generally the con is the amount of memory needed to implement a table of the specified type. The pros are varied.

Standard table types are (or I do anyway...) generally used to hold data as a temporary staging area after being read from the database (you do use SELECT ... INTO TABLE rather than SELECT ... ENDSELECT don't you ?). These type of tables can hold large amounts of information at the lowest cost to memory. Relatively they are slower to search than the sorted or hashed tables as the records could be unordered, the only sure way of finding that an entry is not in the table is to search the table from start to finish.

Sorted tables automatically sort the rows into a specified key order. This enables a faster search of the table as large amounts of information can be discounted quickly. These are handy as they provide easier ways of reporting control breaks and so forth. However, I do not tend to use these as either I provide the user with the ability to sort the report by whatever fields they require meaning that a fixed key limits this, or I tend to use Hash tables if I require a look up.

As mentioned above, and shown in the example program above, Hash tables are at their best being used as a look up table. The access time is fast, it's constant and using one of these properly can certainly speed up your program.
Regards

Rich

Image
Abap KC:http://www.richard-harper.me.uk/Kb
SFMDR:http://www.se37.com
Rich
 
Posts: 7112
Joined: Thu Oct 31, 2002 4:47 pm
Location: Liverpool

Return to ABAPers

Who is online

Users browsing this forum: No registered users and 1 guest





loading...


This website is not affiliated with, sponsored by, or approved by SAP AG.