简单好用的hash表-----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)

Simon 's Blog

导航

OHH,最近发表

这里随便填填,没事