哈希除留余数法、平方取中法、随机数法都是哈希的比较算法么

哈希算法是一种将任意长度的数据映射为固定长度的数据的算法，而除留余数法、平方取中法、随机数法等是哈希函数，是哈希算法中的一部分。哈希函数是哈希算法的关键部分，它决定了元素在哈希表中的位置。

除留余数法、平方取中法、随机数法等都是常见的哈希函数，它们的实现方式不同，适用于不同的场景。例如，除留余数法适用于哈希表大小为素数的情况，平方取中法适用于关键字长度较大的情况，随机数法适用于关键字分布均匀的情况。

因此，除留余数法、平方取中法、随机数法等都是哈希函数，是哈希算法的一部分，而不是哈希算法的比较算法。

相关问题

c语言实现哈希表（拉链法）*** 【基本要求】 （1）生成n个随机数或从键盘输入n个整数，并输出。 （2）采用除留余数法作为哈希函数 H(key)=key % p，选择适当的p。 （3）用拉链法处理冲突建立哈希表，并显示哈希表。 （4）分别计算成功和失败的平均查找长度。 （5）功能：检索（输出依次比较的数据）、插入、 删除。 【演示结果】 （1）输入查找表长度n，显示生成的n个随机数。 （2）哈希函数。 （3）显示哈希表，以及平均查找长度。 （4）输入查找数据，显示依次比较的数据、比较次数以及查找结果。 （5）输入插入数据，显示插入结果，以及平均查找长度。 （6）输入删除数据，显示删除结果，以及平均查找长度。 注意：以上功能应可多次操作。

好的，下面是C语言实现哈希表（拉链法）的代码，包括基本要求和演示结果的功能：

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

#define MAXSIZE 20 //哈希表长度
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

typedef int Status;
typedef int KeyType;
typedef struct {
    KeyType key;
    //其他数据项
} ElemType; //哈希表中存储的元素类型

typedef struct {
    ElemType *elem; //存储空间基址
    int count; //当前数据元素个数
} HashTable;

//初始化哈希表
Status InitHashTable(HashTable *H) {
    H->elem = (ElemType*) malloc(MAXSIZE * sizeof(ElemType));
    if (!H->elem) exit(0); //存储分配失败
    H->count = 0;
    for (int i = 0; i < MAXSIZE; i++) {
        H->elem[i].key = 0; //哈希表初始值为0，表示该位置没有数据
    }
    return SUCCESS;
}

//哈希函数
int Hash(KeyType key) {
    return key % 5; //选择p=5，采用除留余数法
}

//插入数据
Status Insert(HashTable *H, ElemType e) {
    int p = Hash(e.key);
    int c = 0; //计算查找次数
    while (H->elem[p].key != 0) { //该位置已有数据，发生冲突
        if (H->elem[p].key == e.key) return DUPLICATE; //数据已存在，返回重复标志
        p = (p + 1) % MAXSIZE; //线性探测下一位置
        c++;
    }
    H->elem[p] = e; //将数据插入哈希表
    H->count++;
    printf("Insert %d success, cost %d search.\n", e.key, c+1);
    return SUCCESS;
}

//查找数据
Status Search(HashTable H, KeyType key) {
    int p = Hash(key);
    int c = 0; //计算查找次数
    while (H.elem[p].key != 0) {
        if (H.elem[p].key == key) {
            printf("Search %d success, cost %d search.\n", key, c+1);
            return SUCCESS;
        }
        p = (p + 1) % MAXSIZE; //线性探测下一位置
        c++;
    }
    printf("Search %d failed, cost %d search.\n", key, c+1);
    return UNSUCCESS;
}

//删除数据
Status Delete(HashTable *H, KeyType key) {
    int p = Hash(key);
    int c = 0; //计算查找次数
    while (H->elem[p].key != 0) {
        if (H->elem[p].key == key) {
            H->elem[p].key = 0; //将该位置数据置为0，表示已删除
            H->count--;
            printf("Delete %d success, cost %d search.\n", key, c+1);
            return SUCCESS;
        }
        p = (p + 1) % MAXSIZE; //线性探测下一位置
        c++;
    }
    printf("Delete %d failed, cost %d search.\n", key, c+1);
    return UNSUCCESS;
}

//显示哈希表
void DisplayHashTable(HashTable H) {
    printf("HashTable:\n");
    for (int i = 0; i < MAXSIZE; i++) {
        printf("%d ", H.elem[i].key);
    }
    printf("\n");
}

//计算平均查找长度
float ASL(HashTable H, int n) {
    int sum = 0;
    for (int i = 0; i < MAXSIZE; i++) {
        if (H.elem[i].key != 0) sum++;
    }
    return (float)n / sum;
}

