hash 算法-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心

苦海澜石

凯发app官方网站首页　| 　博文目录　| 　关于我

khls27

  • 博客访问： 753010
  • 博文数量： 144
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1150
  • 用 户 组： 普通用户
  • 注册时间： 2014-03-17 14:32
个人简介

小公司研发总监，既当司令也当兵！

文章分类

全部博文（144）

推荐博文
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
hash 算法--联系人查找

分类： linux

2016-01-02 22:40:29

hash算法原理本文就不累赘讲述了，百度/google一下就知道了。

本demo程序实现一个简单的联系人hash表，通过姓名查找联系人：
1. hash函数采用简单的姓名字母累加和，通过掩码映射的方式获取hash-key；
2. 冲突解决采用链式散列；
3.由于联系人姓名（拼音）累加和分布相对集中（几百到两千左右），因此该hash表容量一般小于2000冲突较少，如果联系人数量较多，该hash函数冲突会增加。

点击(此处)折叠或打开

  1. /**
  2. * 联系人hash表实现demo
  3. */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>

  8. struct hashtableentry {
  9.     int flag;
  10.     int nextindex;
  11.     int prveindex;
  12.     char* name;
  13. };
  14.     
  15. struct peoplehashtable {
  16.     unsigned int size;
  17.     unsigned int entrys;
  18.     struct hashtableentry *datas;
  19. };

  21. enum entryflag {
  22.     state_unused = 0,
  23.     state_hash_used,
  24.     state_collision_used
  25. };

  27. int getuppersize(int size)
  28. {
  29.     int uppersize = 1;

  31.     if (size <= 0)
  32.         return 1;

  34.     while (uppersize < size)
  35.         uppersize <<= 1;

  37.     return uppersize;

  39. }

  41. int gethashkey(struct peoplehashtable *table, const char *name)
  42. {
  43.     char *ptr;
  44.     unsigned key = 0;

  46.     if (null == name)
  47.         return -1;

  49.     ptr = name;

  51.     while ('\0' != *ptr)
  52.     {
  53.         key = *ptr;
  54.         ptr;
  55.     }

  57.     printf("sum of %s: [%d], and key : [%d]\n",name, key, key & (table->size -1));
  58.     if (null == table)
  59.         return key;

  61.     return (key & (table->size -1));
  62. }

  64. int insert2table(struct peoplehashtable *table, char *name)
  65. {
  66.     int key = 0;
  67.     struct hashtableentry *entry;
  68.     struct hashtableentry *tmp;

  70.     int i;

  72.     if (null == table)
  73.         return -1;

  75.     if (table->entrys == table->size)
  76.     {
  77.         printf("table is full, can not insert only more!\n");
  78.         return -1;
  79.     }

  81.     key = gethashkey(table, name);
  82.     entry = &(table->datas[key]);

  84.     if (entry->flag == state_unused)
  85.     {
  86.         entry->flag = state_hash_used;
  87.         entry->name = name;
  88.         table->entrys;
  89.         return 0;
  90.     }

  92.     if (entry->flag == state_hash_used)
  93.     {
  94.         // find a useable entry
  95.         for (i = 0; i < table->size; i)
  96.         {
  97.             if (table->datas[i].flag == state_unused)
  98.                 break;
  99.         }

  101.         // find if entry has a collision entry
  102.         while( entry->nextindex != -1)
  103.         {
  104.             entry = &table->datas[entry->nextindex];
  105.         }

  107.         tmp = &(table->datas[i]);

  109.         tmp->flag = state_collision_used;
  110.         tmp->name = name;
  111.         tmp->prveindex = key;

  113.         entry->nextindex = i;
  114.         table->entrys;
  115.         return 0;
  116.     }
  117.     
  118.     if (entry->flag == state_collision_used)
  119.     {
  120.         // find a useable entry
  121.         for (i = 0; i < table->size; i)
  122.         {
  123.             if (table->datas[i].flag == state_unused)
  124.                 break;
  125.         }

  127.         // remove current entry to the empty entry space
  128.         tmp = &table->datas[entry->prveindex];
  129.         tmp->nextindex = i;

  131.         tmp = &table->datas[i];
  132.         tmp->prveindex = entry->prveindex;
  133.         tmp->flag = entry->flag;
  134.         tmp->name = entry->name;
  135.         tmp->nextindex = entry->nextindex;

  137.         entry->flag = state_hash_used;
  138.         entry->name = name;
  139.         entry->prveindex = -1;
  140.         entry->nextindex = -1;

  142.         table->entrys;
  143.         return 0;
  144.     }

  146.     return -1;
  147. }

  149. struct hashtableentry* findpeople(struct peoplehashtable *table, char *name)
  150. {
  151.     int key;
  152.     struct hashtableentry *entry = null;

  154.     if (null == table)
  155.         return null;

  157.     key = gethashkey(table, name);

  159.     entry = &table->datas[key];
  160.     if (entry->name != null && !strcmp(entry->name, name))
  161.     {
  162.         return entry;
  163.     }

  165.     while(entry)
  166.     {
  167.         if (entry->name && !strcmp(entry->name, name))
  168.             return entry;

  170.         if (entry->nextindex != -1)
  171.             entry = &table->datas[entry->nextindex];
  172.         else
  173.             return null;
  174.     }
  175.     return null;
  176. }

  178. int createhashtable(struct peoplehashtable **table, unsigned int size)
  179. {
  180.     int uppersize = getuppersize(size);

  182.     struct peoplehashtable *tableptr = null;
  183.     struct hashtableentry *entrylist = null;
  184.     int i;

  186.     tableptr = (struct peoplehashtable*)malloc(sizeof(*tableptr));
  187.     if (null == tableptr)
  188.         return -1;

  190.     entrylist = (struct hashtableentry*)malloc(sizeof(*entrylist) * uppersize);
  191.     if (null == entrylist)
  192.     {
  193.         free(tableptr);
  194.         return -1;
  195.     }
  196.     memset(entrylist, 0, sizeof(*entrylist) * uppersize);
  197.     for(i = 0; i < uppersize; i)
  198.     {
  199.         entrylist[i].flag = state_unused;
  200.         entrylist[i].name = null;
  201.         entrylist[i].nextindex = -1;
  202.         entrylist[i].prveindex = -1;
  203.     }

  205.     tableptr->datas = entrylist;
  206.     tableptr->entrys = 0;
  207.     tableptr->size = uppersize;

  209.     *table = tableptr;

  211.     return 0;
  212. }

  214. int destoryhashtable(struct peoplehashtable *table)
  215. {
  216.     if (null == table)
  217.         return 0;

  219.     free(table->datas);
  220.     free(table);

  222.     return 0;
  223. }

  225. static void debug_print_table(struct peoplehashtable *table)
  226. {
  227.     int i;

  229.     printf("table infos:\n");
  230.     printf("size: [%d], entry numbers;[%d]\n", table->size,table->entrys);
  231.     printf("index flag prve next name\n");
  232.     for (i = 0; i < table->size; i)
  233.     {
  234.         printf("]]]] %s\n", i,table->datas[i].flag ,table->datas[i].prveindex, table->datas[i].nextindex, table->datas[i].name == null ? "--" :table->datas[i].name);
  235.     }
  236. }
  237. /*
  238. void main()
  239. {
  240.     char *peoples[30]= {
  241.         "刘敏",
  242.         "wang wu",
  243.         "li si",
  244.         "liu yu gu",
  245.         "jiang jie hui",
  246.         "tan wei wei",
  247.         "liu tao",
  248.         "mi yue",
  249.         "mi shu",
  250.         "yin si",
  251.         "yin dang",
  252.         "huang zi",
  253.         "zhang zi",
  254.         "qu yuan",
  255.         "tang jia jun",
  256.         "gui wa zi",
  257.         "qu li zi",
  258.         "gong zhu",
  259.         "tang hui",
  260.         "jiu zhong",
  261.         ""
  262.     };

  264.     struct peoplehashtable *table;
  265.     struct hashtableentry *entry;

  267.     int ret;
  268.     int i;

  270.     ret = createhashtable(&table, 20);

  272.     if (ret < 0)
  273.     {
  274.         printf("create hash table fail\n");
  275.         return;
  276.     }

  278.     i = 0;
  279.     for (i = 0; i < 20; i)
  280.     {
  281.         insert2table(table,peoples[i]);
  282.     }
  283.     printf("-- add people done!\n");
  284.     
  285.     debug_print_table(table);


  288.     entry = findpeople(table, "jiu zhong");
  289.     if (entry != null)
  290.     {
  291.         printf("find!\n");
  292.     }
  293.     else
  294.         printf("--no--\n");

  296.     destoryhashtable(table);
  297.     table = null;
  298. }*/



阅读(2311) | 评论(0) | 转发(0) |
0

上一篇：md5 c语言实现（根据rfc1321）

下一篇：快速排序

给主人留下些什么吧！~~
| | | | |

凯发app官方网站 copyright 2001-2010 chinaunix.net all rights reserved 北京皓辰网域网络信息技术有限公司. 凯发k8官网下载客户端中心的版权所有

感谢所有关心和支持过chinaunix的朋友们
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图