SAS中的哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
在SAS中使用哈希表十分简单，并不需要知道SAS内部是怎么实现的，但要需要知道哈希表是存储在内存中的，因而容量有一定的限制；在哈希表中“查找”并不是真的查找，而是根据key值直接获得存储的地址。
SAS提供了两个类来处理哈希表，用于存储数据的Hash和用于遍历的Hiter。Hash类提供了查找、添加、修改、删除等方法，Hiter提供了用于定位和遍历的first、next等方法。
使用Hash表有以下的一些优点：
* 键值的查找是在内存中进行的，有利于提高性能。
* Hash表可以在数据步运行时动态地添加更新或删除记录。也就是说，Hash表可以对数据进行一些微观的操作。
* 在Hash表中可以很快地定位数据，由键值直接得到存储的地址，减少了查找次数。
* 使用Hash可以做一些merge和sql难以实现的数据集合并，在细节上可以有更多的控制。
定义Hash类需要有下面三个步骤:
1. 定义一个对象。
2. 实例化该对象。
3. 初始化该并对属性赋值。
之后就可以调用Hash类的函数实现需要的功能：包括添加、查找、替换、删除等等。
* 定义对象
declare hash myhash;
myhash = _new_ hash();
或者
declare hash myhash();
* 初始化对象
declare hash variable_name(argument_tag-1 : value-1
<, …argument_tag-n: value-n>);
或者
variable_name = _new_ hash(argument_tag-1: value-1
<, …argument_tag-n: value-n>);
初始化时的参数：
hashexp: hash表的框数。
在查找数据时，SAS首先用hash function得到数据所在的“框”，然后再框内查找key对应的记录。框内的记录是用树形结构组织的。因而数据查找的时间复杂度为O(log(N/HSIZE))，N为记录的条数，Hsize为框数；因此尽量用最多的框。
dataset: 定义从哪个数据集中导入数据到哈希表里
ordered: 定义使用hiter变量hash表及输出hash表到数据集时的顺序。
ascending | a : 根据key值升序。
descending | d : 根据key值降序。
YES | Y : 升序。
NO | N : 不排序。
例子：
data participants;
input name $ gender:$1. treatment $;
datalines;
John M Placebo
Ronald M Drug-A
Barbara F Drug-B
Alice F Drug-A
;
data weight(drop=i);
input date:DATE9. @;
do i = 1 to 4;
input name $ weight @;
output;
end;
/* For brevity, only two dates are listed below */
datalines;
05May2006 Barbara 125 Alice 130 Ronald 170 John 160
04Jun2006 Barbara 122 Alice 133 Ronald 168 John 155
;
data results;
length name treatment $ 8 gender $ 1;
if _N_ = 1 then do;
declare hash h(dataset:’participants’);
h.defineKey(’name’);
h.defineData(’gender’, ‘treatment’);
h.defineDone();
end;
set weight;
if h.find() = 0 then
output;
run;
proc print data=results;
format date DATE9.;
var date name gender weight treatment;
run;
Output:
1 05MAY2006 Barbara F 125 Drug-B
2 05MAY2006 Alice F 130 Drug-A
3 05MAY2006 Ronald M 170 Drug-A
4 05MAY2006 John M 160 Placebo
5 04JUN2006 Barbara F 122 Drug-B
6 04JUN2006 Alice F 133 Drug-A
7 04JUN2006 Ronald M 168 Drug-A
8 04JUN2006 John M 155 Placebo
说明
Hash是一个类，使用前需要首先进行实例化和初始化，然后定义常用的属性，在定义完成后才能调用对象的一些方法。
本例中declare hash h(dataset:’participants’);将数据集participants实例化成了一个hash对象h，接下来使用defineKey和 defineData定义hash表的键和值。接着使用defineDone来说明hash表的定义已经完成。
本例使用了hash表的find方法，在读入一条观测后，使用find方法将得到与当前观测Key值相等的记录，如果找到匹配的记录（find返回的值为0）则输出Hash表和主表中的所有变量当前的值。
* Example two: Add/Replace/Output
data goals;
input player $ when & $9.;
datalines;
Hill 1st 01:24
Jones 1st 09:43
Santos 1st 12:45
Santos 2nd 00:42
Santos 2nd 03:46
Jones 2nd 11:15
;
data _null_;
length goals_list $ 64;
if _N_ = 1 then do;
declare hash h();
h.defineKey(’player’);
h.defineData(’player’, ‘goals_list’);
h.defineDone();
end;
set goals end=done;
if h.find() ^= 0 then do;
goals_list = when;
h.add();
end;
else do;
goals_list = trim(goals_list) || ‘, ‘ || when;
h.replace();
end;
if done then
h.output(dataset:’goal_summary’);
run;
proc print data=goal_summary;
run;
Output
Obs player goals_list
1 Hill 1st 01:24
2 Santos 1st 12:45, 2nd 00:42, 2nd 03:46
3 Jones 1st 09:43, 2nd 11:15
说明
这个例子使用了find/add/replace/output这四个函数，与上个例子不同，本例没有通过数据集来构建一个Hash对象，刚开始时 Hash表中并没有记录。首先通过find查看Hash表中有无player值匹配的记录，如果没有就使用add方法将当前观测的键和值插入到Hash表中。如果Hash表中已经有和当前观测player值相等的记录，则使用replace方法更新Hash表中该记录的值。在处理完goals中的所有观测后，使用output方法将Hash表中的记录输出到数据集中。
在使用add时，如果hash表中已经存在相应的Key，当前的观测会被忽略。
需要注意replace和add的不同，由于在Hash表中相同的key值只能对于的到一条记录，当hash表中已存在与当期处理的观测Key值相同的记录时；使用replace，该Key对应的值将被替换；使用add时，由于hash表中已经存在对应的记录，所以add将被忽略。
Hiter Object
/* Create Input Data Set */
data patients;
length patient_id $ 16 discharge 8;
input patient_id discharge:DATE9.;
datalines;
Smith-4123 15MAR2004
Hagen-2834 23APR2004
Smith-2437 15JAN2004
Flinn-2940 12FEB2004
;
/* Load and iterate over hash */
data _null_;
length patient_id $ 16
discharge 8;
declare hash ht(dataset:”patients”,
ordered:”ascending”);
ht.defineKey(”patient_id”);
ht.defineData(”patient_id”, “discharge”);
ht.defineDone();
declare hiter iter(”ht”);
rc = iter.first();
do while (rc=0);
put patient_id discharge:DATE9.;
rc = iter.next();
end;
run;
说明
declare hiter iter(”ht”);给哈希表ht定义了一个遍历器iter，之后调用first方法将遍历器定位到Hash表的第一条记录，然后使用next方法遍历Hash表中的所有记录并输出。
参考资料
SUGI 2008：《Hash Crash and Beyond》
SUGI 2008：《How Do I Love Hash Tables》
摘自：
http://sunix.name/2009/09/sas%E4%B8%AD%E7%9A%84%E5%93%88%E5%B8%8C%E8%A1%A8/
