openssl哈希表

r囧r小猫 2022-05-11 22:20 184阅读 0赞

**一 哈希表**

在一般的数据结构如线性表和树中，记录在结构中的相对位置是与记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列的关键字比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。在查找时，只需根据这个对应关系找到给定值。这种对应关系既是哈希函数，按这个思想建立的表为哈希表。

哈希表存在冲突现象：不同的关键字可能得到同一哈希地址。在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。

**二 哈希表数据结构**

openssl函数使用哈希表来加快查询操作，并能存放任意形式的数据，比如配置文件的读取、内存分配中被分配内存的信息等。其源码在crypto/lhash目录下。

openssl中的哈希表数据结构在lhash.h中定义。

1.      typedef struct lhash_node_st
        {
            void *data;
            struct lhash_node_st *next;
        #ifndef OPENSSL_NO_HASH_COMP
            unsigned long hash;
        #endif
        }LHASH_NODE;

本结构是一个单链表。

data：用于存放数据地址。

next：为下一个数据地址。

hash：为数据哈希计算值。

typedefstruct lhash_st
    {
    	LHASH_NODE **b;
     	LHASH_COMP_FN_TYPE comp;
     	LHASH_HASH_FN_TYPE hash;
    	unsigned	int num_nodes;
    	unsigned	int num_alloc_nodes;
    	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;

b指针数组用于存放所有的数据，数组中的每一个值为数据链表的头指针。

comp用于存放数据比较函数地址。

hash用于存放计算哈希值函数的地址。

num\_nodes为链表个数。

num\_alloc\_nodes为b分配空间的大小。

![966b531a-5af2-3d9b-838e-f48a59196405.png][]

**三 哈希函数说明**

1、LHASH \*lh\_new(LHASH\_HASH\_FN\_TYPE h, LHASH\_COMP\_FN\_TYPE c)

功能：生成哈希表

源文件：lhash.c

说明：输入参数h为哈希函数，c为比较函数。这两个函数都是回调函数。因为哈希表用于存放任意的数据结构，哈希表存放、查询、删除等操作都需要比较数据和进行哈希运算，而哈希表不知道用户数据如何进行比较，也不知道用户数据结构中需要对哪些关键项进行散列运算。所以，用户必须提供这两个回调函数。

2、void \*lh\_delete(LHASH \*lh, const void \*data)

源文件：lhash.c

功能：删除散列表中的一个数据

说明：data为数据结构指针。

3、void lh\_doall(LHASH \*lh, LHASH\_DOALL\_FN\_TYPE func)

源文件：lhash.c

功能：处理哈希表中的所有数据

说明：func为外部提供的回调函数，本函数遍历所有存储在哈希表中的数据，每个数据被func处理。

4、void lh\_doall\_arg(LHASH \*lh, LHASH\_DOALL\_ARG\_FN\_TYPE func, void \*arg)

源文件：lhash.c

功能：处理哈希表中所有数据

说明：此参数类似于lh\_doall函数，func为外部提供的回调函数，arg为传递给func函数的参数。本函数遍历所有存储在哈希表中的数据，每个数据被func处理。

5、void lh\_free(LHASH \*lh)

源文件：lhash.c

功能：释放哈希表。

6、void \*lh\_insert(LHASH \*lh, void \*data)

源文件：lhash.c

功能：往哈希表中添加数据。

说明：data为需要添加数据结构的指针地址。

7、void \*lh\_retrieve(LHASH \*lh, const void \*data)

源文件：lhash.c

功能：查询数据。

说明：从哈希表中查询数据，data为数据结构地址，此数据结构中必须提供关键项(这些关键项对应于用户提供的哈希函数和比较函数)以供查询，如果查询成功，返回数据结构的地址，否则返回NULL。比如SSL握手中服务端查询以前存储的SESSION时，它需要提供其中关键的几项。

SSL\_SESSION \*ret=NULL,data;

data.ssl\_version=s->version;

data.session\_id\_length=len;

memcpy(data.session\_id,session\_id,len);

ret=(SSL\_SESSION \*)lh\_retrieve(s->ctx->sessions,&data);

8、void lh\_node\_stats\_bio(const LHASH \*lh, BIO \*out)

源文件：lh\_stats.c

功能：将哈希表中每个链表下的数据状态输出到BIO中。

9、void lh\_node\_stats(const LHASH \*lh, FILE \*fp)

源文件：lh\_stats.c

功能：将哈希表中每个链表下数据到输出到FILE中。

说明：此函数调用了lh\_node\_stats\_bio函数。

10、void lh\_node\_usage\_stats\_bio(const LHASH \*lh, BIO \*out)

源文件：lh\_stats.c

功能：将哈希表的使用状态输出到BIO中。

11、void lh\_node\_usage\_stats(const LHASH \*lh, FILE \*fp)

源文件：lh\_stats.c

功能：将哈希表的使用状态输出到FILE中。

说明：此函数调用了lh\_node\_usage\_stats\_bio函数

12、unsigned long lh\_num\_items(const LHASH \*lh)

源文件：lhash.c

功能：获取哈希表中元素的个数。

13、void lh\_stats\_bio(const LHASH \*lh, BIO \*out)

源文件：lh\_stats.c

功能：输出哈希表统计信息到BIO中。

14、void lh\_stats(const LHASH \*lh, FILE \*fp)

源文件：lh\_stats.c

功能：打印哈希表的统计信息，此函数调用了lh\_stats\_bio。

15、unsigned long lh\_strhash(const char \*c)

源文件：lhash.c

**四 实例**

1.  `#include<string.h>`
2.  `#include<openssl/lhash.h>`
3.  ``
4.  `typedefstructStudent_st`
5.  `{`
6.  `char name[20];`
7.  `int age;`
8.  `char otherInfo[200];`
9.  `}Student;`
10. ``
11. `staticintStudent_cmp(constvoid*a,constvoid*b)`
12. `{`
13. `char*namea=((Student*)a)->name;`
14. `char*nameb=((Student*)b)->name;`
15. `return strcmp(namea,nameb);`
16. `}`
17. ``
18. `/* 打印每个值*/`
19. `staticvoidPrintValue(Student*a)`
20. `{`
21. `printf("name :%s\n",a->name);`
22. `printf("age :%d\n",a->age);`
23. `printf("otherInfo : %s\n",a->otherInfo);`
24. `}`
25. ``
26. `staticvoidPrintValue_arg(Student*a,void*b)`
27. `{`
28. `int flag=0;`
29. ``
30. `flag=*(int*)b;`
31. `printf("用户输入参数为:%d\n",flag);`
32. `printf("name :%s\n",a->name);`
33. `printf("age :%d\n",a->age);`
34. `printf("otherInfo : %s\n",a->otherInfo);`
35. `}`
36. ``
37. `int main()`
38. `{`
39. `int flag=11;`
40. `_LHASH *h;`
41. `Student s1={ "zcp",28,"hu bei"},`
42. `s2={ "forxy",28,"no info"},`
43. `s3={ "skp",24,"student"},`
44. `s4={ "zhao_zcp",28,"zcp's name"},`
45. `*s5;`
46. `void*data;`
47. ``
48. `/*创建哈希表*/`
49. `h=lh_new(NULL,Student_cmp);`
50. `if(h==NULL)`
51. `{`
52. `printf("err.\n");`
53. `return-1;`
54. `}`
55. `/*将数据插入哈希表*/`
56. `data=&s1;`
57. `lh_insert(h,data);`
58. `data=&s2;`
59. `lh_insert(h,data);`
60. `data=&s3;`
61. `lh_insert(h,data);`
62. `data=&s4;`
63. `lh_insert(h,data);`
64. ``
65. `/*遍历打印*/`
66. `lh_doall(h,PrintValue);`
67. `lh_doall_arg(h,PrintValue_arg,(void*)(&flag));`
68. ``
69. `/*查找数据*/`
70. `data=lh_retrieve(h,(constvoid*)"skp");`
71. `if(data==NULL)`
72. `{`
73. `printf("can not find skp!\n");`
74. `lh_free(h);`
75. `return-1;`
76. `}`
77. `else`
78. `{`
79. `s5=data;`
80. `printf("\n\nstudent name : %s\n",s5->name);`
81. `printf("sutdent age : %d\n",s5->age);`
82. `printf("student otherinfo : %s\n",s5->otherInfo);`
83. `lh_free(h);`
84. `}`
85. ``
86. `getchar();`
87. `return0;`
88. `}`

编译与运行

1.  `[root@localhost ~]# cd /`
2.  `[root@localhost /]# cd openssl-1.1.0c/test`
3.  `[root@localhost test]# gcc example2.c -o example2 -L/usr/lib -lssl -lcrypto`
4.  `[root@localhost test]# ./example2 name :zhao_zcp age :28 otherInfo : zcp's name name :skp age :24 otherInfo : student name :forxy age :28 otherInfo : no info name :zcp age :28 otherInfo : hu bei 用户输入参数为:11 name :zhao_zcp age :28 otherInfo : zcp's name 用户输入参数为:11 name :skp age :24 otherInfo : student 用户输入参数为:11 name :forxy age :28 otherInfo : no info 用户输入参数为:11 name :zcp age :28 otherInfo : hu bei student name : skp sutdent age : 24 student otherinfo : student`

[966b531a-5af2-3d9b-838e-f48a59196405.png]: /images/20220512/c109e12ed25e4674838a563af34fb577.png