第四章 哈希表 / 4.2 哈希表数据结构

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

openssl中的哈希表数据结构在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;

本结构是一个单链表。其中,data用于存放数据地址,next为下一个数据地址,hash为数据哈希计算值。

 

typedef struct 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_nodesb分配空间的大小。

基本的结构如下示图: