211.哈希表实现活期储蓄账目管理系统

  • 时间:
  • 浏览:0

摘要:随着社会发展,统统人 的生活水平不断提高,会将一定的收入用于活期存储,因其储户开户、销户、存入、支出活动频繁的需求特点,本课程设计使用哈希表进行银行活期储蓄账目管理系统的模拟,实现基本的数据存储和处里操作。

关键词管理系统;哈希表;数据形态学

1.1那先 的疑问描述

  活期储蓄帐目管理,活期储蓄处里中,储户开户、销户、存入、支出活动频繁,系统设计要求:1)能比较太快地找到储户的帐户,以实现存款、取款记账;2)能比较简单,太快地实现插入和删除,以实现开户和销户的时需。

1.2模块组成

伪UI模块:伪界面,为了使界面美观设计的伪UI

主程序池池模块:初始化工作及功能选着和调用

开户模块:要求能新建账户因此 不能进一步对所建立的账户进行设置开户金额等操作。

销户模块:查找到目的账户,对其销户。

查询模块:不能通过账号查找,太快的找到要查找的账户,并显示账户余额。

存取模块:在太快地查找到目的账户后,对账户余额进行修改。

测试模块:超级管理员不能模拟输入数据,并输出删剪数据

1.3 功能要求

根据1.2模块组成该系统具有以下一三个次责的功能:

开户功能:不能从键盘输入用户账户新建账户,并对其进行进行设置初始开户金额。

销户功能:查找到目的账户,若余额为0则对其销户,因此 提示先取钱再销户。

查询功能:不能通过账号查找,太快的找到要查找的账户,并显示账户余额。

存取功能:在太快地查找到目的账户后,对账户进行存钱取钱操作。

测试功能:不能通过管理员预设密码进行,模拟输入,删剪输出操作,以方便测试。

2.1 设计思路

  每另有一三个用户看作另有一三个基本单位,将系统抽象只包括账号和金额,密码、日期等不做存储和处里。为了便于后期维护与找错,使形态学 更加明了,采用数据形态学 型函数与功能实现型函数分离形态学 ,存储数据形态学 是哈希表。

图1 数据形态学 型函数和功能实现型函数

2.2 存储形态学 设计

  数据形态学 存储采用的是哈希表,账号存储为字符串,常用字符串哈希函数有 BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash、ELFHash等,本程序池池采用 BKDRHash对字符串进行散列,得到另有一三个整数的hash值,根据得到的hash值选着另有一三个槽位置,处里冲突办法 为链接法,如图3哈希表插入过程。其中零号元素位用于存储哈希表主槽位容积,非所有元素容积,如图2哈希表存储模型。

 

图2 哈希表存储模型

 

图3 哈希表插入过程

2.3 算法设计说明

下面将从函数调用关系和对次责算法设计说明另有一三个方面进行

2.3.1 函数调用关系

图4 函数调用关系

2.3.2 算法设计说明

  哈希表初始化算法思想是,为哈希表主槽申请空间并置为0,第0个元素的值域用于存放哈希表主槽长度。

  判断哈希值所在哈希表槽位的思想是,将字符串用BKDR算法散列成另有一三个整数哈希值,用该整数哈希值对长度取余加1一定落在哈希表主槽槽位数组内,其中加1是为了处里落在0位,如果 0位用于存储长度。

  哈希表插入元素的思想是,结合图3,先求插入值的主槽,主槽占据 该元素则直接更新值域,如果 主槽删剪时会该元素,则冲突处里,本程序池池用链接法,查看主槽冲突指针域,重复上述过程,即找主槽,因此 遍历主槽冲突链,占据 就更新,不占据 就插入。

  哈希表删除元素的思想与插入元素的思想较为类式,将对应插入改成删除。

  哈希表搜索的思想是,先求要搜索值的哈希值,再利用判断哈希值所在哈希表槽位的算法找到该槽位,对比该槽位元素查看否有一致,一致则查找成功,不一样则看该槽位否有有冲突元素,有搞笑的话则对比该槽位元素否有一致,那末 搞笑的话则不占据 该元素,查找失败。

 

图5 哈希表查找流程图

  返回删剪数据元素个数的思想为,遍历主槽,如果 主槽后面 有冲突链则遍历冲突链。

  打印删剪元素的思想与返回删剪元素思想类式,先主槽,并查看否有有冲突链。

3.1 形态学 体定义

根据2.2存储形态学 设计,哈希表形态学 体的定义为:

typedef struct _htItem{

    struct _htItem  *next;//冲突时下另有一三个

    char *key_string;//

    uint fid;//卫星值

} htItem;

3.2 功能型函数

开户、销户等功能型函数较为简单,在此不做说明,其中存取函数利用哈希表形态学 ,删剪时会找到该元素直接更改卫星值值域,却说取出值域中的卫星值经过处里后,重新插入该元素,代码如下:

        scanf("%d",&moneyAD);

        htItem *tmp = htGet(spAD, ht);

        moneyAD = moneyAD  +  (tmp->fid);

        htSet(spAD, moneyAD, ht);

3.3 数据形态学 型函数

3.3.1 初始化函数

根据2.3.2哈希表初始化思想,初始化函数如下:

//初始化HashTable

void htInit(htItem **ht, uint length){

    int i;

    for (i = 0; i<length; i++){

        ht[i] = (htItem*)malloc(sizeof(htItem));

        memset(ht[i], 0, sizeof(htItem));//用来对一段内存空间删剪设置为某个字符

    }

    ht[0]->fid = length;//第另有一三个存长度

}

3.3.2 判断哈希值所在哈希表槽位

根据2.3.2判断哈希值所在哈希表槽位的思想,代码如下:

// get the index of hash table  根据得到的hash值选着另有一三个槽位置
uint htIndex(char *key, htItem **ht){
    uint hashedKey = bkdrHash(key);
    uint length = (ht[0]->fid - 1);
    return (uint)hashedKey % length + 1;    //char转整数哈希值再用哈希函数定位槽位
    //0号位存长度,对长度取余加1,一定落在槽位内
}

其中bkdrHash(key)函数为:

uint bkdrHash(char *key){
    uint seed = 131;
    uint hash = 0;
    while (*key != '\n' && *key != 0){
            //通常使用时,判别条件为*key != 0即可,此处的*key != '\n'是因程序池池时需
        hash = hash * seed + (*key++);
    }
    return (hash & 0x7FFFFFFF);
}

3.3.3 哈希表插入元素与删除元素

根据2.3.2哈希表插入元素与删除元素算法思想,以插入为例代码如下:

uint htSet(char *key, uint fid, htItem **ht){
    uint i = htIndex(key, ht);
    htItem *item = ht[i];
    while (item->next){
    //如果
占据

搞笑的话则直接更新值
        if (strcmp(key, item->next->key_string) == 0){
            item->next->fid = fid;
            return 0;
        }else{
            item = item->next;
        }
    }
    //处里冲突元素
    item->next = (htItem*)malloc(sizeof(htItem));
    item->next->fid = fid;
    item->next->key_string = key;
    item->next->next = NULL;
    return 0;
}

3.3.4 哈希表查找元素

根据2.3.2哈希表查找元素思想,代码如下:

//get hashTable elements 进行对应的hash值的搜索,如果
找到则返回该节点
htItem* htGet(char *key, htItem **ht){
    uint i = htIndex(key, ht);
    htItem *item = ht[i]->next;
    htItem *tmp = (htItem*)malloc(sizeof(htItem));
    memset(tmp, 0, sizeof(htItem));//  内存空间初始化 
    while (item){
        if (strcmp(key, item->key_string) == 0){
            return item;
            tmp->fid = item->fid;
            tmp->key_string = item->key_string;
            return tmp;// 返回地址
        }
        item = item->next;
    }
    return NULL;
}

3.3.5 返回所有元素个数与打印删剪元素

根据2.3.2哈希表计算所有元素思想和打印所有元素思想,以计算所有元素个数为例,代码如下:

// get element number in the hashtable 所有元素总和个数
//遍历所有槽位和对应槽位冲突的元素
uint htLen(htItem **ht){
    uint alength = ht[0]->fid;
    uint i, length = 0;
    for (i = 1; i < alength; i++){
        if (ht[i]->next)
            length++;
    }
    return length;
}

4.1 测试数据

