/*****************************************************************************************************************
 
SAS file name: array_hash_character.sas
File location: 
__________________________________________________________________________________________________________________
 
Purpose: To demonstrate array hasing in SAS with character keys.
Author: Peter Clemmensen
Creation Date: 09/10/2020
 
This program supports the blog post "Array Hashing With Character Key Values" on SASnrd.com

*****************************************************************************************************************/

proc datasets lib=work nolist kill;
run;

/* Example Data */
data large(keep = k) small;
   call streaminit(123);
   length k $ 20;
   do _N_ = 1 to 1e7;
      k = uuidgen();
      d = rand('integer', 1, 1e6);
      output large;
      if rand('uniform') < .1 then output small;
   end;
run;

/* Find a fitting prime */
%let load = 0.5;
data _null_;
   do p=ceil(p/&load) by 1 until (j = up + 1);
      up = ceil(sqrt(p));
      do j=2 to up until (not mod(p,j)); end;
   end;
   call symput('hsize',left(put(p,best.)));
   stop;
   set small nobs=p;
run;

%put &hsize.;

/* Array Hashing */
data arrayhash(keep=k d) / stack = 100;
   array key  {0 : &hsize.} $20 _temporary_;
   array link {0 : &hsize.}     _temporary_;
   array data {0 : &hsize.}     _temporary_;
   r=&hsize.;

   do until (lr1);
      set small end = lr1;
      h = mod(input(k, pib6.), &hsize.) + 1; 
      found = 0;

      if link [h] > . then do;                  
         link traverse;                         
         if found then continue;
         do r=r by -1 until (link [r] = .);       
         end;
         link [h] = r;                          
         h        = r;
      end;

      link [h] = 0;                             
      key  [h] = k;
      data [h] = d;
   end;

   do until (lr2);
      set large end = lr2;
      found = 0;
      h = mod(input(k, pib6.), &hsize.) + 1;      
      if link[h] > . then link traverse;        
      if found then d = data[h];                
      else d = .;
      output;
   end;

   stop;

   traverse:

   if k = key [h] then found = 1;
   else if link [h] ne 0 then do;
      h = link [h];
      link traverse;
   end;
run;

/* Hash Object Approach */
data hash(drop=rc);
   if _N_=1 then do;
      declare hash h(dataset:'small', hashexp:20);
      h.definekey('k');
      h.definedata('d');
      h.definedone();
   end;

   set large;
   d=.;

   rc=h.find();
run;

/* Verify that the two results are identical */
proc compare base=arrayhash comp=hash; run;