hash算法

作者 : 开心源码 本文共1301个字,预计阅读时间需要4分钟 发布时间: 2022-05-14 共156人阅读

简单一点的hash算法就是直接取模。

高级一点的hash算法会乘以一个大素数来将源数据的分布规律变得不那么显著,也就是说,不管输入的是一串分布很紧凑的数字序列还是很稀疏的数字序列,生成的结果都是非常分散的数字序列。

linux内核代码里面的这个hash要更高一级,包含2个特征,最接近32位或者者64位上限黄金分割点的素数,只要要最少的移位和求和就能生成。

前者确保即便是1,2这样的小数也会被乘溢出,被轻易打散。

后者确保任何一个整数乘这个大素数的时候都可以通过最少的移位和求和就可得到乘积,不用傻傻的真的相乘。

/* 2^31 + 2^29 – 2^25 + 2^22 – 2^19 – 2^16 + 1 */

#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

/*  2^63 + 2^61 – 2^57 + 2^54 – 2^51 – 2^18 + 1 */

#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL

#if BITS_PER_LONG == 32

#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32

#define hash_long(val, bits) hash_32(val, bits)

#elif BITS_PER_LONG == 64

#define hash_long(val, bits) hash_64(val, bits)

#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64

#else

#error Wordsize not 32 or 64

#endif

static inline u64 hash_64(u64 val, unsigned int bits)

{

    u64 hash = val;

    /*  Sigh, gcc can’t optimise this alone like it does for 32 bits. */

    u64 n = hash;

    n <<= 18;

    hash -= n;

    n <<= 33;

    hash -= n;

    n <<= 3;

    hash += n;

    n <<= 3;

    hash -= n;

    n <<= 4;

    hash += n;

    n <<= 2;

    hash += n;

    /* High bits are more random, so use them. */

    return hash >> (64 – bits);

}

static inline u32 hash_32(u32 val, unsigned int bits)

{

    /* On some cpus multiply is faster, on others gcc will do shifts */

    u32 hash = val * GOLDEN_RATIO_PRIME_32;

    /* High bits are more random, so use them. */

    return hash >> (32 – bits);

}

static inline unsigned long hash_ptr(const void *ptr, unsigned int bits)

{

    return hash_long((unsigned long)ptr, bits);

}

#endif /* _LINUX_HASH_H */

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » hash算法

发表回复