Simon 's Blog
» 做笔记做笔记
Toggle navigation
Simon 's Blog
HOME
总裁介绍
coper
zongcai
what
ARCH
TAGS
navigation
!!! 简单好用的hash表-----uthash
? uthash ?
2018-03-06 09:44:45
1322
0
0
simon88
? uthash ?
散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。线性表查找的时间复杂度为O(n)而平衡二叉树的查找的时间复杂度为O(log(n))。无论是采用线程表或是树进行存储,都面临面随着数据量的增大,查找速度将不同程度变慢的问题。而哈希表正好解决了这个问题。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数 函数f (key)常用的对应关系: - 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=a\cdot k + b,其中a\,b为常数(这种散列函数叫做自身函数) - 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。 - 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。 - 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。 - 随机数法 - 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k \,\bmod \,p, p\le m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生碰撞。 uthash支持:增加、查找、删除、计数、迭代、排序、选择等操作。 ``` #include "uthash.h" typedef struct g_hashElement { int key; char name[10]; UT_hash_handle hh; } tTestHashElement; tTestHashElement *element = nullptr; // 添加 void add_user(int userID,char*name) { tTestHashElement*starget = (tTestHashElement*)malloc(sizeof(tTestHashElement)); starget->key = userID; strcpy(starget->name, name); HASH_ADD_INT(element, key, starget);/* id: name of key field */ } //查找 tTestHashElement* findUser(int userID) { tTestHashElement* sTarget = nullptr; HASH_FIND_INT(element, &userID, sTarget); return sTarget; } //删除 void deleteUser(tTestHashElement*User) { if (!User) { return; } HASH_DEL(element, User); free(User); } //计数 void printHash() { unsigned int num_user; num_user = HASH_COUNT(element); printf("there are %u element\n",num_user); tTestHashElement*sww = element; for (; sww!=nullptr; sww = (tTestHashElement*)sww->hh.next) { printf("element key %d:name %s\n",sww->key,sww->name); } } //比较 int name_sort(tTestHashElement*a,tTestHashElement*b) { return strcmp(a->name, b->name); } int id_sort(tTestHashElement*a,tTestHashElement*b) { return a->key - b->key; } //排序 void sortByName(tTestHashElement*a,tTestHashElement*b) { HASH_SORT(element, name_sort); } void sortByID(tTestHashElement*a,tTestHashElement*b) { HASH_SORT(element, id_sort); } ``` ```C #include "uthash.h" #include <stdlib.h> /* malloc */ #include <stdio.h> /* printf */ #include <time.h> typedef struct example_user_t { int id; int cookie; UT_hash_handle hh; } example_user_t; int main(int argc,char *argv[]) { int i; example_user_t *user, *users=NULL; srand((unsigned int)time(NULL)); /* create elements */ for(i=0;i<10;i++) { if ( (user = (example_user_t*)malloc(sizeof(example_user_t))) == NULL) exit(-1); user->id = rand()%100; user->cookie = i*i; HASH_ADD_INT(users,id,user); } for(user=users; user != NULL; user=(example_user_t*)(user->hh.next)) { printf("user %d, cookie %d\n", user->id, user->cookie); } return 0; } ``` 参考自[【STL】哈希表 uthash.h](http://blog.csdn.net/yhhwatl/article/details/27335331)
上一篇:
libev源码解析
下一篇:
XPath
0
赞
1322 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
0
条评论
More...
<>