HASH 算法--联系人查找

hash算法原理本文就不累赘讲述了，百度/google一下就知道了。

本demo程序实现一个简单的联系人hash表，通过姓名查找联系人：
1. hash函数采用简单的姓名字母累加和，通过掩码映射的方式获取hash-key；
2. 冲突解决采用链式散列；
3.由于联系人姓名（拼音）累加和分布相对集中（几百到两千左右），因此该hash表容量一般小于2000冲突较少，如果联系人数量较多，该hash函数冲突会增加。

/**
* 联系人hash表实现demo
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct HashTableEntry {
    int flag;
    int nextIndex;
    int prveIndex;
    char* name;
};

struct PeopleHashTable {
    unsigned int size;
    unsigned int entrys;
    struct HashTableEntry *datas;
};

enum EntryFlag {
    STATE_UNUSED = 0,
    STATE_HASH_USED,
    STATE_COLLISION_USED
};

int getUpperSize(int size)
{
    int upperSize = 1;

    if (size <= 0)
        return 1;

    while (upperSize < size)
        upperSize <<= 1;

    return upperSize;

}

int getHashKey(struct PeopleHashTable *table, const char *name)
{
    char *ptr;
    unsigned key = 0;

    if (NULL == name)
        return -1;

    ptr = name;

    while ('\0' != *ptr)
    {
        key += *ptr;
        ptr++;
    }

    printf("sum of %s: [%d], and key : [%d]\n",name, key, key & (table->size -1));
    if (NULL == table)
        return key;

    return (key & (table->size -1));
}

int insert2Table(struct PeopleHashTable *table, char *name)
{
    int key = 0;
    struct HashTableEntry *entry;
    struct HashTableEntry *tmp;

    int i;

    if (NULL == table)
        return -1;

    if (table->entrys == table->size)
    {
        printf("table is full, can NOT insert only more!\n");
        return -1;
    }

    key = getHashKey(table, name);
    entry = &(table->datas[key]);

    if (entry->flag == STATE_UNUSED)
    {
        entry->flag = STATE_HASH_USED;
        entry->name = name;
        table->entrys++;
        return 0;
    }

    if (entry->flag == STATE_HASH_USED)
    {
        // find a useable entry
        for (i = 0; i < table->size; i++)
        {
            if (table->datas[i].flag == STATE_UNUSED)
                break;
        }

        // find if entry has a collision entry
        while( entry->nextIndex != -1)
        {
            entry = &table->datas[entry->nextIndex];
        }

        tmp = &(table->datas[i]);

        tmp->flag = STATE_COLLISION_USED;
        tmp->name = name;
        tmp->prveIndex = key;

        entry->nextIndex = i;
        table->entrys++;
        return 0;
    }

    if (entry->flag == STATE_COLLISION_USED)
    {
        // find a useable entry
        for (i = 0; i < table->size; i++)
        {
            if (table->datas[i].flag == STATE_UNUSED)
                break;
        }

        // remove current entry to the empty entry space
        tmp = &table->datas[entry->prveIndex];
        tmp->nextIndex = i;

        tmp = &table->datas[i];
        tmp->prveIndex = entry->prveIndex;
        tmp->flag = entry->flag;
        tmp->name = entry->name;
        tmp->nextIndex = entry->nextIndex;

        entry->flag = STATE_HASH_USED;
        entry->name = name;
        entry->prveIndex = -1;
        entry->nextIndex = -1;

        table->entrys++;
        return 0;
    }

    return -1;
}

struct HashTableEntry* findPeople(struct PeopleHashTable *table, char *name)
{
    int key;
    struct HashTableEntry *entry = NULL;

    if (NULL == table)
        return NULL;

    key = getHashKey(table, name);

    entry = &table->datas[key];
    if (entry->name != NULL && !strcmp(entry->name, name))
    {
        return entry;
    }

    while(entry)
    {
        if (entry->name && !strcmp(entry->name, name))
            return entry;

        if (entry->nextIndex != -1)
            entry = &table->datas[entry->nextIndex];
        else
            return NULL;
    }
    return NULL;
}

int createHashTable(struct PeopleHashTable **table, unsigned int size)
{
    int upperSize = getUpperSize(size);

    struct PeopleHashTable *tablePtr = NULL;
    struct HashTableEntry *entryList = NULL;
    int i;

    tablePtr = (struct PeopleHashTable*)malloc(sizeof(*tablePtr));
    if (NULL == tablePtr)
        return -1;

    entryList = (struct HashTableEntry*)malloc(sizeof(*entryList) * upperSize);
    if (NULL == entryList)
    {
        free(tablePtr);
        return -1;
    }
    memset(entryList, 0, sizeof(*entryList) * upperSize);
    for(i = 0; i < upperSize; i++)
    {
        entryList[i].flag = STATE_UNUSED;
        entryList[i].name = NULL;
        entryList[i].nextIndex = -1;
        entryList[i].prveIndex = -1;
    }

    tablePtr->datas = entryList;
    tablePtr->entrys = 0;
    tablePtr->size = upperSize;

    *table = tablePtr;

    return 0;
}

int destoryHashTable(struct PeopleHashTable *table)
{
    if (NULL == table)
        return 0;

    free(table->datas);
    free(table);

    return 0;
}

static void debug_print_table(struct PeopleHashTable *table)
{
    int i;

    printf("table infos:\n");
    printf("size: [%d], entry numbers;[%d]\n", table->size,table->entrys);
    printf("index flag prve next name\n");
    for (i = 0; i < table->size; i++)
    {
        printf("%5d%5d%5d%5d %s\n", i,table->datas[i].flag ,table->datas[i].prveIndex, table->datas[i].nextIndex, table->datas[i].name == NULL ? "--" :table->datas[i].name);
    }
}
/*
void main()
{
    char *peoples[30]= {
        "刘敏",
        "wang wu",
        "li si",
        "liu yu gu",
        "jiang jie hui",
        "tan wei wei",
        "liu tao",
        "mi yue",
        "mi shu",
        "yin si",
        "yin dang",
        "huang zi",
        "zhang zi",
        "qu yuan",
        "tang jia jun",
        "gui wa zi",
        "qu li zi",
        "gong zhu",
        "tang hui",
        "jiu zhong",
        ""
    };

    struct PeopleHashTable *table;
    struct HashTableEntry *entry;

    int ret;
    int i;

    ret = createHashTable(&table, 20);

    if (ret < 0)
    {
        printf("create hash table fail\n");
        return;
    }

    i = 0;
    for (i = 0; i < 20; i++)
    {
        insert2Table(table,peoples[i]);
    }
    printf("-- add people done!\n");

    debug_print_table(table);


    entry = findPeople(table, "jiu zhong");
    if (entry != NULL)
    {
        printf("find!\n");
    }
    else
        printf("--no--\n");

    destoryHashTable(table);
    table = NULL;
}*/