一文读懂哈希算法（Hash）竞猜游戏开发的特性

哈希函数是一个公共函数，它可以将任何长度M的消息映射到一个、散列值（Hash Value）、杂凑值或者消息摘要。它是一种单向密码系统，即从明文到密文的不可逆映射。只有一个加密过程，但没有解密过程。

1、单调性（Monotonicity）：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

　　
2、负载（Load）：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同
的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

3、平衡性（Balance）：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

4、分散性（Spread）：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同
，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分
散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

/*

 * @Author: Carlos

 * @Date: 2020-07-2 23:48:50

 * @LastEditTime: 2020-07-2 23:48:50

 * @LastEditors: Carlos

 * @Description: Hash

 */

#include “stdio.h”

#include “stdlib.h”

#define HASHSIZE 7 //定义散列表长为数组的长度

#define NULLKEY -1

typedef struct

{

    int *elem; //数据元素存储地址，动态分配数组

    int count; //当前数据元素个数

} HashTable;

/**

 * @Description: 哈希函数初始化

 * @Param: HashTable *hashTable 结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void Init(HashTable *hashTable)

{

    int i;

    hashTable->elem = (int *)malloc(HASHSIZE * sizeof(int));

    hashTable->count = HASHSIZE;

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

    {

        hashTable->elem[i] = NULLKEY;

    }

}

/**

 * @Description: 哈希函数(除留余数法)

 * @Param: int data 哈希的数据

 * @Return: 哈希后data存储的地址

 * @Author: Carlos

 */

int Hash(int data)

{

    return data % HASHSIZE;

}

/**

 * @Description: 哈希表的插入函数，可用于构造哈希表

 * @Param: HashTable *hashTable 结构体指针，int data 哈希的数据

 * @Return: 无

 * @Author: Carlos

 */

void Insert(HashTable *hashTable, int data)

{

    int hashAddress = Hash(data); //求哈希地址

    //发生冲突

    while (hashTable->elem[hashAddress] != NULLKEY)

    {

        //利用开放定址法解决冲突

        hashAddress = (++hashAddress) % HASHSIZE;

    }

    hashTable->elem[hashAddress] = data;

}

/**

 * @Description: 哈希表的查找算法

 * @Param: HashTable *hashTable 结构体指针，int data 哈希的数据

 * @Return: 无

 * @Author: Carlos

 */

int Search(HashTable *hashTable, int data)

{

    int hashAddress = Hash(data); //求哈希地址

    while (hashTable->elem[hashAddress] != data)

    { //发生冲突

        //利用开放定址法解决冲突

        hashAddress = (++hashAddress) % HASHSIZE;

        //如果查找到的地址中数据为NULL，或者经过一圈的遍历回到原位置，则查找失败

        if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data))

        {

            return -1;

        }

    }

    return hashAddress;

}

int main()

{

    int i, result;

    HashTable hashTable;

    int arr[HASHSIZE] = {13, 29, 27, 28, 26, 30, 38};

    //初始化哈希表

    Init(&hashTable);

    //利用插入函数构造哈希表

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

    {

        Insert(&hashTable, arr[i]);

    }

    //调用查找算法

    result = Search(&hashTable, 29);

    if (result == -1)

        printf(“查找失败“);

    else

        printf(“29 在哈希表中的位置是:%d”, result + 1);

    return 0;

}