图6 测试

  测试开户20190019开户金额为666666,并查询,输出金额为666666,结果正确,存取功能,存1元,查询余额为666667,取666667,余额为0,销户后,查询用户不占据 ,统统异常提示等功能因篇幅所限没哟此贴图。

  利用测试模块,功能选着输入未在列表中展示的54321,超级管理员密码为54321,自动模拟输入120个数据,其中哈希表主槽位120,一定产生冲突,因此 再功能选着输入未在列表中展示的12345,超级管理员密码为12345,展示所有元素,显示数据为120条,结果正确。

4.2 调试与分析

  那先 的疑问1 :最结束了了申请内存为sp=(char *)malloc(sizeof(char)); 人太好达到可变空间的目的,因此 考虑到不安全,实际申请另有一三个char空间, 统统空间不一定没用,和char *p;直接用赋值是一样的错误,那先 的疑问1应改为sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));其中ACCOUNT_NUM可用define预设。

  那先 的疑问2:for{ scanf(sp); htSet(sp, tempmoney, item);}未申请空间,无论输入多少删剪时会另有一三个记录,结合那先 的疑问1,如果 没用申请空间,统统所有元素都覆盖在另有一三个未知空间,那先 的疑问2应在循环中加入申请空间。

  那先 的疑问3:do{scanf("%d", &funChoose); switch(funChoose){};}while{}输入另有一三个数字非法字符,显示非法输入,正确;输入另有一三个字母,就死循环,通过询问别人,加个getchar();吸收字符,处里;发现输入另有一三个字符串就会空出字符串长度个循环,那先 的疑问3应为while(getchar() != '\n');

时间繁复度为O(1),统统调试那先 的疑问因篇幅所限就没哟此一一列出,多数错误产生的愿因如果 对C语言理解严重不足透彻。通过查阅书籍笔记,和讨论删剪时会所处里。

4.3 算法改进

  算法中并未加入载荷因子,下一步改进可从数据形态学 方面,加入载荷因子,实现自动扩容,提高厚度。

  程序池池用C语言编写,并未涉及对文件的操作,所有存储均在内存进行,仅体现形态学 思想,下一步从C语言方面,可添加文件映射,提高实用性。

  通过本次课程设计,对哈希表及数据形态学 这门课有了更进一步的理解,哈希表本质是另有一三个数组,如果 说数组是特殊的哈希表,哈希表最重要的次责是咋样散列,本设计是用已有技术调用BKDRHash字符串散列,并未有当事人实际创新算法。最结束了了想用Java实现,时需直接调用已有函数,根据课程要求,提交为.c文件,应该用C语言,感觉有种重复造轮子的感觉,如果 实际编写时,查询对字符串散列的函数,发现有另有一三个题为“HashMap在Java1.7与1.8中的区别的”博客,在Java1.8中使用另有一三个Node数组来存储数据,统统Node如果 是链表形态学 ,也如果 是红黑树形态学 ,在Java1.7中是链表形态学 ,向HashMap中put/get 1w条hashcode相同的对象JDK1.7: put 0.26s,get 0.55s,JDK1.8(未实现Compare接口):put 0.92s,get 2.1s;80W条hashcode相同的对象JDK1.8(正人太好现Compare接口,):put/get最少开销删剪时会320ms左右,结论是处里Hash Collision DoS攻击。因此 想到最初重复造轮子的想法,底层的改变带来的影响是巨大的,好在Java目前还是开源的,我希望如果 闭源,如果 有看似非常好的闭源语言如果 框架,盲目的直接调用,拿来主义,之时会产生不可计量的后果,因此 底层的技术是统统取代不了的,数据形态学 和算法等基础课程更像是厚度课程,归根到底还是数学,因此 底层基础技术的学习是必要且重要的。

[1]严蔚敏,李冬梅,吴伟民.数据形态学 (C语言版)[J].计算机教育,2012(12):62.

[2]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,殷建平,徐云,王刚,刘晓光,苏明,邹恒明,王宏志.算法导论(原书第3版)[J].计算机教育,2013(10):51.

[3] wiki.《Hash table》.

https://en.wikipedia.org/wiki/Hash_table.2019年5月20访问

[4]Mr.Wang.《HashMap 在 Java1.7 与 1.8 中的区别》.

