-
各种哈希函数的C语言程序代码
2014-06-19 11:46:54常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。 BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RS...常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。
BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}return (hash & 0x7FFFFFFF);
}// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;while (*str)
{
hash = hash * a + (*str++);
a *= b;
}return (hash & 0x7FFFFFFF);
}// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;while (*str)
{
hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}return (hash & 0x7FFFFFFF);
}// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;while (*str)
{
hash = (hash << OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}return (hash & 0x7FFFFFFF);
}// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;while (*str)
{
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}return (hash & 0x7FFFFFFF);
}// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;while (*str)
{
hash = hash * seed + (*str++);
}return (hash & 0x7FFFFFFF);
}// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;while (*str)
{
hash += (hash << 5) + (*str++);
}return (hash & 0x7FFFFFFF);
}// AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = 0;
int i;for (i=0; *str; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
}
}return (hash & 0x7FFFFFFF);
} -
C语言新哈希函数
2021-01-06 23:21:26小明设计了一个哈希函数,将一个长度为 k 的字符串转成个长度为 32 的字符串。这个哈希函数的设计如下: 声明一个长度为 32 的数组 arr,并将其中元素全部初始化为 0。 取出每一位的 ASCII 值,将长度为 k的字符串中...小明设计了一个哈希函数,将一个长度为 k 的字符串转成个长度为 32 的字符串。这个哈希函数的设计如下:
声明一个长度为 32 的数组 arr,并将其中元素全部初始化为 0。 取出每一位的 ASCII 值,将长度为 k的字符串中第 iii 位的 ASCII 码加入到 arr[i % 32] 中(1≤i≤k)。 声明一个长度为 32的数组 bits,令 bits[j] 为 arr[31 - j] 与 arr[j] << 1 的值进行了按位异或运算后得到的结果(0≤j≤31)。 计算出 bits[j] % 85 + 34 并将该十进制数在 ASCII 码中对应的字符输出到结果字符串的第 j+1 位(0≤j≤31)。
请实现一个程序,当输入一个字符串 s 后,输出哈希函数的结果 f(s)。
输入格式
输入为一行,包括一个长度为 k 的字符串(32<k<500),这个字符串由大写字母、小写字母和数字组成(不含空格)。
输出格式
输出为一行,为一个长度为 32 的字符串哈希结果
#include <stdio.h> #include <string.h> int main() { int arr[32]; //声明一个长度为32的数组arr int bits[32]; int result[32]; for (int i = 0; i < 32; i++) {//初始化arr数组 arr[i] = 0; } char s[500]; //声明一个字符串s scanf("%s",&s); //输入字符串s int k = strlen(s); //计算字符串s的长度 for (int i = 1; i <= k; i++) { //将长度为k的字符串中第i位的ASC码加入到数组中 arr[i % 32] += s[i - 1]; } for (int j = 0; j < 32; j++) { //字符串转换 bits[j] = arr[31 - j] ^ (arr[j] << 1); result[j] = bits[j] % 85 + 34; printf("%c",result[j]);//输出哈希函数结果 } return 0; }
-
哈希表 C语言 小白初探
2020-04-28 16:22:16哈希表初理解1.... 散列函数的构造1. 选择标准2. 常见方法6. 代码分析 本篇的解释非常非常小白,帮助理解入门。 1. 哈希表是什么 哈希表又叫散列表(Hash table),外国人给起的名字,别念反变成嘻哈表就...哈希表初理解
本篇的解释非常非常小白,帮助理解入门。1. 哈希表是什么
哈希表又叫散列表(Hash table),外国人给起的名字,别念反变成嘻哈表就OK了,哈哈。为了更好的理解哈希表,我们拿字典当例子。小时候大家都查过字典吧,有的同学按照拼音来查,有的同学按照偏旁部首来查,等到熟悉了之后,为了比比谁查的更快,偏旁拼音都不看了,直接凭着abcde…xyz的顺序,大概就能翻到想要的那一页。
咳咳,扯远了。哈希表,它就像一本字典一样,但是它像一维数组一样,是一维的,等到了哈希map,那就复杂了。同时它的功能也并不是简单的查询,而是能完成增删改查。先记住这两点吧
- 维度 :一维
- 功能:增删改查
2. 特别注意哪些参数
还是拿字典来举例子吧。我们在新版的《新华字典》中随机取几个汉字,假设它们所在的页数分别为如下表格:
k 哈 希 表 很 难 f(k) 23 45 65 56 45 这里假设‘难希’都在45页。k和f(k)分别代表什么呢?要去新华字典查 希望的 希这个字的解释,假设你只能用拼音方法,Xi 那么X是不是你所要找到关键字呢。你在差字典的时候,字典的目录会返回给你希的页数,希-45。那么,k就是要查找的关键字,f(k) 就是返回给你的页数。在哈希表中,k是关键字,f(k)是返回的地址。
又明确了两点:- k: 需要查找的关键字
- f(k): 返回地址
3. 哈希冲突
1. 什么是哈希冲突
字典可以一页排版好好几个汉字,在访问45页的时候,希和难同时出现,但是返回值要求只能有一个。那返回值取困难的难,还是取希望的希?这就是冲突。
2. 完全避免冲突的条件
条件有两个,不解释:
- 关键字的个数小于哈希表的长度
- 选择合适的散列函数f(k)
3. 冲突不可能完全避免的原因
因素非常多,主要原因是哈希表的特性,决定了关键字的个数通常要大于散列表的长度。
4. 影响冲突的因素
表的填满程度,f(k)函数
4. 既然有冲突,为什么还要使用哈希表
答:快!看上图表格,时间复杂度O(1)。并且,通过人的设计,冲突可以减少。
5. 散列函数的构造
就是f(k)的构造。
1. 选择标准
- 简单
- 均匀
2. 常见方法
- 平方取中法
- 除留余数法
- 相乘取整法
- 随机函数法
这些方法会在另外的博客上介绍,这里只留一个概念。
6. 代码分析
#include<stdio.h> #include<stdlib.h> #define HASHSIZE 12 #define NULLKEY -32768 typedef struct { int* elem; int count; }HashTable; int m = 0; //初始化散列表 int InitHashTable(HashTable* H) { int i; m = HASHSIZE; H->count = m; H->elem = (int*)malloc(m * sizeof(int)); for (i = 0; i < m; i++) { H->elem[i] = NULLKEY; } return 1; } //散列函数 int Hash(int key) { return key % m; } //插入关键字进散列表 void InsertHash(HashTable* H, int key) { int addr = Hash(key); while (H->elem[addr] != NULLKEY) { addr = (addr + 1) % m; } H->elem[addr] = key; } //查找指定元素 int SearchHash(HashTable H, int key, int* addr) { *addr = Hash(key); while (H.elem[*addr]!= key) { *addr = (*addr + 1) % m; if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) { return -1; } } return *addr; } int main() { int a[12] = { 12,67,56,16,25,37,22,29,15,47,48,34 }; HashTable H; int i; InitHashTable(&H); for(i = 0; i < m; i++) { InsertHash(&H,a[i]); } printf("插入之后的哈希表为:"); for (i = 0; i < m; i++) { printf("%d,", H.elem[i]); } int addr, j; j = SearchHash(H, a[5], &addr); printf("搜索到a[5]的地址是:%d", j); }
输出的结果:
插入之后的哈希表为:12,25,37,15,16,29,48,67,56,34,22,47,搜索到a[5]的地址是:2
这段代码先将哈希表初始化,然后将数组中的值通过哈希函数赋值给哈希表。最终返回的是哈希表中a[5],也就是37在表中的地址。散列函数是除留余数法。
-
哈希表C语言实现详解
2019-12-29 01:16:412、操作函数声明 3、具体实现 1、数据结构 #define HASH_TABLE_MALLOC(size) rt_malloc(size); #define HASH_TABLE_REALLOC(p,size) rt_realloc(p,size); #define HASH_TABLE_CALLOC(n,size) rt_calloc(n,size);...目录
1、数据结构
#define HASH_TABLE_MALLOC(size) rt_malloc(size); #define HASH_TABLE_REALLOC(p,size) rt_realloc(p,size); #define HASH_TABLE_CALLOC(n,size) rt_calloc(n,size); #define HASH_TABLE_FREE(p) rt_free(p); struct hash_table_node; struct hash_table; /* 哈希函数,根据key计算哈希值 */ typedef int (*hash_fun)(struct hash_table *table, const void *key); /* *哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key * hash桶中的元素是从小到大排列的, * 返回值 > 0 : key_cmp > key_becmp * 返回值 = 0 : key_cmp = key_becmp * 返回值 < 0 : key_cmp < key_becmp */ typedef int (*hash_keycmp)(struct hash_table *table, const void *key_cmp, const void *key_becmp); /* hash桶中的节点数据删除函数,如果插入节点为动态分配,则需要在该函数中释放节点空间 */ typedef int (*node_value_free)(struct hash_table_node *node); struct hash_table_node { void *key; void *value; struct hash_table_node *next; /*哈希桶节点下个节点*/ }; struct hash_table { int size; /*哈希桶的大小,即数组的大小*/ int num; /*各个哈希桶中节点个数的总和*/ hash_fun hashfun; /*哈希函数*/ hash_keycmp keycmp; /*哈希key比较*/ node_value_free valuefree; /*哈希桶节点数据删除*/ struct hash_table_node **tables; /*哈希桶,其实就是一个数组*/ }; /*根据当前结构体元素的地址,获取到结构体首地址*/ //#define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER) //#define container(ptr,type,member) ({\ // const typeof( ((type *)0)->member) *__mptr = (ptr);\ // (type *) ((char *)__mptr - OFFSETOF(type,member));}) #define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER) #define container(ptr,type,member) ((type *) ((char *)ptr - OFFSETOF(type,member)))
2、操作函数声明
extern struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree); extern struct hash_table *hash_table_creat_default(int size, node_value_free valuefree); extern int hash_table_insert(struct hash_table *hashtable, void *key, void *value); extern int hash_table_delete(struct hash_table *hashtable, void *key); extern int hash_table_modify(struct hash_table *hashtable, void *key, void *value); extern void * hash_table_search(struct hash_table *hashtable, void *key); extern void hash_table_sample(void);
3、具体实现
#include "algo_hash_table.h" /** * 默认使用的哈希函数. * * @return 哈希值 */ static int hash_fun_default(struct hash_table *table, const void *key) { unsigned int hash = 0; unsigned int seed = 131; char *temp = NULL; temp = (char*)key; while(*temp) { hash = hash * seed + *temp++; } hash &= 0x7FFFFFFF; hash %= table->size; return hash; } /** * 哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key * * @return > 0 : key_cmp > key_becmp * @return = 0 : key_cmp = key_becmp * @return < 0 : key_cmp < key_becmp * */ static int hash_keycmp_default(struct hash_table *table, const void *key_cmp, const void *key_becmp) { return strcmp(key_cmp, key_becmp); } /** * 动态创建一个哈希表. * * @return NULL:创建失败 * !NULL:创建成功 */ struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree) { struct hash_table *hashtable = NULL; struct hash_table_node **tables = NULL; int i = 0; if (size < 0 || hashfun == NULL || keycmp == NULL) return NULL; /*申请哈希表结构空间*/ hashtable = HASH_TABLE_MALLOC(sizeof(*hashtable)); if (hashtable == NULL) return NULL; /*申请哈希桶数据空间,实际就是申请size大小的数组空间*/ tables = (struct hash_table_node**)HASH_TABLE_MALLOC(size * sizeof(tables)); if (tables == NULL) return NULL; hashtable->num = 0; hashtable->size = size; hashtable->tables = tables; hashtable->hashfun = hashfun; hashtable->keycmp = keycmp; hashtable->valuefree = valuefree; /*清零哈希桶(数组)空间*/ for (i = 0; i < size; i++) { hashtable->tables[i] = NULL; } return hashtable; } /** * 使用默认的函数函数、key比较函数、节点删除函数 动态创建一个哈希表. * * @return NULL:创建失败 * !NULL:创建成功 */ struct hash_table *hash_table_creat_default(int size, node_value_free valuefree) { return hash_table_creat(size, hash_fun_default, hash_keycmp_default, valuefree); } /** * 向一个哈希桶插入一个节点,有3种情况: * 1、prev==NULL,插入位置是头结点 2、key小于cur->key 3、cur==NULL,链表尾插入 * * @param hashtable: 散列表 * @param key: 关键值 * @param value: 节点数据 * @param value: 节点数据大小 * * @return 0:插入成功 * -1:哈希表不存在 或 key为空 或 value为空 * -2:节点已经存在 */ int hash_table_insert(struct hash_table *hashtable, void *key, void *value) { struct hash_table_node *prev = NULL; struct hash_table_node *cur = NULL; struct hash_table_node *new_node = NULL; int hvalue = 0; if (hashtable == NULL || key == NULL || value == NULL) return -1; /*根据key计算出哈希值*/ hvalue = hashtable->hashfun(hashtable, key); cur = hashtable->tables[hvalue]; /*hash桶中的元素是从小到大排列的,查找要插入的位置*/ while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) > 0)) { prev = cur; cur = cur->next; } /*如果key相同,表示节点以及存在,直接返回*/ if ((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) == 0)) return -2; /*插入新增节点*/ new_node = (struct hash_table_node*)HASH_TABLE_MALLOC(sizeof(*new_node)); if (new_node == NULL) return NULL; new_node->key = key; new_node->value = value; if (prev == NULL) /*第1种情况*/ { new_node->next = NULL; hashtable->tables[hvalue] = new_node;/*这里不能为cur = new_node,因为此时的cur和table[hvalue]都是无效的*/ } else /*第2、3种情况*/ { new_node->next = cur; prev->next = new_node; } hashtable->num ++; return 0; } /** * 删除一个节点. * * @param hashtable: 散列表 * @param key: 删除节点关键值 * * @return 0:删除成功 * -1:哈希表不存在 或 key为空 * -2:节点不存在 */ int hash_table_delete(struct hash_table *hashtable, void *key) { struct hash_table_node *prev = NULL; struct hash_table_node *cur = NULL; int hvalue = 0; if (hashtable == NULL || key == NULL) return -1; /*根据key计算出哈希值*/ hvalue = hashtable->hashfun(hashtable, key); cur = hashtable->tables[hvalue]; /*hash桶中的元素是从小到大排列的,查找要删除的位置*/ while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0)) { if (hashtable->keycmp(hashtable, key, cur->key) == 0) { if (prev == NULL)/*如果删除的是头结点*/ { hashtable->tables[hvalue] = cur->next; } else { prev->next = cur->next; } /*若节点所指向的数据(包括key和value)为动态分配,则需要在这里释放*/ hashtable->valuefree(cur); HASH_TABLE_FREE(cur); hashtable->num --; return 0; } else { prev = cur; cur = cur->next; } } return -2; } /** * 修改一个节点.注意事项: * 1、会先释放节点指向的就数据空间(这里如果是realloc更大的数据空间,容易造成指针泄露,且是不知道整个数据结构的大小的) * 2、修改的节点必须为新动态分配的空间 * * @param hashtable: 散列表 * @param key: 修改节点关键值 * @param value: 修改节点数据 * * @return 0:修改成功 * -1:哈希表不存在 或 key为空 或value为空 * -2:节点不存在 */ int hash_table_modify(struct hash_table *hashtable, void *key, void *value) { struct hash_table_node *cur = NULL; int hvalue = 0; if (hashtable == NULL || key == NULL || value == NULL) return -1; /*根据key计算出哈希值*/ hvalue = hashtable->hashfun(hashtable, key); cur = hashtable->tables[hvalue]; /*hash桶中的元素是从小到大排列的,查找要修改的位置*/ while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0)) { if (hashtable->keycmp(hashtable, key, cur->key) == 0) { hashtable->valuefree(cur); cur->key = key; cur->value = value; return 0; } else { cur = cur->next; } } return -2; } /** * 根据key查找节点数据. * * @param hashtable: 散列表 * @param key: 查找节点关键值 * @param value: 查找节点数据 * * @return NULL:查找失败 * !NULL:查找成功 */ void * hash_table_search(struct hash_table *hashtable, void *key) { struct hash_table_node *cur = NULL; int hvalue = 0; if (hashtable == NULL || key == NULL) return NULL; /*根据key计算出哈希值*/ hvalue = hashtable->hashfun(hashtable, key); cur = hashtable->tables[hvalue]; /*hash桶中的元素是从小到大排列的,查找要查找的位置*/ while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0)) { if (hashtable->keycmp(hashtable, key, cur->key) == 0) { return cur->value; } else { cur = cur->next; } } return NULL; } /******************************************************************************************* * 使用示例 *******************************************************************************************/ struct test_node { char key[10]; char value[10]; }; int node_value_free_sample(struct hash_table_node *node) { struct test_node *node_temp = NULL; /*根据key在test_node结构体中的偏移地址,找到散列表节点实际指向的结构体首地址*/ node_temp = container(node->key, struct test_node, key); /*如果节点所指向数据空间为动态申请的则需要释放*/ HASH_TABLE_FREE(node_temp); return 0; } struct hash_table *hash_table_test; char table_node_read[5][10]; void hash_table_sample(void) { int i = 0; struct test_node *node_temp = NULL; char rd_key[10] = {10}, del_key[10] = {0}; char *temp = NULL; hash_table_test = hash_table_creat_default(5, node_value_free_sample); /*插入 -- 查询*/ for (i=0; i<5; i++) { node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp)); memset(node_temp, 0, sizeof(*node_temp)); sprintf(node_temp->key, "AAA%d", i); sprintf(node_temp->value, "%d", i+10); hash_table_insert(hash_table_test, node_temp->key, node_temp->value); } for (i=0; i<5; i++) { sprintf(rd_key, "AAA%d", i); temp = hash_table_search(hash_table_test, rd_key); memcpy(table_node_read[i], temp, 10); } /*修改 -- 查询*/ for (i=0; i<5; i++) { node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp)); memset(node_temp, 0, sizeof(*node_temp)); sprintf(node_temp->key, "AAA%d", i); sprintf(node_temp->value, "%d", i+20); hash_table_modify(hash_table_test, node_temp->key, node_temp->value); } for (i=0; i<5; i++) { sprintf(rd_key, "AAA%d", i); temp = hash_table_search(hash_table_test, rd_key); memcpy(table_node_read[i], temp, 10); } /*删除 -- 查询*/ for (i=0; i<3; i++) { sprintf(del_key, "AAA%d", i); hash_table_delete(hash_table_test, del_key); } for (i=0; i<5; i++) { temp = NULL; memset(table_node_read[i], 0, 10); sprintf(rd_key, "AAA%d", i); temp = hash_table_search(hash_table_test, rd_key); if (temp != NULL) { memcpy(table_node_read[i], temp, 10); } } }
-
浅析全域哈希和完全哈希(c语言实现)
2014-03-05 22:29:31先简单介绍下哈希函数 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做... -
常用哈希函数结构 数据结构
2009-05-07 11:12:10目前比较有名的哈希函数 C语言 数据结构 -
用C语言实现SHA1哈希函数
2015-01-12 09:26:39用C语言实现SHA1哈希函数,它将文件的每一行进行加密,输出160位的哈希值 -
用C语言实现MD5哈希函数
2015-01-12 09:24:04用C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。 -
C语言哈希函数库murmur3.zip
2019-07-17 03:52:57这是 Murmur3 哈希函数的 C 语言移植版本,Murmur3 是一个非加密的哈希算法,主要设计目的是快速和高质量,原有代码是 C 的,先移植到 C 并兼容标准 C 和 gcc 编译器。 标签:murmur3 -
常用哈希函数的比较及其C语言实现
2015-07-22 23:36:23所谓完美哈希函数,就是指没有冲突的哈希函数,即对任意的 key1 != key2 有h(key1) != h(key2)。 设定义域为X,值域为Y, n=|X|,m=|Y|,那么肯定有m>=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2),那么称h为... -
散列/哈希查找 C语言实现
2013-12-16 16:12:131、基本概念 散列(hash)同顺序、链接和索引一样,是存储数据的又一种方法。 散列存储的基本思想是:以数据(通常为集合)...散列存储中使用的函数h(K),称为散列函数或哈希函数,它实现关键字到存储地址的映射(或称转 -
用C语言实现常用的字符串哈希函数
2015-01-12 09:43:34用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等 -
经常使用哈希函数的比較及其C语言实现
2016-04-16 10:19:00基本概念 所谓完美哈希函数。就是指没有冲突的哈希函数。即对随意的 key1 != key2 有h(key1) !...=h(key2),那么称h为完美哈希函数,当m=n时,h称为最小完美哈希函数(这个时候就是一一映射了)。 在处理大... -
SHA256 摘要算法 、HMAC_SHA256 散列/哈希算法 C语言实现,适应于各种嵌入式单片机
2019-05-17 09:46:55/*此函数用于对消息计算摘要值,输入任意大小消息,输出32字节摘要值*/ void hmac_sha256_get(uint8_t digest[32], uint8_t *message, int message_length, uint8_t *key, int key_length);/*此函数用于HMAC_SHA256... -
c语言哈希表电子辞典_哈希表的C语言实现
2020-12-21 15:56:34说到哈希表,首先就得说到哈希函数,哈希函数是用来得到给定key值的在哈希表中的存储位置的。哈希函数也并不是固定的,可以自己根据情况来定,一般常用常见的有直接定制法,除留余数法,平方取中法,折叠法,随机数... -
【C语言】哈希函数写法、字符串深度复制
2016-05-15 13:28:00除此之外,[1]还对常用字符串哈希函数 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash进行了量化比较。 1.2 哈希函数分类 [2]中把哈希函数分为如下几类: 加法Hash; 位运算Hash;... -
完美哈希函数的实现
2011-12-16 10:58:17用C++实现的完美哈希函数,打印C语言的32个关键字的哈希值,并且判断所输入的字符串是否为关键字 -
哈希表,哈希算法(C语言)
2017-08-15 16:17:31哈希表哈希表,又称散列表,常用于在海量数据中查找数据哈希表中元素是由哈希函数确定的。将数据元素的关键字key作为自变量,通过一定的函数关系H(称为哈希函数),计算出的值,即为该元素的存储地址。其优点是:运算... -
哈希查找-C语言
2019-01-07 14:23:55六种哈希函数的构造方法: (1)直接定址法 函数公式:f(key) = a * key + b(a,b为常数) 这种方法的优点是:简单、均匀,不会产生冲突。但是需要事先知道关键字的分布情况,适合查找表较小并且连续的... -
哈希表的C语言实现
2019-06-16 22:47:282.哈希表的哈希函数; 3.哈希表的冲突问题解决;什么叫做闭散列,什么叫做开散列;闭,严重遵守哈希内涵。开,有点开放的意味,解决冲突靠链表,有点变味的哈希; 二、相关数据结构解读: ... -
数据结构哈希表(c语言)
2020-12-27 17:52:03决定一个哈希表的主要是哈希函数与处理冲突的方法。而按照设定的哈希函数和处理冲突的方法将一组关键字key 映射到有限的地址集合中,这就是哈希表。 哈希函数构造方法 直接定义法:代码块如下: int hash1(int key)... -
数据结构与算法之哈希表(C语言版)
2020-07-21 15:43:05title: 数据结构与算法之哈希表(C语言版) date: 2020-07-19 21:05:15 ...绝大多数的哈希函数会将一些不同的键映射到表中相同的槽位上,当两个键映射到一个相同的槽位上时,即产生了冲突。优秀的哈希函数. -
数据结构---哈希表的C语言实现
2018-03-06 17:58:46说到哈希表,,首先就得说到哈希函数,哈希函数是用来得到给定key值的在哈希表中的存储位置的。 哈希函数也并不是固定的,可以自己根据情况来定,一般常用常见的有直接定制法,除留余数法,平方取中法,折叠法,... -
哈希表(C语言)
2020-12-13 21:15:56哈希表 哈希表又称散列表,是一种是“key-value"形式存储的数据结构。即将key映射到表上的一个单元,从而实现快速查找等操作,这个映射操作就叫散列,具体通过散列函数实现相应的映射。根据key的形式,散列的形式... -
【数据结构】哈希表(C语言)
2020-08-05 10:17:06结构操作可以分为哈希函数和冲突处理 1.哈希函数 通过数组下标访问value时间复杂度O(1) 数组的下标是整型数值 ,如果我们将任意类型的元素映射成整型,那么我们就可以直接访问下标 数值–>通过哈希函数的映射–&... -
散列表/哈希表(C语言简单实现)
2020-11-24 15:48:37散列表/哈希表(C语言简单实现) 本文参考自《大话数据结构》 定义 通过某个函数f计算出记录的存储位置,...我们把这种对应关系f称为散列函数,又称为哈希函数。按照这个思路,采用散列技术将记录存储在一块连续的存储 -
C语言 哈希表
2018-06-14 10:52:26哈希函数 哈希冲突 拉链法 代码实现 线性探测法 代码实现 哈希表简介 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。 哈希函数 得到一个数的... -
数据结构---哈希表的C语言实现(闭散列)
2019-07-22 19:26:00构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系... 说到哈希表,,首先就得说到哈希函数,哈希函数是用来得到给定key值的在哈希表中的存储位置的。 哈希函数也...