C语言 字符串哈希函数

1、DJB2 哈希函数

著名的哈希算法之一，由 Daniel J. Bernstein 提出，具有较好的性能和广泛的应用。它简单且效果不错。

#include <stdio.h>

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    return hash;
}

int main() {
    char *str = "Hello, World!";
    printf("Hash value: %lu\n", hash((unsigned char *)str));
    return 0;
}

2、SDBM 哈希函数

SDBM 哈希函数是另一种常见的字符串哈希算法，简单并且执行效率高。

#include <stdio.h>

unsigned long sdbm_hash(unsigned char *str) {
    unsigned long hash = 0;
    int c;
    while ((c = *str++)) {
        hash = c + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}

int main() {
    char *str = "Hello, World!";
    printf("SDBM Hash value: %lu\n", sdbm_hash((unsigned char *)str));
    return 0;
}

3、FNV-1a 哈希函数

FNV-1a 是一个简单的哈希算法，使用异或和乘法操作来计算哈希值，效率高并且结果均匀。

#include <stdio.h>

unsigned long fnv1a_hash(unsigned char *str) {
    unsigned long hash = 14695981039346656037UL;
    int c;
    while ((c = *str++)) {
        hash ^= c;
        hash *= 1099511628211;
    }
    return hash;
}

int main() {
    char *str = "Hello, World!";
    printf("FNV-1a Hash value: %lu\n", fnv1a_hash((unsigned char *)str));
    return 0;
}

4、BKDR Hash（倍数种子法）

经典中国算法竞赛中常用的字符串哈希函数，选择合适的 seed 可降低碰撞率。

#include <stdio.h>

// 哈希函数定义（BKDR Hash）
unsigned int hash4(const char *str) {
    unsigned int seed = 131; // 常用：31、131、1313 等
    unsigned int hash = 0;
    while (*str)
        hash = hash * seed + (unsigned char)(*str++);
    return hash;
}

int main() {
    const char *examples[] = {
        "hello",
        "world",
        "hash",
        "function",
        "hello" // 重复测试
    };

    int n = sizeof(examples) / sizeof(examples[0]);
    for (int i = 0; i < n; i++) {
        printf("String: %-10s  Hash: %u\n", examples[i], hash4(examples[i]));
    }

    return 0;
}

5、简单加权求和法（乘 31）

最常见的哈希方法，类似 Java 的 String.hashCode() 实现。

#include <stdio.h>

// 哈希函数定义（乘31法）
unsigned int hash1(const char *str) {
    unsigned int hash = 0;
    while (*str)
        hash = hash * 31 + (unsigned char)(*str++);
    return hash;
}

int main() {
    const char *examples[] = {
        "apple",
        "banana",
        "cherry",
        "apple",    // 相同字符串
        "banana",   // 相同字符串
        "Apple"     // 大小写不同
    };

    int n = sizeof(examples) / sizeof(examples[0]);
    for (int i = 0; i < n; i++) {
        printf("String: %-10s  Hash: %u\n", examples[i], hash1(examples[i]));
    }

    return 0;
}