https://www.cnblogs.com/justlove/p/7624455.html.2019年5月20访问

[5]灵剑.《hash算法的数学原理是那先 ,咋样保证尽如果 少的碰撞?》.

https://www.zhihu.com/question/20807188.2019年5月20访问

  1 /*
  2     作者:
  3         赵忠瑞
  4         
  5     功能:
  6         哈希表实现活期储蓄帐目管理
  7         
  8     具体要求:    
  9         数据形态学

课程设计  选题19. 活期储蓄帐目管理(限1 人完成) 哈希表
 10            活期储蓄处里中,储户开户、销户、存入、支出活动频繁,系统设计要求:
 11             1)能比较太快地找到储户的帐户,以实现存款、取款记账;
 12             2)能比较简单,太快地实现插入和删除,以实现开户和销户的时需。 
 13             
 14     文件脉络:
 15         part1  头文件及形态学

体定义
 16         part2  函数声明 
 17                      数据形态学

型函数声明 
 18                      功能实现型函数声明 
 19         part3    main函数 
 20         part4    功能实现型函数        
 21         part5    数据形态学

型函数  
 22 */ 
 23 
 24 
 25 //———————part1——————————————
 26 #include <stdio.h>
 27 #include <stdlib.h>
 28 #include <memory.h>
 29 #include <string.h>
 80 #define ACCOUNT_NUM  16  //账号位数 
 31 
 32 typedef unsigned int uint;
 33 //哈希表元素
 34 typedef struct _htItem{
 35     struct _htItem  *next;//冲突时下另有一三个 
 36     char *key_string;//
 37     uint fid;//卫星值 
 38 } htItem;
 39 
 40 
 41 //————————part2—————————————
 42 //---------下面是数据形态学

型函数声明------------- 
 43 void htInit(htItem **ht, uint length);// 构造函数,申请哈希表的空间
 44 uint htSet(char *key, uint val, htItem **ht);//向哈希表中插入另有一三个值
 45 htItem* htGet(char *key, htItem **ht);//从哈希表中获得另有一三个对应的key
 46 int htDel(char *key, htItem **ht);//从哈希表中删除另有一三个key
 47 uint bkdrHash(char *key);//对string进行散列得到另有一三个整数值
 48 uint htIndex(char *key, htItem **ht);//根据key计算另有一三个整数值,因此


