哈希表

1、作用：

用来快速判断一个元素是否出现在集合中，可以将查找元素的复杂度从O(n)降低到O(1).

2、哈希映射

（1）对于每一个给定的关键字key值，通过哈希函数映射 f(key) 之后，就可以得到一个在哈希表M中 记录该关键字的地址。

（2）通常的操作：
key % (总长度) = 哈希表M中的位置
每个关键字key对应的位置是固定的

（3）<font color="red"存储的数据结构
在python中，其实就是一个字典。
将每个元素都对应一个序号，构成key-value的形式，存在字典中。关键字key的值是元素，经过哈希表映射之后得到的位置是value的值。
当需要查找元素的时候，直接利用dict[key] = value 的形式就可以找到。

3、解决哈希碰撞问题

常用的解决方案有散列法和拉链法。散列法又分为开放寻址法和再散列法

4、哈希表的优势

（1）在列表查找中，使用最广泛的二分查找算法，复杂度为O(log2n)，但其始终只能用于有序列表。普通无序列表只能采用遍历查找，复杂度为O(n)。
（2）拥有较为理想的哈希函数实现的哈希表，对其任意元素可以直接通过计算获取位置，查找速度始终为常数级，即O(1)。

5、js中哈希表的实现

js中只有Map，没有HashMap。HashMap只是map的一种底层实现方式。

// 创建一个Map对象
var map = new Map();

// 可以用数组当中的下标作为key,也可以用值作为key
// 检查key是否存在
map.has(key);

// 通过key取对应的value
map.get(key);

// 删除
m.delete('Adam');

// 添加
m.set('Adam', 67);

6、哈希表的空间消耗

使用哈希表的时候，需要用到栈，所以空间复杂度为O(n)

数组、链表和哈希表关系

数组与链表的区别

（1）存储空间上
链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据时，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。
（2）长度的可变性
链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。
（3）查找效率：
按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；按值查找时，若数组无序，数组和链表时间复杂度均为O(n)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；
（4）插入删除时：
数组平均需要移动n/2个元素，而链表只需修改指针即可；
（5）空间分配方面：
(静态)数组从栈中分配空间, 对于程序员(某些编程语言如java对于堆内存的管理也交由程序自动控制，但性能肯定有差异)方便快速,但是自由度小。链表从堆中分配空间, 自由度大但是申请管理比较麻烦。

链表

那么有没有一种数据结构可以结合该两者的优点呢？那就是哈希表。

哈希表将需要查找的key值，通过hash函数的计算，换算为数组的位置值。这样在查找时就可以直接定位数据的位置。它结合了数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势

总结

数组------查找快，修改慢！
链表------查找慢，修改快！
哈希表：是数组和链表的结合体。

注意：

• 在程序变量中，数组和链表都只需要在栈上存储一个起始位置，占用一个变量位置即可。
• hash将需要定位的值通过hash函数换算为数据的位置值，以空间换时间。

链表开源库—utlist.h

介绍

utlist.h中包含了一组用于C结构体的通用链表宏。使用起来非常简单，只需要将utlist.h拷贝到你的项目，并包含进你的源码即可，utlist.h宏提供了基本的链表操作：添加、删除、排序、遍历。

源码获取

utlist.h的源码可以在GitHub上直接获取(src/utlist.h)：

https://github.com/troydhanson/uthash

链表类型

utlist.h支持下面三种类型的链表：

• 单向链表
• 双向链表
• 环形双向链表

使用效率

• 头部添加：对所有的链表类型都是常量；
• 尾部添加：单向链表O(n)；双向链表是常量；
• 删除：单向链表O(n)；双向链表是常量；
• 排序：对所有链表类型都是O(n log(n))；
• 有序链表遍历：对所有链表类型都是O(n)；
• 无序链表遍历：对所有链表类型都是O(n)；

参考：开源库uthash第二弹utlist.h

哈希表开源C库—uthash

简介

