简单HashTable(取模法)

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable
//http://www.cunmou.com/phpbook/preface.md
//http://wiki.swoole.com/wiki/index/prid-7
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

int main(int argc, char const *argv[])
{
    HashTable *h = (HashTable *)malloc(sizeof(HashTable));
    hash_init(h);

    char * str1 = "key1";
    char * str2 = "key2";
    char * str3 = "key3";
    char * str4 = "key4";
    char * str5 = "key5";
    char * str6 = "key6";
    char * str7 = "key7";
    char * str8 = "key8";

    int num1 = 1;
    int num2 = 2;
    int num3 = 3;
    int num4 = 4;
    int num5 = 5;
    int num6 = 6;
    int num7 = 7;
    int num8 = 8;

    hash_insert(h, str1, &num1);
    hash_insert(h, str2, &num2);
    hash_insert(h, str3, &num3);
    hash_insert(h, str4, &num4);
    hash_insert(h, str5, &num5);
    hash_insert(h, str6, &num6);
    hash_insert(h, str7, &num7);
    hash_insert(h, str8, &num8);

    int *num11 = NULL;
    int *num22 = NULL;
    int *num33 = NULL;
    int *num44 = NULL;
    int *num55 = NULL;
    int *num66 = NULL;
    int *num77 = NULL;
    int *num88 = NULL;

    hash_lookup(h, str1, (void **)&num11);
    hash_lookup(h, str2, (void **)&num22);
    hash_lookup(h, str3, (void **)&num33);
    hash_lookup(h, str4, (void **)&num44);
    hash_lookup(h, str5, (void **)&num55);
    hash_lookup(h, str6, (void **)&num66);
    hash_lookup(h, str7, (void **)&num77);
    hash_lookup(h, str8, (void **)&num88);

    printf("find result key=%s value=%d \n", str1, *num11);
    printf("find result key=%s value=%d \n", str2, *num22);
    printf("find result key=%s value=%d \n", str3, *num33);
    printf("find result key=%s value=%d \n", str4, *num44);
    printf("find result key=%s value=%d \n", str5, *num55);
    printf("find result key=%s value=%d \n", str6, *num66);
    printf("find result key=%s value=%d \n", str7, *num77);
    printf("find result key=%s value=%d \n", str8, *num88);
 
    hash_destroy(h);
    return 0;
}

//参考：http://www.php-internals.com/book/?p=chapt03/03-01-01-hashtable

//http://www.cunmou.com/phpbook/preface.md

//http://wiki.swoole.com/wiki/index/prid-7

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

int main(int argc, char const *argv[])

{

HashTable *h = (HashTable *)malloc(sizeof(HashTable));

hash_init(h);

char * str1 = "key1";

char * str2 = "key2";

char * str3 = "key3";

char * str4 = "key4";

char * str5 = "key5";

char * str6 = "key6";

char * str7 = "key7";

char * str8 = "key8";

int num1 = 1;

int num2 = 2;

int num3 = 3;

int num4 = 4;

int num5 = 5;

int num6 = 6;

int num7 = 7;

int num8 = 8;

hash_insert(h, str1, &num1);

hash_insert(h, str2, &num2);

hash_insert(h, str3, &num3);

hash_insert(h, str4, &num4);

hash_insert(h, str5, &num5);

hash_insert(h, str6, &num6);

hash_insert(h, str7, &num7);

hash_insert(h, str8, &num8);

int *num11 = NULL;

int *num22 = NULL;

int *num33 = NULL;

int *num44 = NULL;

int *num55 = NULL;

int *num66 = NULL;

int *num77 = NULL;

int *num88 = NULL;

hash_lookup(h, str1, (void **)&num11);

hash_lookup(h, str2, (void **)&num22);

hash_lookup(h, str3, (void **)&num33);

hash_lookup(h, str4, (void **)&num44);

hash_lookup(h, str5, (void **)&num55);

hash_lookup(h, str6, (void **)&num66);

hash_lookup(h, str7, (void **)&num77);

hash_lookup(h, str8, (void **)&num88);

printf("find result key=%s value=%d \n", str1, *num11);

printf("find result key=%s value=%d \n", str2, *num22);

printf("find result key=%s value=%d \n", str3, *num33);

printf("find result key=%s value=%d \n", str4, *num44);

printf("find result key=%s value=%d \n", str5, *num55);

printf("find result key=%s value=%d \n", str6, *num66);

printf("find result key=%s value=%d \n", str7, *num77);

printf("find result key=%s value=%d \n", str8, *num88);

hash_destroy(h);

return 0;

}

#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容
#define HASH_TABLE_INIT_SIZE 6
//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)
//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作
#if defined(DEBUG)
#  define LOG_MSG printf
#else
#  define LOG_MSG(...)
#endif

#define SUCCESS 0
#define FAILED -1

typedef struct _Bucket
{
    char *key;                  //字符串key
    void *value;                //value指针，直接操作传入的指针，不返回value值
    struct _Bucket *next;
} Bucket;