获得对应的槽位索引
 49 uint htLen(htItem **ht);//求哈希表元素数
 80 void print_hashTable(htItem **ht);//打印哈希表,测试
 51 //-------下面是功能实现型函数声明--------- 
 52 void funFakeUI();//伪界面,为了使界面美观设计的伪UI
 53 int funOpenAccount(htItem **ht);//开户函数
 54 int funDelAccount(htItem **ht);//销户函数
 55 int funAddDelMoney(htItem **ht);//存款取款的流水操作
 56 int funSearch(htItem **ht);//查询余额操作
 57 int funTestDisplay(htItem **ht);//超级管理员测试,打印所有数据 
 58 int funTestInput(htItem **ht);//超级管理员测试,模拟输入数据120个数据,一定冲突
 59 
 80  
 61 //———————part3——————————————
 62 int main(void){
 63     htItem *item[101];
 64     htInit(item, 101);//初始化
 65     int funChoose = 0;
 66     funFakeUI();//伪UI 
 67     do{
 68         printf("\n\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
 69         printf("\n\t请选着功能:1开户 2销户 3存取 4查询 5退出\n\t功能选着:  ");
 70         funChoose = 0;
 71         scanf("%d", &funChoose);
 72     //    getchar();    //吸收单个字符 
 73         while(getchar() != '\n'); //吸收字符串非法字符,因此


死循环 
 74         switch(funChoose){
 75             case 1:
 76                 funOpenAccount(item);
 77                 break;
 78             case 2:
 79                 funDelAccount(item);
 80                 break;
 81             case 3:
 82                 funAddDelMoney(item);
 83                 break; 
 84             case 4:
 85                 funSearch(item);
 86                 break;
 87             case 5:
 88                 printf("\n\t欢迎再次使用!\n");
 89                 return 0;
 90             case 54321://测试项,模拟输入120个数据,一定冲突 
 91                 funTestInput(item);
 92                 break; 
 93             case 12345://测试项,展示所有数据 
 94                 funTestDisplay(item);
 95                 break;
 96             default:
 97                 printf("\n\t非法操作!");
 98         } 
 99     }while(funChoose != 5);
80 }    
101 
102 
103 //——————part4 功能实现型函数———————————
104 /*******************************/ 
105 //伪UI 
106 void funFakeUI(){
107     printf("\n\n----------------欢迎使用活期储蓄帐目管理模拟程序池池----------------\n");//more to develop
108 }
109 
110 /********************************/ 
111 //开户 
112 int funOpenAccount(htItem **ht){
113     //printf("fun  开户 begin\n");
114     int iAccountAdd,iAccountAddSum;
115     printf("\n\n\t请输入预开户账号总数\n\t本次开户总数:");
116     scanf("%d",&iAccountAddSum);
117     for(iAccountAdd=0; iAccountAdd<iAccountAddSum; iAccountAdd++) { 
118         printf("\n\t\t请输入预开户%d的账号和开户金额:\n",iAccountAdd+1);
119         char *sp;
120         sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));
121         int tempmoney;
122         printf("\t\t预开户账号:");
123         scanf("%s",sp);
124         if (htGet(sp, ht)){
125             //检查账户否有占据

 
126             printf("\t\t该账户已占据

!\n\t\t------------------------------"); 
127             continue;
128             //break;
129             //return 0; 
180         } 
131         printf("\t\t开户金额:  ");
132         scanf("%d",&tempmoney);
133         htSet(sp, tempmoney, ht);
134         printf("\t\t开户完成!\n\t\t------------------------------");
135     } 
136 //    printf("\t系统所有开户信息为:\n");
137 //    print_hashTable(ht);    
138 //    printf("fun  开户 end\n\n\n");    
139 }
140 
141 
142 /*******************************/ 
143 //销户 
144 int funDelAccount(htItem **ht){
145 //    printf("fun  销户 begin\n");
146     int iAccountDel,iAccountDelSum;
147     printf("\n\t请输入本次销户账号总数:\n\t销户总数:");
148     scanf("%d",&iAccountDelSum);
149     printf("\n\t感情的搞笑的话提示,谨慎操作!\n\n");
80     for(iAccountDel=0; iAccountDel<iAccountDelSum; iAccountDel++) {     
151         printf("\n\t\t请输入预销户%d的账号:\n",iAccountDel+1);
152         char *sp;
153         sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));
154         int tempmoney;
155         printf("\t\t预销户账号:");
156         scanf("%s",sp);
157         htItem *tmp;
158         if ( tmp = htGet(sp, ht)){
159             if(tmp->fid)
180                 printf("\t\t用户 %s 的余额为 %d ,非空,取出余额再确认销户\n", tmp->key_string, tmp->fid);
161             else{
162                 htDel(sp, ht);
163                 free(sp);
164                 printf("\t\t销户成功!\n");
165             } 
166         }
167         else
168             printf("\t\t那末

此用户! 请确认信息重新操作\n");
169         printf("\t\t-----------------------------------------\n");
170     } 
171     //    printf("\t系统所有开户信息为:\n");
172     //    print_hashTable(ht);    
173     //printf("fun  销户 end\n\n\n");    
174 }
175 
176 
177 /**********************************/ 
178 //存取流水 
179 int funAddDelMoney(htItem **ht){
180     //printf("fun  流水 begin\n\n\n");    
181     printf("\n\t请输入预存取的账号: ");
182     char *spAD;
183     spAD=(char *)malloc(ACCOUNT_NUM*sizeof(char));
184     scanf("%s",spAD);
185     //htItem *tmpTestNull; 
186     if (!htGet(spAD, ht)){
187         printf("\t那末

此用户! 请确认信息重新操作\n");
188         return 0;
189     }
190     printf("\t请输入流水类型:1存款 2取款\n\t流水类型: ") ;
191     int ADkind;
192     scanf("%d", &ADkind);
193     printf("\t请输入存取的金额:");
194     int moneyAD = 0;
195     scanf("%d",&moneyAD);
196     htItem *tmp = htGet(spAD, ht);
197     switch(ADkind){
198         case 1: 
199             moneyAD = moneyAD +  (tmp->fid);
80             htSet(spAD, moneyAD, ht);
201             printf("\t存款成功\n");
202             break;
203         case 2: 
204             if((moneyAD = (tmp->fid) - moneyAD) >= 0){
205                     htSet(spAD, moneyAD, ht);
206                     printf("\t取款成功\n");
207             }else
208                 printf("\t余额严重不足\n");
209             break;
210         default: 
211             printf("\t非法输入\n");
212             return 0;
213     }
214 //    printf("系统所有开户信息为:\n");
215 //    print_hashTable(ht);    
216 }
217 
218 /****************************/ 
219 //查询 
220 int funSearch(htItem **ht){
221     printf("\n\t请输入要查询的账号:");
222         char *sp;
223         sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));
224         scanf("%s",sp);
225         htItem *tmp; 
226         if ( tmp = htGet(sp, ht)){
227             if(tmp->fid)
228                 printf("\t用户 %s 的余额为 %d \n", tmp->key_string, tmp->fid);
229             else{
280                 printf("\t账户有误\n");
231             } 
232         }
233         else
234             printf("\t那末

此用户! 请确认信息重新操作\n");
235 }
236 
237 /****************************/ 
238 //超级管理员测试,打印所有数据
239 int funTestDisplay(htItem **ht){
240     printf("\n\t\t######################################\n\n\t\t{ 请输入超级管理员密码 }\t") ;
241     int pw;
242     scanf("%d", &pw);
243     while(getchar() != '\n'); //吸收非法字符串 
244     if(pw == 12345)
245         print_hashTable(ht);
246     //return 0;
247     printf("\n\t\t######################################\n") ;
248 }
249 
280 //超级管理员测试,模拟输入120个数据时会产生冲突
251 int funTestInput(htItem **ht){
252     printf("\n\t\t######################################\n\n\t\t{ 请输入超级管理员密码 }\t") ;
253     int pw;
254     scanf("%d", &pw);
255     while(getchar() != '\n'); //吸收非法字符串 
256     if(pw == 54321){
257     //模拟输入120个数据———————————————————————————————————————— 
258         int iinput = 0;
259         for(iinput=0; iinput<120; iinput++){
280             char *sp;
261             sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));
262             int account = 20190000 + iinput; //模拟账号 
263             ltoa(account,sp,10);
264             //  将长整型值转换为字符串  
265             //char *__cdecl ltoa(long _Val,char *_DstBuf,int _Radix) __MINGW_ATTRIB_DEPRECATED_MSVC805;
266             htSet(sp, iinput, ht);
267         } 
268         printf("\n\t\t模拟输入完成\n");
269     }
270     printf("\n\t\t######################################\n") ;
271 }
272 
273 
274 
275 //————————part5 数据形态学

