c/c++ hash表 (哈希表 字典表)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

1: 表: 存储数据 key –> value;

这里写图片描述

2: 表存储数据结构的困难:
怎么查找? 一个一个key去比较去查找?==效率不高

这里写图片描述

**3: Hash算法加快查找;
将字符串的key,转成整数,使用整数找到对应的value;**

Hash算法将字符串转成整数,同样的Hash值得 key:value会放到一个集合里面,由于Hash能使得不同的字符串尽量有不同的整数值(仍然有重复);
将海量的数据,按照HASH值分成不同的集合,先找集合,再找key–>value,大大提高效率;

这里写图片描述

Hash表设计

1: key, value节点:
struct hash_node {
char* key;
void* node;
struct hash_node* next;
};

2: hash算法: 选取一种HASH算法;
3: 有限的集合数目, 定义一个集合数目,每个集合的元素用链表连接;
4: 对用户开放的hash表接口;
struct hash_table* creator_hash_table(集合的数目);
void destroy_hash_table(struct hash_table*);
void* hash_find(table, char* key);
hash_delete(table, char* key);
hash_insert(table, char*key, void* value); // 直接插入,不判断是否有key重复;
hash_set(table, char* key, void* value); // 如果key存在就覆盖,如果不存在返回;


  • 身份证(key):数据信息(value),如果我们有10000个学生,查找一个学生的话,很费劲;
  • 如果说有一个办法能均匀的将10000个人分成n个集合,(N100*100)我们有一种办法能快速的找到key,所对应的集合,那么就能很快的在集合里面找出所对应的value;
  • 怎么根据key来分集合;
  • 怎么分能够相对比较均匀;
  • 采用Hash算法
    • 1:将一个字符串变成一个整数 %N规模(0,N-1)的集合序号里面
    • 整数 %N = 集合序列号,[0,n-1],用数组来表示每个集合;
    • 2:对于不同的字符串,尽可能的生成不同的Key;
      • Hash散列,要散得足够均匀;
      • “hello”–>3;
      • “helmm” –>7;
      • 随机的字符串样本,能均匀的分布出来,分散开来;
    • 主流的Hash算法;

创建Hash结构

这里写图片描述
这里写图片描述

创建hash对象

这里写图片描述

这里写图片描述

引用mysql经典算法函数

这里写图片描述

增/插入数据

这里写图片描述

这里写图片描述

删除表

这里写图片描述
这里写图片描述

删除hash对象

这里写图片描述

这里写图片描述

修改数据

这里写图片描述
这里写图片描述

查询数据

这里写图片描述
这里写图片描述

这里写图片描述

总结

1: 理解HASH表的原理,为什么能实现基于名字快速查找;
2: 理解HASH算法;
3: 编写HASH表;


–>源码

点这里可以跳转到人工智能网站

发表评论