typedef struct _HashTable
{
    int size;                    // 哈希表的大小
    int elem_num;                // 已经保存元素的个数
    Bucket **buckets;            // bucket指针数组
} HashTable;

int hash_init(HashTable *ht);
//**result(参数为二级指针，因为需要传入指针的引用)
int hash_lookup(HashTable *ht, char *key, void **result);
int hash_insert(HashTable *ht, char *key, void *value);
int hash_remove(HashTable *ht, char *key);
int hash_destroy(HashTable *ht);
#endif

#ifndef _HASH_TABLE_H_

#define _HASH_TABLE_H_

//初始化hashtable的默认长度，当hashtable的实际长度超过HASH_TABLE_INIT_SIZE时会以2倍的方式扩容

#define HASH_TABLE_INIT_SIZE 6

//以下宏配合hashtable.c中的hash_str函数，可以计算hash值(取模法)

#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

//如果定义了DEBUG常量，则LOG_MSG会使用printf，否则是一个空操作

#if defined(DEBUG)

# define LOG_MSG printf

#else

# define LOG_MSG(...)

#endif

#define SUCCESS 0

#define FAILED -1

typedef struct _Bucket

{

char *key; //字符串key

void *value; //value指针，直接操作传入的指针，不返回value值

struct _Bucket *next;

} Bucket;

typedef struct _HashTable

{

int size; // 哈希表的大小

int elem_num; // 已经保存元素的个数

Bucket **buckets; // bucket指针数组

} HashTable;

int hash_init(HashTable *ht);

//**result(参数为二级指针，因为需要传入指针的引用)

int hash_lookup(HashTable *ht, char *key, void **result);

int hash_insert(HashTable *ht, char *key, void *value);

int hash_remove(HashTable *ht, char *key);

int hash_destroy(HashTable *ht);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtable.h"
//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法
static void resize_hash_table_if_needed(HashTable *ht);
//将字符串key转换成数字(每个字符的ASCII累加)
static int hash_str(char *key);
//哈希表扩容方法，将哈希表扩容2倍
static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)
{
    ht->size 		= HASH_TABLE_INIT_SIZE;
    ht->elem_num 	= 0;
    ht->buckets		= (Bucket **)calloc(ht->size, sizeof(Bucket *));
    //分配内存失败，直接返回错误
    if(ht->buckets == NULL) return FAILED;
    LOG_MSG("[init]\tsize: %d\n", ht->size);
    return SUCCESS;
}

int hash_lookup(HashTable *ht, char *key, void **result)
{
    //把字符串的每个字符的ascii码累加后和hash表的size取模
    int index = HASH_INDEX(ht, key);
    //从buckets中获取bucket指针
    Bucket *bucket = ht->buckets[index];
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            *result = bucket->value;
            return SUCCESS;
        }
        bucket = bucket->next;
    }
    LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);
    return FAILED;
}

int hash_insert(HashTable *ht, char *key, void *value)
{
    resize_hash_table_if_needed(ht);
    int index = HASH_INDEX(ht, key);
    Bucket *org_bucket = ht->buckets[index];
    Bucket *tmp_bucket = org_bucket;
    while(tmp_bucket)
    {
        if(strcmp(key, tmp_bucket->key) == 0)
        {
            tmp_bucket->value = value;
            return SUCCESS;
        }
        tmp_bucket = tmp_bucket->next;
    }
    Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));
    bucket->key	  = key;
    bucket->value = value;
    bucket->next  = NULL;
    ht->elem_num++;
    if(org_bucket != NULL)
    {
        LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);
        bucket->next = org_bucket;
    }
    ht->buckets[index] = bucket;
    LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);
    return SUCCESS;
}

int hash_remove(HashTable *ht, char *key)
{
    int index = HASH_INDEX(ht, key);
    Bucket *bucket  = ht->buckets[index];
    Bucket *prev	= NULL;
    if(bucket == NULL) return FAILED;
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);
            if(prev == NULL)
            {
                ht->buckets[index] = bucket->next;
            }
            else
            {
                prev->next = bucket->next;
            }
            free(bucket);
            ht->elem_num--;
            return SUCCESS;
        }
        prev   = bucket;
        bucket = bucket->next;
    }
    LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);
    return FAILED;
}