型函数————————————————————————————————/ 
276 /***************************/ 
277 //初始化HashTable
278 void htInit(htItem **ht, uint length){
279     int i;
280     for (i = 0; i<length; i++){
281         ht[i] = (htItem*)malloc(sizeof(htItem));
282         memset(ht[i], 0, sizeof(htItem));//用来对一段内存空间删剪设置为某个字符
283     }
284     ht[0]->fid = length;//第另有一三个存长度 
285 }
286 
287 /******************************/ 
288 //get hashTable elements 进行对应的hash值的搜索,如果
找到则返回该节点
289 htItem* htGet(char *key, htItem **ht){
290     uint i = htIndex(key, ht);
291     htItem *item = ht[i]->next;
292     htItem *tmp = (htItem*)malloc(sizeof(htItem));
293     memset(tmp, 0, sizeof(htItem));//  内存空间初始化  
294     while (item){
295         if (strcmp(key, item->key_string) == 0){
296             return item;
297             tmp->fid = item->fid;
298             tmp->key_string = item->key_string;
299             return tmp;// 返回地址 
80         }
801         item = item->next;
802     }
803     return NULL;
804 }
805 
806 /*****************************/ 
807 // set hashTable element 插入新的hash值
808 uint htSet(char *key, uint fid, htItem **ht){
809     uint i = htIndex(key, ht);
310     htItem *item = ht[i];
311     while (item->next){
312     //如果
占据

搞笑的话则直接更新值
313         if (strcmp(key, item->next->key_string) == 0){
314             item->next->fid = fid;
315             return 0;
316         }else{
317             item = item->next;
318         }
319     }
320     //处里冲突元素 
321     item->next = (htItem*)malloc(sizeof(htItem));
322     item->next->fid = fid;
323     item->next->key_string = key;
324     item->next->next = NULL;
325     return 0;
326 }
327 
328 /******************************/ 
329 // delete one element of hashtable  删除hash值
380 int htDel(char *key, htItem **ht){
331     uint i = htIndex(key, ht);
332     htItem *item = ht[i];
333     while (item->next){
334         if (strcmp(key, item->next->key_string) == 0){
335             htItem *tmp = item->next;
336             item->next = tmp->next;
337             free(tmp);
338             return 0;
339         }
340         item = item->next;
341     }
342     return -1;
343 }
344 
345 /********************************/ 
346 //常用字符串哈希函数有 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等, 
347 // 本程序池池采用 BKDR hash function  对字符串进行散列,得到另有一三个整数的hash值 
348 uint bkdrHash(char *key){
349     uint seed = 131;
380     uint hash = 0;
351     while (*key != '\n' && *key != 0){
352         //通常使用时,判别条件为*key != 0即可,此处的*key != '\n'是因程序池池时需 
353         hash = hash * seed + (*key++);
354     }
355     return (hash & 0x7FFFFFFF);
356 }
357 
358 /******************************/ 
359 // get the index of hash table  根据得到的hash值选着另有一三个槽位置
380 uint htIndex(char *key, htItem **ht){
361     uint hashedKey = bkdrHash(key);
362     uint length = (ht[0]->fid - 1);
363     return (uint)hashedKey % length + 1;    //char转整数哈希值再用哈希函数定位槽位 
364     //0号位存长度,对长度取余加1,一定落在槽位内 
365 }
366 
367 /******************************/ 
368 // get element number in the hashtable 所有元素总和个数 
369 //遍历所有槽位和对应槽位冲突的元素 
370 uint htLen(htItem **ht){
371     uint alength = ht[0]->fid;
372     uint i, length = 0;
373     for (i = 1; i < alength; i++){
374         if (ht[i]->next) {
375             length++;
376         }
377     }
378     return length;
379 }
380 
381 /**************************/ 
382 // get capacity of hashtable 哈希表主槽容积
383 uint htCapacity(htItem **ht){
384     return ht[0]->fid;
385 }
386 
387 
388 /****************************/ 
389 //print hashTable  打印哈希表     *用于测试 
390 void print_hashTable(htItem **ht){
391     uint length = ht[0]->fid;
392     uint i;
393     htItem *item;
394     printf("\n\t\t哈希表所有数据:\n");
395 /*    1.遍历主槽,
396     2.主槽为null时遍历下另有一三个主槽,
397     3.主槽不为null时,打印该元素
398     4.检查该元素否有占据

冲突元素,即该元素的指针域否有为null 
399     5.重复1-4 
80 */ 
401     for (i = 1; i < length; i++){
402         item = ht[i]->next;
403         while (item){
404             printf("\t\t%s --> %d\n", item->key_string, item->fid);
405             item = item->next;
406         }
407     }
408 }
409 
410 
411 //————————文件结束了了—————————
412 
413 
414 
415 /*统统参考     
416             https://en.wikipedia.org/wiki/Hash_table
417             https://github.com/utx201777/Daily
418             https://www.cnblogs.com/heyonggang/p/3419574.html
419             https://www.cnblogs.com/justlove/p/7624455.html
420             https://cloud.tencent.com/developer/article/1092226
421             https://www.cnblogs.com/liuliuliu/p/3966851.html
422             https://www.cnblogs.com/stevenczp/p/7028071.html
423             http://www.partow.net/programming/hashfunctions/#AvailableHashFunctions
424             https://blog.csdn.net/cy_tec/article/details/51202140
425             https://blog.csdn.net/fcbarcelonalove/article/details/84578418
426             https://www.zhihu.com/question/20807188
427             https://www.byvoid.com/zhs/blog/string-hash-compare
428 */
相关代码