C语言的标准库中没有哈希表的函数可以使用，但是可以通过第三方头文件uthash.h这个包来实现哈希表的操作。uthash 是C的比较优秀的开源代码，它实现了常见的hash操作函数，例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能，支持C语言的任意数据结构最为key值，甚至可以采用多个值作为key，无论是自定义的struct还是基本数据类型，需要注意的是不同类型的key其操作接口方式略有不通。

使用uthash代码时只需要包含头文件"uthash.h"即可。由于该代码采用宏的方式实现，所有的实现代码都在uthash.h文件中，因此只需要在自己的代码中包含该头文件即可。可以通过下面两种方式获取源代码。

• 通过官方下载链接：
  官方GitHub地址

https://github.com/troydhanson/uthash

• 另外uthash的英文使用文档介绍可从下面网址获得：
  uthash英文使用文档

http://troydhanson.github.io/uthash/
http://troydhanson.github.io/uthash/userguide.html

uthash能做什么

通过uthash软件，支持对hash表的item进行如下操作：
添加/替换（add/replace）
查找（find）
删除（delete）
统计（count）
迭代器（iterate）
排序（sort）

uthash包括的额外内容

uthash 附带了三个“附加功能”。这些提供列表、动态数组和字符串：

• utlist.h为 C 结构提供链表宏。
• utarray.h使用宏实现动态数组。
• utstring.h实现了一个基本的动态字符串。

uthash效率

uthash的插入、查找、删除的操作时间都是常量，当然这个常量的值受到key以及所选择的hash函数的影响。

uthash共提供了7种函数函数，一般情况下选择默认的即可。如果对效率要求特别高时，可以再根据自己的需求选择适合自己的hash函数。

简单使用

定义hash数据结构

在自己的数据结构中添加UT_hash_handle的支持：

#include "uthash.h"

struct my_struct {
    int id;            /* we'll use this field as the key */
    char name[10];
    UT_hash_handle hh; /* makes this structure hashable */
};

struct my_struct *g_users = NULL;

• id是键（key）；
• name是值（value），即自己要保存的数据域，这里可以根据自己的需要让它变成结构体指针或者其他类型都可以；
• hh是内部使用的hash处理句柄，在使用过程中，只需要在结构体中定义一个UT_hash_handle类型的变量即可，不需要为该句柄变量赋值，但必须在该结构体中定义该变量；
• Uthash所实现的hash表中可以提供类似于双向链表的操作，可以通过结构体成员hh的hh.prev和hh.next获取当前节点的上一个节点或者下一个节点。

注意：在uthash中，当您的结构添加到hash表中时，并不会被移动或拷贝到其他位置。这意味着在程序运行过程中，无论是对hash表进行添加或删除操作，都可以保证您数据结构的安全性。

从hash表查找item

struct my_struct *find_user(int user_id)
{
    struct my_struct *s = NULL;
    HASH_FIND_INT(g_users, &user_id, s);
    return s;
}

向hash表添加item

void add_user(struct my_struct *s) 
{
    HASH_ADD_INT(g_users, id, s );
}

从hash删除item

void delete_user(struct my_struct *user)
{
    HASH_DEL(g_users, user);
}

在实际操作时，需要特别注意以下三点：

• 与任何hash表一样，每个item都必须有唯一的key，因此uthash也要求key具有唯一性；
• 插入时，先查找，当键不在当前的hash表中时再进行插入，以确保键的唯一性；
• 需调用插入接口函数时需要明确告诉接口函数，自己定义的键变量的名字是什么。

参考：开源库uthash第一弹uthash.h

最后

更多请阅读英文使用文档：
uthash英文使用文档

简介

我就默认大家都清楚哈希表的原理、用途了。今天这篇文章侧重于讲解使用哈希表的必要性，并且用实验数据和自己的推理作为佐证。

哈希表性能测试

代码

最简单的一个哈希例子，记录了学生id和成绩的映射。没考虑异常处理，没考虑数据合理性。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define HASH_TABLE_SIZE 520000000