int hash_destroy(HashTable *ht)
{
    int i;
    Bucket *cur = NULL;
    Bucket *tmp = NULL;
    for(i = 0; i < ht->size; ++i)
    {
        cur = ht->buckets[i];
        while(cur)
        {
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(ht->buckets);
    free(ht);
    return SUCCESS;
}

static int hash_str(char *key)
{
    int hash = 0;

    char *cur = key;

    while(*cur != '\0')
    {
        hash +=	*cur;
        ++cur;
    }

    return hash;
}

static int hash_resize(HashTable *ht)
{
    int org_size = ht->size;
    ht->size = ht->size * 2;
    ht->elem_num = 0;
    LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);
    Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
    Bucket **org_buckets = ht->buckets;
    ht->buckets = buckets;
    int i = 0;
    for(i = 0; i < org_size; ++i)
    {
        Bucket *cur = org_buckets[i];
        Bucket *tmp;
        //循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)
        while(cur)
        {
            hash_insert(ht, cur->key, cur->value);
            tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(org_buckets);
    LOG_MSG("[resize] done\n");
    return SUCCESS;
}

static void resize_hash_table_if_needed(HashTable *ht)
{
    if(ht->size - ht->elem_num < 1)
    {
        hash_resize(ht);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "hashtable.h"

//设置key时，检查下哈希表是否已满，已满的话，调用hash_resize方法

static void resize_hash_table_if_needed(HashTable *ht);

//将字符串key转换成数字(每个字符的ASCII累加)

static int hash_str(char *key);

//哈希表扩容方法，将哈希表扩容2倍

static int hash_resize(HashTable *ht);

int hash_init(HashTable *ht)

{

ht->size = HASH_TABLE_INIT_SIZE;

ht->elem_num = 0;

ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

//分配内存失败，直接返回错误

if(ht->buckets == NULL) return FAILED;

LOG_MSG("[init]\tsize: %d\n", ht->size);

return SUCCESS;

}

int hash_lookup(HashTable *ht, char *key, void **result)

{

//把字符串的每个字符的ascii码累加后和hash表的size取模

int index = HASH_INDEX(ht, key);

//从buckets中获取bucket指针

Bucket *bucket = ht->buckets[index];

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

*result = bucket->value;

return SUCCESS;

}

bucket = bucket->next;

}

LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);

return FAILED;

}

int hash_insert(HashTable *ht, char *key, void *value)

{

resize_hash_table_if_needed(ht);

int index = HASH_INDEX(ht, key);

Bucket *org_bucket = ht->buckets[index];

Bucket *tmp_bucket = org_bucket;

while(tmp_bucket)

{

if(strcmp(key, tmp_bucket->key) == 0)

{

tmp_bucket->value = value;

return SUCCESS;

}

tmp_bucket = tmp_bucket->next;

}

Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));

bucket->key = key;

bucket->value = value;

bucket->next = NULL;

ht->elem_num++;

if(org_bucket != NULL)

{

LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);

bucket->next = org_bucket;

}

ht->buckets[index] = bucket;

LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n", index, key, ht->elem_num);

return SUCCESS;

}

int hash_remove(HashTable *ht, char *key)

{

int index = HASH_INDEX(ht, key);

Bucket *bucket = ht->buckets[index];

Bucket *prev = NULL;

if(bucket == NULL) return FAILED;

while(bucket)

{

if(strcmp(bucket->key, key) == 0)

{

LOG_MSG("[remove]\tkey:(%s) index: %d\n", key, index);

if(prev == NULL)

{

ht->buckets[index] = bucket->next;

}

else

{

prev->next = bucket->next;

}

free(bucket);

ht->elem_num--;

return SUCCESS;

}

prev = bucket;

bucket = bucket->next;

}

LOG_MSG("[remove]\t key:%s not found remove \tfailed\t\n", key);

return FAILED;

}

int hash_destroy(HashTable *ht)

{

int i;

Bucket *cur = NULL;

Bucket *tmp = NULL;

for(i = 0; i < ht->size; ++i)

{

cur = ht->buckets[i];

while(cur)

{

tmp = cur;

cur = cur->next;

free(tmp);

}

free(ht->buckets);

free(ht);

return SUCCESS;

}

static int hash_str(char *key)

{

int hash = 0;

char *cur = key;

while(*cur != '\0')

{

hash += *cur;

++cur;

}

return hash;

}

static int hash_resize(HashTable *ht)

{

int org_size = ht->size;

ht->size = ht->size * 2;

ht->elem_num = 0;

LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);

Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));

Bucket **org_buckets = ht->buckets;

ht->buckets = buckets;

int i = 0;

for(i = 0; i < org_size; ++i)

{

Bucket *cur = org_buckets[i];

Bucket *tmp;

//循环将原先的bucket指针删除，然后重新插入(因为扩容后，需要重新取模定位)

while(cur)

{

hash_insert(ht, cur->key, cur->value);

tmp = cur;

cur = cur->next;

free(tmp);

}

free(org_buckets);

LOG_MSG("[resize] done\n");

return SUCCESS;

}

static void resize_hash_table_if_needed(HashTable *ht)

{

if(ht->size - ht->elem_num < 1)

{

hash_resize(ht);

}

all:
	#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到
	gcc -DDEBUG main.c hashtable.c -o hashtable.out
test: all
	./hashtable.out
clean:
	rm -rf hashtable.out

all:

#-DDEBUG指定常量DEBUG，hashtable.h中 #if defined(DEBUG) 有用到

gcc -DDEBUG main.c hashtable.c -o hashtable.out

test: all

./hashtable.out

clean:

rm -rf hashtable.out

唐晓锋–BLOG

This is just a personal note.

发表评论取消回复

发表评论 取消回复

发表评论取消回复