/*-----------------------------------------------------------------------------
** hash.c**** Implementation of a simple Hash Table for string storage & retrieval**** Written by L. Rossman** Last Updated on 6/19/03**** The hash table data structure (HTable) is defined in "hash.h".** Interface Functions:** HTcreate() - creates a hash table** HTinsert() - inserts a string & its index value into a hash table** HTfind() - retrieves the index value of a string from a table** HTfree() - frees a hash table************************************************************************* NOTE: This is a modified version of the original HASH.C module.**********************************************************************//*-----------------------------------------------------------------------------
** 关于哈希表这一数据结构的介绍，可以参考博文：** ** ** 这里采用的哈希函数是Fletcher's checksum to compute 2-byte hash of string** 这里的哈希冲突解决方法是采用上述博文中的第3种方法“链地址法”** 将所有关键字为同义词的记录存储在同一线性链表中。该线性链表的定义在hash.h中的HTentry*/#include <malloc.h>
#include <string.h>#include "hash.h"/*
**--------------------------------------------------------------** 输入："ID标识"作为哈希函数的参数** 输出：哈希后的值** 作用：使用了Fletcher's checksum算法的哈希函数来处理32位长的字符串以获得散列值。**--------------------------------------------------------------*//* Use Fletcher's checksum to compute 2-byte hash of string */unsigned int hash(char *str){ unsigned int sum1= 0, check1; unsigned long sum2= 0L; while( '\0' != *str ) { sum1 += (*str); str++; if ( 255 <= sum1 ) sum1 -= 255; sum2 += sum1; } check1= sum2; check1 %= 255; check1= 255 - (sum1+check1) % 255; sum1= 255 - (sum1+check1) % 255; return( ( ( check1 << 8 ) | sum1 ) % HTMAXSIZE);}/*
**--------------------------------------------------------------** 输入：无** 输出：成功则返回哈希表头指针** 作用：创建一个长度为HTMAXSIZE的哈希表，并初始化 **--------------------------------------------------------------*/HTtable *HTcreate(){ int i; HTtable *ht = (HTtable *) calloc(HTMAXSIZE, sizeof(HTtable)); if (ht != NULL) for (i=0; i<HTMAXSIZE; i++) ht[i] = NULL;/* Comment by CCR: Here Can Be Better,the Reason is:calloc在动态分配完内存后，自动初始化该内存空间为零，而malloc不初始化，里边数据是随机的垃圾数据。所以这句可以注释掉 */ return(ht);}/*
**--------------------------------------------------------------** 输入：哈希表ht、"ID标识"key、Node中的索引值** 输出：成功插入返回1，否则返回0** 作用：将一个字符串以及索引值插入到哈希表中 **--------------------------------------------------------------*/int HTinsert(HTtable *ht, char *key, int data){ unsigned int i = hash(key); struct HTentry *entry; if ( i >= HTMAXSIZE ) return(0); entry = (struct HTentry *) malloc(sizeof(struct HTentry)); if (entry == NULL) return(0);//判断内存是否分配成功 entry->key = key; entry->data = data; //将同一hash值的链表挂到当前对象entry后面，再将当前对象entry置于队首 entry->next = ht[i]; ht[i] = entry; return(1);}/*
**--------------------------------------------------------------** 输入：哈希表、"ID标识" ** 输出：给出指定"ID标识"在Node中的索引值，若没找到返回0** 作用：返回指定"ID标识"在Node中的索引值 **--------------------------------------------------------------*/int HTfind(HTtable *ht, char *key){ unsigned int i = hash(key); struct HTentry *entry; if ( i >= HTMAXSIZE ) return(NOTFOUND); entry = ht[i]; while (entry != NULL) { //哈希冲突处理：链地址法 if (strcmp(entry->key,key) == 0 ) return(entry->data); entry = entry->next; } return(NOTFOUND);}/*
**--------------------------------------------------------------** 输入：哈希表、"ID标识"** 输出：寻找指定"ID标识"是否存在于哈希表中，若没找到返回NULL，找到则返回指向"ID标识"的指针** 作用：判断指定"ID标识"是否存在于哈希表中 **--------------------------------------------------------------*/char *HTfindKey(HTtable *ht, char *key){ unsigned int i = hash(key); struct HTentry *entry; if ( i >= HTMAXSIZE ) return(NULL); entry = ht[i]; while (entry != NULL) { if ( strcmp(entry->key,key) == 0 ) return(entry->key); entry = entry->next; } return(NULL);}/*
**--------------------------------------------------------------** 输入：哈希表** 输出：** 作用：回收哈希表的内存 **--------------------------------------------------------------*/void HTfree(HTtable *ht){ struct HTentry *entry, *nextentry; int i; for (i=0; i<HTMAXSIZE; i++) { entry = ht[i]; while (entry != NULL) { nextentry = entry->next; free(entry); entry = nextentry; } } free(ht);}--------------------------------------------------------
哈希表这一数据结构是用内存空间来提高时间效率的算法，理想情况下（不存在冲突）的哈希算法的时间复杂度是常数O（1）。但是实际情况是即便开辟了足够多的一连串的内存空间，如果哈希函数选取不当，还是会发生冲突。EPANET中的哈希函数的选取是使用了Fletcher's checksum算法的哈希函数来处理32位长的字符串以获得散列值，这个哈希算法的优劣本人还无法去评断。但是注意，EPANET中的冲突处理是采用链地址法，而EPANET中默认提供的哈希地址个数是HTMAXSIZE个，在hash.h中是这样定义的#define HTMAXSIZE 1999。如果我们的模型有5W个左右的节点与管段，那么这2000个地址空间，平均每个地址空间会挂有一个长度为25的线性链表。而哈希函数算法不一定这么优秀，可能某个地址空间挂了一个长度为上百甚至上千的线性链表，那么查询效率就低下了。所以，如果运行EPANET的机子有足够多的内存，比如8G以上，那么就可以试着修改hash.h中的#define HTMAXSIZE 1999。将整个1999改的大些，那么运行效率也就可以提高了。