除留余数法构造哈希表

除留余数法是一种常用的哈希函数构造方法，它可以将关键字映射到哈希表的索引位置上。具体步骤如下：

1. 首先，确定哈希表的大小，通常选择一个素数作为哈希表的大小，可以减少冲突的概率。

2. 对于给定的关键字，计算其除以哈希表大小的余数。这个余数就是该关键字在哈希表中的索引位置。

3. 将关键字存储在计算得到的索引位置上。如果该位置已经被占用，可以使用一定的冲突解决策略，比如线性探测法或链表法。

需要注意的是，除留余数法在某些情况下可能会导致冲突较多，特别是当关键字之间存在一定的规律或者集中分布时。因此，在实际应用中，可能需要结合其他哈希函数构造方法或者采用更复杂的哈希算法来减少冲突。

相关问题

（C语言版数据结构）实现哈希表的构造和查找算法，要求：用除留余数法构造哈希表，用链地址法解决冲突

以下是C语言版数据结构实现哈希表的构造和查找算法，使用除留余数法构造哈希表，用链地址法解决冲突：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 13 //哈希表长度

//定义哈希表节点
typedef struct HashNode {
    int key;
    struct HashNode *next;
} HashNode;

//定义哈希表
typedef struct HashTable {
    HashNode *head[MAXSIZE];
} HashTable;

//哈希函数
int HashFunction(int key) {
    return key % MAXSIZE;
}

//初始化哈希表
void HashInit(HashTable *hashTable) {
    for (int i = 0; i < MAXSIZE; i++) {
        hashTable->head[i] = NULL;
    }
}

//插入节点
void HashInsert(HashTable *hashTable, int key) {
    int index = HashFunction(key);
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = key;
    node->next = NULL;
    if (hashTable->head[index] == NULL) {
        hashTable->head[index] = node;
    } else {
        HashNode *p = hashTable->head[index];
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = node;
    }
}

//查找节点
HashNode *HashSearch(HashTable *hashTable, int key) {
    int index = HashFunction(key);
    HashNode *p = hashTable->head[index];
    while (p != NULL && p->key != key) {
        p = p->next;
    }
    return p;
}

//打印哈希表
void PrintHashTable(HashTable *hashTable) {
    for (int i = 0; i < MAXSIZE; i++) {
        printf("hashTable[%d]: ", i);
        HashNode *p = hashTable->head[i];
        while (p != NULL) {
            printf("%d ", p->key);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    HashTable hashTable;
    HashInit(&hashTable);
    int keys[] = {12, 3, 23, 14, 7, 8, 9, 10, 11, 5, 6, 16, 21};
    int n = sizeof(keys) / sizeof(keys[0]);
    for (int i = 0; i < n; i++) {
        HashInsert(&hashTable, keys[i]);
    }
    PrintHashTable(&hashTable);
    int key = 7;
    HashNode *node = HashSearch(&hashTable, key);
    if (node != NULL) {
        printf("Find key %d\n", key);
    } else {
        printf("Not find key %d\n", key);
    }
    return 0;
}

使用除留余数法作为哈希构造函数

除留余数法是一种简单的哈希函数构造方法，它将输入的关键字除以一个数并取余数作为哈希值。具体地，对于一个给定的关键字k和一个正整数m，除留余数法的哈希函数h(k)定义为 h(k) = k mod m。

使用除留余数法作为哈希函数的优点是简单、快速。但是，如果选择的m不合适，就会导致哈希冲突的发生，降低哈希表的性能。因此，在实际应用中，需要根据实际情况选取合适的m值，或采用其他的哈希函数构造方法。