int main() {
    HashTable H;
    InitHashTable(&H);
    int n;
    printf("Input the size of hash table: ");
    scanf("%d", &n);
    printf("Input %d integers: ", n);
    for (int i = 0; i < n; i++) {
        ElemType e;
        scanf("%d", &e.key);
        Insert(&H, e);
    }
    DisplayHashTable(H);
    printf("ASL of successful search: %.2f\n", ASL(H, H.count));
    printf("ASL of unsuccessful search: %.2f\n", ASL(H, MAXSIZE-H.count));
    while (1) {
        printf("1. Search\n2. Insert\n3. Delete\n4. Exit\n");
        int choice;
        scanf("%d", &choice);
        if (choice == 4) break;
        KeyType key;
        switch (choice) {
            case 1:
                printf("Input the key to search: ");
                scanf("%d", &key);
                Search(H, key);
                break;
            case 2:
                printf("Input the key to insert: ");
                scanf("%d", &key);
                ElemType e = {key};
                Insert(&H, e);
                DisplayHashTable(H);
                printf("ASL of successful search: %.2f\n", ASL(H, H.count));
                printf("ASL of unsuccessful search: %.2f\n", ASL(H, MAXSIZE-H.count));
                break;
            case 3:
                printf("Input the key to delete: ");
                scanf("%d", &key);
                Delete(&H, key);
                DisplayHashTable(H);
                printf("ASL of successful search: %.2f\n", ASL(H, H.count));
                printf("ASL of unsuccessful search: %.2f\n", ASL(H, MAXSIZE-H.count));
                break;
            default:
                printf("Invalid choice.\n");
        }
    }
    return 0;
}

注：代码中使用了除留余数法，哈希表长度MAXSIZE为20，哈希函数为H(key)=key % 5，可以根据实际情况进行修改。

C++常见的哈希算法

### C++ 中常用的哈希算法

#### 一、哈希算法概述

哈希算法是一种将任意大小的数据映射到固定大小的数据的方法。该方法具备快速计算、唯一性和固定长度的优点，但也存在哈希冲突和不可逆性的缺点[^3]。

#### 二、C++中的常见哈希算法及其特点

##### 1. **除留余数法**

这是最简单的一种哈希函数设计方式，通过取模运算来决定数据应该存放在哪个桶里：

size_t hash(int key, size_t table_size) {
    return key % table_size;
}

这种方法虽然直观易懂，但在某些情况下可能导致分布不均的问题[^1]。

##### 2. **平方取中法**

对于整型键值而言，先将其平方再从中截取出一部分作为索引也是一种有效的策略：

size_t mid_square_hash(int key, size_t table_size) {
    long square = static_cast<long>(key) * key;
    string strSquare = to_string(square);
    int start_pos = (strSquare.length() / 2) - 2;
    string substr = strSquare.substr(start_pos, 4); // 取中间四位
    return stoi(substr) % table_size;
}

此方法有助于改善因输入序列规律性强而导致的聚集现象。

##### 3. **折叠法**

当面对较长位串形式的关键字时，可采用分组求和的方式构建哈希值：

size_t folding_hash(const std::string& key, size_t table_size) {
    const char* bytes = key.c_str();
    unsigned long sum = 0;
    while (*bytes != '\0') {
        sum += *bytes++;
    }
    return sum % table_size;
}

这种方式特别适合处理字符类型的键值。

##### 4. **随机数法**

利用伪随机数生成器创建难以预测但稳定的哈希结果：

#include <random>
std::default_random_engine generator;

template<typename T>
size_t random_hash(T value, size_t table_size) {
    std::hash<T> hasher;
    auto seed = hasher(value);
    generator.seed(seed);
    uniform_int_distribution<size_t> distribution(0, table_size-1);
    return distribution(generator);
}

此类技术常用于防止恶意攻击者故意制造碰撞的情况[^2]。

#### 三、线性探测解决哈希冲突

为了应对不可避免的哈希冲突问题，在`HashTable`类模板的基础上实现了基于线性探测机制的插入操作：

bool insert(const K& key, const V& val) {
    size_t index = this->hash(key);

    while (_tables[index]._state == EXIST && _tables[index]._kv.first != key) {
        ++index %= _tables.size(); // 循环查找下一个可用槽位
    }

    if (_tables[index]._state != EXIST || _tables[index]._kv.first == key) {
        _tables[index]._kv = make_pair(key, val);
        _tables[index]._state = EXIST;
        ++_n;
        return true;
    }
    
    return false; // 表已满或其他错误条件
}

上述代码片段展示了如何在线性探查过程中找到合适的位置存放新元素，并妥善处理重复键的情形[^4]。