发布时间：2010-5-13 16:45
分类名称：OpenSSL
今天学的是《OpenSSL编程》第四章 哈希表。这一章主要讲了OpenSSL中哈希表的用法，和堆栈一样，OpenSSL实现了一个适用于任何数据类型的哈希表。
下面是哈希表中两个重要的数据结构，这些数据结构的定义在/crypto/lhash/lhash.h中：
这个结构体是一个链表，链表的每一个节点都是一个用户存入的数据：
typedef struct lhash_node_st
{
void *data; //用于保存指向数据的指针
struct lhash_node_st *next; //形成一个链表
#ifndef OPENSSL_NO_HASH_COMP
unsigned long hash; //数据的哈希值
#endif
} LHASH_NODE;
这个结构体表示一个哈希表：
typedef struct lhash_st
{
LHASH_NODE **b; //这是一个LHASH_NODE的指针数组，用于保存数据
LHASH_COMP_FN_TYPE comp; //哈希表的比较函数，OpenSSL提供默认的比较函数
LHASH_HASH_FN_TYPE hash; //哈希表的哈希函数，OpenSSL提供默认的哈希函数
unsigned int num_nodes;
unsigned int num_alloc_nodes; //b的长度
unsigned int p;
unsigned int pmax;
unsigned long up_load; /* load times 256 */ //装填因子的上限
unsigned long down_load; /* load times 256 */ //装填因子的下限
unsigned long num_items; //表中所存的数据的个数
/*下面的成员都是给各个操作计数用的，没什么好说的*/
unsigned long num_expands;
unsigned long num_expand_reallocs;
unsigned long num_contracts;
unsigned long num_contract_reallocs;
unsigned long num_hash_calls;
unsigned long num_comp_calls;
unsigned long num_insert;
unsigned long num_replace;
unsigned long num_delete;
unsigned long num_no_delete;
unsigned long num_retrieve;
unsigned long num_retrieve_miss;
unsigned long num_hash_comps;
int error;
} LHASH;
上面的结构体就是哈希表的结构体，要想理解OpenSSL中哈希表的实现，这个结构体中第一部分的成员每个的意义都必须理解才行。而这一部分的成员有一些可以通过字面意思就知道它们做什么用的，但是还有３个是一两句注释说不清楚的，它们分别是：num_nodes，p，pmax。至于这３个成员分别什么意思，一会儿下面再说，我们现在先看一下OpenSSL的哈希表是如何解决冲突的。
从上面两个结构体，我们可以大概看出，OpenSSL的哈希表是把数据data的地址保存在结构LHASH_NODE中，然后用哈希函数计算出数据data对应的哈希值，再通过得到的哈希值计算出保存数据地址的结构体在数组b中的下标，最后把结构体的地址保存到数组b相应的下标处。
不过，在哈希表中经常存在冲突：
１. 因为哈希函数的问题导致两个不同数据的哈希值相同
２. 因为两个不同数据的不同的哈希值，在计算在数组b中的下标时，得到的是相同的下标
以上这两个原因都导致两个不同的数据在数组b中发生冲突，那么如何解决冲突就成为一个不可避免的问题。
通常，哈希表中解决冲突的方法有下面几种：
１. 开放定址法
２. 再散列法
３. 链地址法
４. 建立一个公共溢出区
在OpenSSL中，解决冲突的方法是链地址法。也就是说，当有多个数据因为上面所说的两个任一个原因，要存在数组b的同一个下标下面，这时，OpenSSL会建立一个链表，把这些数据存入同一个链表中，并把这个链表的头指针存入数组b的那个下标处。
举个例子，比如现在有一个数据data1，哈希值为hash1，要把这个数据存入哈希表中，指向哈希表的指针为lh，假设，此时data1不会发生冲突，并且通过计算得到data1所对应的下标是５，也就是说OpenSSL会通过下面的语句把data1存入哈希表中（为了代码清爽，下面代码只说明了意思，OpenSSL源代码不是这个样子的）：
LHASH_NODE *new_node = (LHASH_NODE *)malloc(sizeof(LHASH_NODE));
new_node->data = &data;
new_node->next = NULL;
new_node->hash = hash1;
lh->b[5] = new_node;
这样就可以把一个数据插入表lh中了。这时，数组b下标为５的元素处，应该是这个样子的：
b[5]---------->LHASH_NODE(data1, hash1)---------->NULL
假如，现在又来了一个数据data2，哈希值是hash2，但根据计算，data2也要存入数组b中下标为５的地方，这就会发生冲突，前面说了，OpenSSL是通过链地址法来解决冲突的。这时，OpenSSL会通过下面的语句把data2链到data1的后面去（为了代码清爽，下面代码只说明了意思，OpenSSL源代码不是这个样子的）：
LHASH_NODE *new_node = (LHASH_NODE *)malloc(sizeof(LHASH_NODE));
new_node->data = &data2;
new_node->next = NULL;
new_node->hash = hash2;
node1->next = new_node; //假设node1是指向数据为data1的结构的指针
这时，数组b下标为５的元素处，应该是这个样子的：
b[5]---------->LHASH_NODE(data1, hash1)---------->LHASH_NODE(data2, hash2)---------->NULL
假如，现在又来了一个数据data3，哈希值为hash1（和data1的哈希值一样），显然，这个数据也应该存入数组b中下标为５的地方。此时，OpenSSL会通过上面的代码把它插入到哈希表中，插入完成后，数组b下标为５的元素处应该是这个样子的：
b[5]---------->LHASH_NODE(data1, hash1)---------->LHASH_NODE(data2, hash2)---------->LHASH_NODE(data3, hash1)---------->NULL
从上面可以看出，OpenSSL是怎样通过链地址法来解决冲突的，也可以看出，在同一个链表中的数据，一部分是因为它们的哈希值一样，另一部分是因为它们的哈希值不一样，而在数组中所处的位置一样造成的。
上面说明了OpenSSL的哈希表的解决冲突方面是如何做的。接下来，我们看一下，OpenSSL的哈希表是如何从一个数据的哈希值得到该数据在数组b中的下标的。
可以想像，当哈希表已经很满的时候（目前不考虑哈希函数比较烂的情况），发生冲突是很经常的，这时，哈希表中会存在很多个链表，而要访问这些链表中的某个数据时，需要把整个链表遍历一遍，时间复杂度会上升，这使得哈希表的优势不再明显。此时，要不然禁止再往哈希表中再插入数据，或者将哈希表的数组b增长一些，并把那些链表的元素往数组b新增的部分均一些，这样就会使情况好一点。OpenSSL使用的就是后一种方法，当哈希表比较满时，就把数组b增长一倍，并作一些相应的操作。
至于，OpenSSL怎么知道什么时候表比较满，什么时候表比较不满，我们先来看一个概念，哈希表的装填因子（load factor），这个值用来表示哈希表的填满程度，这个值在OpenSSL中的计算方法如下：
装填因子(a) ＝ num_items ／ num_nodes
在OpenSSL中，给哈希表插入数据和删除数据时，会用装填因子判断是否应该扩大或者缩小表：
插入函数中：
expand(lh); //如果地方不够，就把地方弄大一点
删除函数中：
contract(lh); //如果地方剩得太多，就把地方弄小一点
其中，up_load = 2 * 256，down_load = 256。
在OpenSSL中，数组b的初始化大小为MIN_NODES，这是一个宏定义，值为16，在初始化函数中，把几个有用的成员都设为下面的值：
num_nodes = MIN_NODES / 2;
num_alloc_nodes = MIN_NODES;
p = 0;
pmax = MIN_NODES / 2;
从上面可以看出，数组b的总长度用num_alloc_nodes表示，其实从代码中也可以看出pmax的值始终等于num_alloc_nodes / 2。下面，要说明的是成员p，pmax，num_nodes是什么意思。
在OpenSSL实现的哈希表中，虽然数组b的长度是num_alloc_nodes，但数组b中，数据并不是保存在0 ~ num_alloc_nodes - 1之间的，而是保存在0 ~ num_nodes - 1之间的。
现在，我们先看一下上面提到的函数expand是怎么实现的：
static void expand(LHASH *lh) //lh为要增长的哈希表
{ //刚才说，当存储地方变大的时候，得把一些链表里的数据匀到那些新多出来的地方去，
//函数expand执行一次，就会把数组下标为p的那一行链表中一部分数据匀到下标为p + pmax的那一行去，
//然后给p加1，因为p是从0开始的，所以p + pmax是从pmax开始的，
//当第一次执行完此函数时，p值为1，num_nodes值为9，pmax值为8，也就是说，函数expand执行完后，
//会把数组b中，下标为0的那一行中的一部分数据，移动到下标为8的那一行中去，
//这些被移动的元素都是哈希值对pmax取余为p - 1，对num_alloc_nodes取余为pmax + p - 1的数据，
//这是因为num_alloc_nodes = 2 * pmax，所以当装填因子还没有到上限时，expand函数不会执行，
//而此时的p值为0，所有数据的下标都是通过nn = hash % pmax得到的，这就会导致当hash值为p, pmax +p,
// 2pmax + p, 3pmax + p, 4pmax + p, ....时，都会落到下标为0的那一行，而当装填因子达到上限时，
// 需要多增大一些空间， 这时，会把第p行的数据匀一部分到第p + pmax行去，
// 这样，就会把hash值为pmax + p, 3pmax + p, ....这些数据 匀到过去，
// 这就是为什么下面在判断哪个数据该移动时，是用hash % num_alloc_nodes来计算的，
//而不是用hash % pmax来计算的。
LHASH_NODE **n,**n1,**n2,*np;
unsigned int p,i,j;
unsigned long hash,nni;
lh->num_nodes++;
lh->num_expands++;
p=(int)lh->p++;
n1= &(lh->b[p]);
n2= &(lh->b[p+(int)lh->pmax]); //一会儿要把n1所指向的链表的一部分数据匀到n2所指的那一行去
*n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
nni=lh->num_alloc_nodes;
for (np= *n1; np != NULL; )
{
#ifndef OPENSSL_NO_HASH_COMP
hash=np->hash;
#else
hash=lh->hash(np->data);
lh->num_hash_calls++;
#endif
if ((hash%nni) != p)
{ /* move it */ //这些数据就是应该被匀过去的数据
*n1= (*n1)->next;
np->next= *n2;
*n2=np;
}
else
n1= &((*n1)->next);
np= *n1;
}
if ((lh->p) >= lh->pmax)
{ //如果p和pmax相等，就说明从0 ~ pmax - 1行，每一行都被匀过了，这也就意味着表已经实在没有地方了，
//这时就应该把数组b的长度增为原来的２倍，pmax也增为原来的２倍，p设为0
j=(int)lh->num_alloc_nodes*2;
n=(LHASH_NODE **)OPENSSL_realloc(lh->b, (int)(sizeof(LHASH_NODE *)*j));
if (n == NULL)
{
lh->error++;
lh->p=0;
return;
}
/* else */
for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
n[i]=NULL; /* 02/03/92 eay */
lh->pmax=lh->num_alloc_nodes;
lh->num_alloc_nodes=j;
lh->num_expand_reallocs++;
lh->p=0;
lh->b=n;
}
}
函数contract和函数expand干的是相反的事，在这里就不多说了。
当有一个数据要插入表lh时，假设这个数据的哈希值为hash1，OpenSSL是通过下面的方法来确定该数据在数组中的下标的：
int nn = hash1 % lh->pmax;
nn = hash1 % lh->num_alloc_nodes;
这样，nn就是该数据所对应的下标了，要注意的是，lh->num_alloc_nodes是lh->pmax的２倍，当第一次算出来的nn小于lh->p时，就说明这个数据处于被匀过的那些行中，那么，就应该再看一下，这个数据是否可以被放到第p + pmax行去，才要让nn = hash1 % lh->num_alloc_nodes。
到此，OpenSSL哈希表结构的各个重要成员是什么意思就应该清楚了。
这里还要多说明的一个函数是getrn，此函数是一个内部函数，但很多函数都调用了它：
static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash)
{ //这个函数的作用确定在哈希表lh中，data保存在哪个LHASH_NODE结构中，返回值是指向那个LHASH_NODE
//的指针的地址。假设返回值为rn，若*rn == NULL，则说明表中没有与data一样的数据，如果要插入，
//则可直接插入，如果要删除，则无法删除（因为表中没有这一项）；而若*rn != NULL，则说明表中有一项，
//且这个项的内容与data相同，这一项的LHASH_NODE结构的地址为*rn，若要插入，则变为replace，
//若要删除，则可直接删除。
LHASH_NODE **ret,*n1;
unsigned long hash,nn;
LHASH_COMP_FN_TYPE cf;
hash=(*(lh->hash))(data);
lh->num_hash_calls++;
*rhash=hash;
nn=hash%lh->pmax;
if (nn < lh->p)
nn=hash%lh->num_alloc_nodes;
cf=lh->comp;
ret= &(lh->b[(int)nn]);
for (n1= *ret; n1 != NULL; n1=n1->next)
{
#ifndef OPENSSL_NO_HASH_COMP
lh->num_hash_comps++;
if (n1->hash != hash)
{ //先比哈希值，如果哈希值不一样，则值肯定不一样
ret= &(n1->next);
continue;
}
#endif
lh->num_comp_calls++;
== 0)
break;
ret= &(n1->next);
}
return(ret);
}
下面，我们来看关于哈希表的各个操作函数的用法：
1. LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
这个函数的作用是为用户产生一个哈希表，成功则返回指向哈希表的指针，否则返回NULL。需要两个参数，这两个参数分别是两个函数指针。第一个参数代表计算哈希值的哈希函数，第二个参数代表比较函数。这两个函数类型的定义如下：
typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *);
typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *);
2. void lh_free(LHASH *lh)
这个函数的作用是销毁一个哈希表，哈希表通过参数传入。这个函数销毁的只是哈希表中的数组b，和各个数据节点所占的内存，并不销毁数据所占的内存。如果想销毁哈希表的时候，同时也将数据所占内存销毁，那么就得自己写一个销毁数据的函数void func_free()，在执行lh_free(lh)之前，执行一次lh_doall(lh, func_free)才行。
3. void *lh_insert(LHASH *lh, void *data)
这个函数的作用是把data插入到哈希表lh中去，如果以前表中就有与data内容一样的数据，则把新的data存进去，把老的data通过返回值传出来。不过这个函数有一个Bug，在插入新值时，不论成功与否，返回值都是NULL。
4. void *lh_delete(LHASH *lh, const void *data)
这个函数的作用是把哈希表中与data值一样的那一项从哈希表lh中删去，如果成功，则返回表中与data值一样的那个data，如果失败，则返回NULL，这里的失败是指，哈希表中没有data。
5. void *lh_retrieve(LHASH *lh, const void *data)
这个函数的作用是在哈希表中查找是否存在与data值一样的项，若有，则返回该项在哈希表中保存的值，否则，返回NULL。
6. void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)
这个函数的作用是用函数func遍历哈希表lh中每一项元素，函数类型LHASH_DOALL_FN_TYPE的定义如下：
typedef void (*LHASH_DOALL_FN_TYPE)(void *);
这里的参数将会是结构LHASH_NODE的成员data。
7. void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
这个函数的作用是用函数func遍历哈希表lh中每一个元素，与上一个函数不同的是，这次的遍历函数，可以由用户传入一个参数，参数arg最后会做为参数传入函数func，函数类型LHASH_DOALL_ARG_FN_TYPE的定义如下：
typedef void (*LHASH_DOALL_ARG_FN_TYPE)(void *, void *);
这里的第一个参数将会是结构LHASH_NODE的成员data，第二个参数将会是arg。
8. unsigned long lh_strhash(const char *c)
这个函数是OpenSSL默认的哈希函数。
9. void lh_stats(const LHASH *lh, FILE *out)
这个函数的作用是把哈希表的状态输出到文件out中。实现在文件lh_stats.c中。
10. void lh_node_stats(const LHASH *lh, FILE *out)
这个函数的作用是把哈希表节点的状态输出到文件out中。实现在文件lh_stats.c中。
11. void lh_node_usage_stats(const LHASH *lh, FILE *out)
这个函数的作用是把哈希表使用的状态输出到文件out中。实现在文件lh_stats.c中。
12. void lh_stats_bio(const LHASH *lh, BIO *out)
这个函数的作用是把哈希表的状态输出到BIO out中。实现在文件lh_stats.c中。
13. void lh_node_stats_bio(const LHASH *lh, BIO *out)
这个函数的作用是把哈希表节点的状态输出到BIO out中。实现在文件lh_stats.c中。
14. void lh_node_usage_stats_bio(const LHASH *lh, BIO *out)
这个函数的作用是把哈希表使用的状态输出到BIO out中。实现在文件lh_stats.c中。
到此，OpenSSL中哈希表中如何实现的就说完了，至于哈希表是怎么用的，这里就不多说了。还有，就是使用时一些宏的用法，这里没有说，不过，在官方文档里，这一点还是比较详细的：http://openssl.org/docs/crypto/lhash.html。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/mm350670610/archive/2010/04/29/5542886.aspx