之前一直都不知道哈希表怎么就能那么快的存取的，今天就来好好研究一番，并且使用C语言简单的实现一下。
刚刚百度了一番，其实哈希存储的实现主要分成两个步骤来考虑：
1、申请一块连续的存储空间，把空间分割成m个桶，用来存储数据。
2、实现一个散列算法，把key经过算法散列对应到我们的m个桶上。
国际惯例，上代码：
main函数部分
#include <stdio.h>
#include <stdlib.h>
int hash(int, int);
void hset(int*, int, int, int);
int hget(int*, int, int);
void main() {
int m = 100;
size_t size = (size_t) (sizeof(int) * m);
int* p = malloc(size);
int k = 1, v = 1024;
hset(p, m, k, v);
printf("设置KEY - VALUE : %d - %d \n", k, v);
printf("获取KEY - VALUE : %d - %d \n", k, hget(p, m, k));
free(p);
}
哈希算法，超简单版：
int hash(int key, int m) {
return key % m;
}
hset函数：
void hset(int* p, int m, int k, int v) {
int hash_key = hash(k, m);
p += hash_key;
*p = v;
}
hget函数：
int hget(int* p, int m, int k) {
int hash_key = hash(k, m);
p += hash_key;
return *p;
}
ooh my god，就是他！！！！！！！！！！！
这么简单吗？就这么简单吗？
嗯呢，就是这么简单。
好意外，好惊喜！(__) 嘻嘻……
言归正传，来看看这个简单的哈希存储是怎么实现的。
1-1内存示意图
图1-1可以看出，整个哈希存储是由一块连续的存储空间，分割成m个桶，每个桶里存储着具体的数据，通的大小由桶内数据类型决定。
桶初始化过程：
int m = 100; // 定义桶的数量
size_t size = (size_t) (sizeof(int) * m); // 根据桶里存放的数据类型，计算需要的内存空间
int* p = malloc(size); //申请内存
OK，初始化工作完成，我们申请了一块连续的存储空间，可以存放100个桶，每个桶里存放了一个int型数据，每个桶的大小4字节。
也就是我们的这个hashmap可以存放100条int类型的数据，接下来会有大兄弟问了，人家的哈希表能存储理论无限多的数据，怎么你的才能存储100条，或者说有限条数据呢？人家哈希表能存储各种数据类型，你怎么就能存int呢？人家key随意设置，你的为啥1和101就互相覆盖了？人家的……
对呀，那都是人家的哈希表，我的就能存储100条int型数据。O(∩_∩)O哈哈~
开玩笑的，上面那些问题都是高阶哈希表具备的功能，包括自动扩容，任意类型存储，还有哈希碰撞的解决，这些都不在这篇文章的讨论范围内，后续我会专门写文章来解释的。
看一看哈希算法
int hash(int key, int m) {
return key % m;
}
其实这不是一个严格意义上的哈希算法，但是他却把我们的输入散列到我们所有桶上，要想得到一个好的哈希算法还是挺难的，所以我们这部分可以留给大家自行百度，我只是演示一下这个功能。
通过上面的算法，我们所有的输入都可以散列到一个具体的桶上，这个值就可以帮助我们做哈希定位。
hset和hget
void hset(int* p, int m, int k, int v) {
int hash_key = hash(k, m);
p += hash_key;
*p = v;
}
int hget(int* p, int m, int k) {
int hash_key = hash(k, m);
p += hash_key;
return *p;
}
不管是set还是get，都有执行了这两句
int hash_key = hash(k, m); // 获得哈希值
p += hash_key; //根据哈希值对指针进行偏移
偏移后的指针，指向的地址就是存储值的内存地址，接下来就简单了，对指针指向的地址赋值就是set，通过指针地址获得数据就是get。
至此，我们的一个简单哈希表就实现了，是不是超简单，希望这篇文章能给菜鸟们帮助，也同时希望大牛们提出宝贵的意见建议。
网友评论