typedef struct
{
    int id;
    int score;
} id_and_score;

typedef struct
{
    id_and_score *val;
    int count;
} HASH_TABLE;
int m = 0;

//初始化散列表
int init_hash_table(HASH_TABLE *H)
{
    int i;
    m = HASH_TABLE_SIZE;
    H->count = m;
    H->val = (id_and_score *)malloc(m * sizeof(id_and_score));
    for (i = 0; i < m; i++)
    {
        H->val[i].id = i;
        H->val[i].score = i+2;
    }
    return 1;
}

//散列函数
int hash_func(int key)
{
    return key % m;
}

//散列表查找关键字
int search_by_hash(HASH_TABLE H, int key)
{
    int addr = hash_func(key);
    while (H.val[addr].id != key)
    {
        addr = (addr + 1) % m;
    }
    return H.val[addr].score;
}

//遍历查找
int search_by_ergodic(HASH_TABLE H, int key)
{
    int i = 0;
    while (i < HASH_TABLE_SIZE)
    {
        if (H.val[i].id == key)
            return H.val[i].score;
        i++;
    }
    return -1;
}

int main()
{
    int time1, time2;

    HASH_TABLE H;
    int i;

    time1 = clock();
    init_hash_table(&H);
    time2 = clock();
    printf("建立哈希表耗费的时间是：%fs\n", (double)(time2 - time1)/CLOCKS_PER_SEC);

    time1 = clock();
    int score = search_by_hash(H, 500000025);
    time2 = clock();
    printf("搜索到500000025号学生的分数是：%d\n", score);
    printf("哈希法搜索耗费的时间是：%fs\n", (double)(time2 - time1)/CLOCKS_PER_SEC);

    time1 = clock();
    score = search_by_ergodic(H, 500000025);
    time2 = clock();
    printf("搜索到500000025号学生的分数是：%d\n", score);
    printf("遍历法搜索耗费的时间是：%fs\n", (double)(time2 - time1)/CLOCKS_PER_SEC);
}

测试结果

响应时间：

CPU占用：

为什么要用哈希表

提高查询速度

在上边已经看到了，在5亿数据量下，使用哈希进行搜索耗时级别为零（耗时很小以至于clock函数都识别不出来），而遍历搜索需要1.5s左右。用哈希进行查找可以明显提高查询速度。

但当时有人可能问了：建立哈希需要将近九秒，这样算下来，总时间应该变多了啊，为什么哈希表建立这么耗时，我们还是要使用它呢？

这样想其实也没有问题，但是我们不能忽略使用场景而空谈。什么时候用哈希呢？答案是查询量非常大的时候。在这种情况下，我们当然不能查一次数据就建一次哈希表；而是一开始，当进程或系统启动的时候，就把数据都加载到内存里边，建立哈希表。这样的话，我们只是在系统启动的时候耗费了9s中建立哈希表。而其他任何时候查询都几乎不耗时间。

在查询量很大的情况下，比如说一天查几百万次（例如某度），这样子用哈希查询相比遍历法节约了几百万秒。查询频率越高，哈希的优势越大。

减少CPU资源的损耗

其实更重要的一点就是节约CPU资源了。

CPU资源是非常宝贵的。如果我们用遍历法，遍历这五亿多条数据，CPU瞬间就拉满了。在上图中，我仅仅一个用户进行查询就耗费了30%的CPU。如果是比较大的应用，同一时间可能有成千上万个用户查询。这么搞CPU，就是再高端的服务器也扛不住啊。

用什么做哈希的key值

大家都知道哈希表是key-value的组合。那么我们应该如何选取key值呢？

最重要的一点：key值不能经常变化。大家在上边也看到了，建立哈希表需要的时间非常长。如果我们频繁改动key值，就要频繁的重建哈希，即浪费时间，也浪费资源。

所以我们一般将较为固定的值作为key，比如url，用户的id等。

写在最后

大家有什么疑问请尽管提，有指导意见也请指出来。我会尽力回答和改正。