精华内容
下载资源
问答
  • 各种哈希函数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);
    }

    转载自:https://www.byvoid.com/blog/string-hash-compare/

    展开全文
  • 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;
    }
    
    展开全文
  • 哈希表初理解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:41
    2、操作函数声明 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、数据结构

    2、操作函数声明

    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);
    #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);
            }
        }
    }

     

     

    展开全文
  • 先简单介绍下哈希函数 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做...
  • 目前比较有名的哈希函数 C语言 数据结构
  • C语言实现SHA1哈希函数,它将文件的每一行进行加密,输出160位的哈希值
  • C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。
  • 这是 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:13
    1、基本概念 散列(hash)同顺序、链接和索引一样,是存储数据的又一种方法。 散列存储的基本思想是:以数据(通常为集合)...散列存储中使用的函数h(K),称为散列函数或哈希函数,它实现关键字到存储地址的映射(或称转
  • C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等
  • 基本概念 所谓完美哈希函数。就是指没有冲突的哈希函数。即对随意的 key1 != key2 有h(key1) !...=h(key2),那么称h为完美哈希函数,当m=n时,h称为最小完美哈希函数(这个时候就是一一映射了)。 在处理大...
  • /*此函数用于对消息计算摘要值,输入任意大小消息,输出32字节摘要值*/ void hmac_sha256_get(uint8_t digest[32], uint8_t *message, int message_length, uint8_t *key, int key_length);/*此函数用于HMAC_SHA256...
  • 说到哈希表,首先就得说到哈希函数哈希函数是用来得到给定key值的在哈希表中的存储位置的。哈希函数也并不是固定的,可以自己根据情况来定,一般常用常见的有直接定制法,除留余数法,平方取中法,折叠法,随机数...
  • 除此之外,[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:28
    2.哈希表的哈希函数; 3.哈希表的冲突问题解决;什么叫做闭散列,什么叫做开散列;闭,严重遵守哈希内涵。开,有点开放的意味,解决冲突靠链表,有点变味的哈希; 二、相关数据结构解读: ...
  • 决定一个哈希表的主要是哈希函数与处理冲突的方法。而按照设定的哈希函数和处理冲突的方法将一组关键字key 映射到有限的地址集合中,这就是哈希表。 哈希函数构造方法 直接定义法:代码块如下: int hash1(int key)...
  • title: 数据结构与算法之哈希表(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的形式,散列的形式...
  • 结构操作可以分为哈希函数和冲突处理 1.哈希函数 通过数组下标访问value时间复杂度O(1) 数组的下标是整型数值 ,如果我们将任意类型的元素映射成整型,那么我们就可以直接访问下标 数值–>通过哈希函数的映射–&...
  • 散列表/哈希表(C语言简单实现) 本文参考自《大话数据结构》 定义 通过某个函数f计算出记录的存储位置,...我们把这种对应关系f称为散列函数,又称为哈希函数。按照这个思路,采用散列技术将记录存储在一块连续的存储
  • C语言 哈希

    2018-06-14 10:52:26
    哈希函数 哈希冲突 拉链法 代码实现 线性探测法 代码实现 哈希表简介 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。 哈希函数 得到一个数的...
  • 构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系... 说到哈希表,,首先就得说到哈希函数哈希函数是用来得到给定key值的在哈希表中的存储位置的。 哈希函数也...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 235
精华内容 94
关键字:

哈希函数c语言

c语言 订阅