散列函数：除留余数法代码

除留余数法是一种简单的散列函数，它可以将任意大小的输入数据映射为一个较小的固定大小的值。以下是除留余数法的代码实现：

def hash_function(key, table_size):
    # 将key转换为整数
    key = int(key)
    # 计算key对table_size取余数作为散列值
    hash_value = key % table_size
    return hash_value

其中，`key`是输入的关键字，`table_size`是散列表的大小。这个散列函数将`key`转换为整数，并将其对`table_size`取余数，得到的结果即为散列值。

相关问题

散列表线性探测法散列函数：除留余数法利用c++

散列表线性探测法是一种解决散列冲突的方法，其中散列函数是将键映射到散列表中的索引位置。除留余数法是一种常见的散列函数，它可以将键转换为一个整数，然后使用模运算将其映射到散列表中的索引位置。

以下是使用除留余数法实现散列表线性探测法的示例代码：

#include <iostream>
#include <cstring>
using namespace std;

const int SIZE = 10; //散列表大小
const int EMPTY = -1; //空位置标记

class HashTable {
private:
    int* table; //散列表
    int hash(int key); //散列函数
public:
    HashTable();
    void insert(int key);
    void remove(int key);
    void display();
};

//构造函数，初始化散列表
HashTable::HashTable() {
    table = new int[SIZE];
    memset(table, EMPTY, SIZE * sizeof(int));
}

//散列函数，除留余数法
int HashTable::hash(int key) {
    return key % SIZE;
}

//插入键到散列表中
void HashTable::insert(int key) {
    int index = hash(key); //计算散列值
    int i = index;
    do {
        if (table[i] == EMPTY) { //如果位置为空
            table[i] = key; //插入键
            return;
        }
        i = (i + 1) % SIZE; //线性探测
    } while (i != index); //回到起始位置，散列表已满
    cout << "散列表已满，插入失败！" << endl;
}

//从散列表中删除键
void HashTable::remove(int key) {
    int index = hash(key); //计算散列值
    int i = index;
    do {
        if (table[i] == key) { //如果找到键
            table[i] = EMPTY; //删除键
            return;
        }
        i = (i + 1) % SIZE; //线性探测
    } while (i != index); //回到起始位置，未找到键
    cout << "未找到键，删除失败！" << endl;
}

//显示散列表中的键
void HashTable::display() {
    for (int i = 0; i < SIZE; i++) {
        if (table[i] != EMPTY) {
            cout << table[i] << " ";
        }
    }
    cout << endl;
}

int main() {
    HashTable ht;
    ht.insert(3);
    ht.insert(7);
    ht.insert(11);
    ht.insert(22);
    ht.insert(31);
    ht.display();
    ht.remove(11);
    ht.remove(7);
    ht.display();
    ht.insert(33);
    ht.insert(44);
    ht.insert(55);
    ht.insert(66);
    ht.display();
    return 0;
}

在这个示例中，我们使用除留余数法作为散列函数，将键映射到散列表中的索引位置。如果该位置已经被占用，则使用线性探测法寻找下一个可用位置。当散列表已满时，插入操作将失败。删除操作将从散列表中删除键，并将其位置标记为空。显示操作将输出散列表中的所有键。

c语言基于散列表的工作原理，采用除留余数法H(key) = key % p (p<m) 作为散列函数，采用线性探测法处理冲突，实现散列查找算法代码

散列表（Hash Table）是一种以键值对（key-value）方式存储数据的数据结构。它通过散列函数将键映射到存储桶（bucket）中，从而实现快速的查找、插入和删除操作。

散列函数采用除留余数法，其中 p 是小于散列表容量 m 的最大质数。线性探测法是一种解决冲突的方法，当散列函数将两个不同的键映射到同一个存储桶时，线性探测法会按照一定的步长依次检查后续的存储桶，直到找到一个空的位置或者遍历完所有的存储桶为止。

下面是一个基于散列表的查找算法的 C 语言实现：

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

#define MAX_SIZE 100

// 散列表结构体
typedef struct HashTable {
    int *data;  // 存储数据的数组
    int size;   // 散列表容量
} HashTable;

// 初始化散列表
void initHashTable(HashTable *ht, int size) {
    ht->data = (int *)malloc(sizeof(int) * size);
    ht->size = size;
    for (int i = 0; i < size; i++) {
        ht->data[i] = -1;  // -1 表示该位置为空
    }
}

// 散列函数
int hash(int key, int p) {
    return key % p;
}

// 插入键值对
void insert(HashTable *ht, int key) {
    int index = hash(key, ht->size);
    if (ht->data[index] == -1) {
        ht->data[index] = key;
    } else {
        int i = 1;
        while (i < ht->size && ht->data[(index + i) % ht->size] != -1) {
            i++;
        }
        if (i == ht->size) {
            printf("散列表已满，无法插入数据\n");
            return;
        }
        ht->data[(index + i) % ht->size] = key;
    }
}

// 查找键值对
int search(HashTable *ht, int key) {
    int index = hash(key, ht->size);
    int i = 0;
    while (i < ht->size && ht->data[(index + i) % ht->size] != key) {
        i++;
    }
    if (i == ht->size) {
        return -1;
    }
    return (index + i) % ht->size;
}

int main() {
    HashTable ht;
    int size, n, key, index;
    printf("请输入散列表容量：");
    scanf("%d", &size);
    initHashTable(&ht, size);
    printf("请输入要插入的键值对个数：");
    scanf("%d", &n);
    printf("请输入 %d 个键值对：\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        insert(&ht, key);
    }
    printf("请输入要查找的键值对：");
    scanf("%d", &key);
    index = search(&ht, key);
    if (index == -1) {
        printf("未找到该键值对\n");
    } else {
        printf("该键值对在散列表中的位置为：%d\n", index);
    }
    return 0;
}

该程序首先定义了一个结构体 HashTable，包含一个指向存储数据的数组 data 和散列表容量 size。initHashTable 函数用于初始化散列表，将数组中所有位置的初始值设为 -1。hash 函数和 insert 函数实现了散列函数和插入键值对的功能。search 函数用于查找键值对，如果找到了该键值对则返回在散列表中的位置，否则返回 -1。

该程序通过输入散列表容量、键值对个数和键值对，可以实现散列查找算法。