功能：创建一个hash table。假设有处理冲突，则採用再散列法放置该元素

代码參考《零基础学数据结构》

代码例如以下：

root@ubuntu:/mnt/shared/appbox/hash# cat hash.c

#include <stdlib.h>

#include <stdio.h>

#include <unistd.h>

#include <malloc.h>

typedef int KeyType;

typedef struct

{

        KeyType key;    /* key value */

        int hi; /*  hash counts */

}DataType;

typedef struct

{

        DataType *data;

        int tableSize;  /* hash table len */

        int curSize;    /* key value numbers */

}HashTable;

void DisplayHash(HashTable *H, int m);

/*

* H:hash table pointer

* m: hashtable len

* p: devided numbers

* hash: be hashed data (src data)

* n: number of key values

*/

void CreateHash(HashTable *H, int m, int p, int hash[], int n)

{

        int i, sum, addr, di, k = 1;/* k: ͻ/

        H->data = (DataType *)malloc(m * sizeof(DataType));

        if(H->data == NULL)

        {

                printf("H->data is NULL!\n");

                return ;

        }

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

        {

                H->data[i].key = -1;

                H->data[i].hi = 0;

        }

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

        {

                sum = 0;

                addr = hash[i] % p;

                di = addr;

                if(H->data[addr].key == -1)

                {

                        H->data[addr].key = hash[i];

                        H->data[addr].hi = 1;

                        printf("[line:%d] addr:%d, i=%d, key=%d\n",__LINE__, addr, i, hash[i]);

                }

                else

                {

                        do

                        {

                                di = (di + k)%m;

                                sum += 1;

                        }while((H->data[di].key != -1));

                        H->data[di].key = hash[i];

                        H->data[di].hi = sum + 1;

                        printf("[line:%d] di:%d, i=%d, key=%d\n",__LINE__, di, i, hash[i]);

                }

        }

        H->curSize = n;

        H->tableSize = m;

        DisplayHash(H, m);

}

void DisplayHash(HashTable *H, int m)

{

        int i;

        printf("hash index:     ");

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

                printf("%-5d", i);

        printf("\n");

        printf("key value:      ");

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

                printf("%-5d", H->data[i].key);

        printf("\n");

        printf("hash times:     ");

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

                printf("%-5d", H->data[i].hi);

        printf("\n");

}

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

{

        int hash[] = {23, 35, 12, 56, 123, 39, 342, 90};

        int m=11, p=11, n=8, pos;

        HashTable H;

        CreateHash(&H, m, p, hash, n);

        return 0;

}

root@ubuntu:/mnt/shared/appbox/hash# 

输出结果：

root@ubuntu:/mnt/shared/appbox/hash# ./hash

[line:59] addr:1, i=0, key=23

[line:59] addr:2, i=1, key=35

[line:70] di:3, i=2, key=12

[line:70] di:4, i=3, key=56

[line:70] di:5, i=4, key=123

[line:59] addr:6, i=5, key=39

[line:70] di:7, i=6, key=342

[line:70] di:8, i=7, key=90

hash index:     0    1    2    3    4    5    6    7    8    9    10

key value:      -1   23   35   12   56   123  39   342  90   -1   -1

hash times:     0    1    1    3    4    4    1    7    7    0    0