散列算法的实现将串号

Question

我要实现哈希表， 我有计划，说明如何串号（哈希函数）转换：

abcdef... -> ((256*a+b) XOR (256*c+d)) XOR (256*e+f) ... 

我在写这个问题，因为我不确定这段代码（主要是循环）是否以正确的方式工作。

int hash(char *s){ 
    int len = strlen(s); 
    int i, result = 0; 
    for(i = 0; i < len-1; i=i+2) { 
      result ^= ((256*s[i])+s[i+1]); 
    } 
    if(s[i]!=0) { 
      result ^= (256*s[i]); 
    } 
    return result; 
} 

Answer 1

Hash函数技术上属于密码学的分支，这已与（可疑）定义和散列的（严格）的要求去做。

因此，强烈建议您不要推出自己的哈希算法，并坚持使现有（测试）算法最小化碰撞。

字符串转换为数字不散列...虽然它可能遇到的碰撞，并与当你认为你想出了一个独特的价值难以追查问题结束了一个好办法...

除非这不是一个学校任务，在这里你得到了一些存根（hash）算法，这些算法实际上是为了满足任务（而不是实际的生活实现），尝试查找实际的哈希算法。它们都带有伪代码，其中大部分都带有用于测试的C实现。

例如，SipHash是在一些标准库（即Ruby和Rust）中使用的非常常见的字符串散列算法。

祝你好运！

编辑

有人认为，使用加密散列函数是次优。你应该考虑你的用例，但是......如果你使用散列来承担平等，我会建议支付性能价格。如果你使用散列作为不安全的指标，它可能并不重要。

这是a page with some non-cryptographic hash functions。

P.S.

这是我为我提到的SipHash写的一个实现...我的代码没有很好的测试，所以如果你发现任何问题，请随时联系post them here。

#include <stdlib.h> 
#include <stdint.h> 

#define SIPHASH_DEFAULT_KEY       \ 
    (uint64_t[]) { 0x0706050403020100, 0x0f0e0d0c0b0a0908 } 

uint64_t siphash24(const void *data, size_t len, uint64_t iv_key[2]); 

// clang-format off 
#if !defined(__BIG_ENDIAN__) && !defined(__LITTLE_ENDIAN__) 
# if defined(__has_include) 
#  if __has_include(<endian.h>) 
#  include <endian.h> 
#  elif __has_include(<sys/endian.h>) 
#  include <sys/endian.h> 
#  endif 
# endif 
# if !defined(__BIG_ENDIAN__) && !defined(__LITTLE_ENDIAN__) && \ 
       __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ 
#  define __BIG_ENDIAN__ 
# endif 
#endif 

#ifndef __unused 
# define __unused __attribute__((unused)) 
#endif 
// clang-format on 

/** 64Bit left rotation, inlined. */ 
#define _lrot64(i, bits)              \ 
    (((uint64_t)(i) << (bits)) | ((uint64_t)(i) >> (64 - (bits)))) 

#ifdef __BIG_ENDIAN__ 
/* the algorithm was designed as little endian */ 
/** inplace byte swap 64 bit integer */ 
#define sip_local64(i)               \ 
    (((i)&0xFFULL) << 56) | (((i)&0xFF00ULL) << 40) |       \ 
     (((i)&0xFF0000ULL) << 24) | (((i)&0xFF000000ULL) << 8) |     \ 
     (((i)&0xFF00000000ULL) >> 8) | (((i)&0xFF0000000000ULL) >> 24) |   \ 
     (((i)&0xFF000000000000ULL) >> 40) | (((i)&0xFF00000000000000ULL) >> 56) 

#else 
/** no need */ 
#define sip_local64(i) (i) 
#endif 

uint64_t siphash24(const void *data, size_t len, uint64_t iv_key[2]) { 
    /* initialize the 4 words */ 
    uint64_t v0 = iv_key[0]^0x736f6d6570736575ULL; 
    uint64_t v1 = iv_key[1]^0x646f72616e646f6dULL; 
    uint64_t v2 = iv_key[0]^0x6c7967656e657261ULL; 
    uint64_t v3 = iv_key[1]^0x7465646279746573ULL; 
    const uint64_t *w64 = data; 
    uint8_t len_mod = len & 255; 
    union { 
    uint64_t i; 
    uint8_t str[8]; 
    } word; 

#define _bs_map_SipRound              \ 
    do {                   \ 
    v2 += v3;                 \ 
    v3 = _lrot64(v3, 16)^v2;             \ 
    v0 += v1;                 \ 
    v1 = _lrot64(v1, 13)^v0;             \ 
    v0 = _lrot64(v0, 32);              \ 
    v2 += v1;                 \ 
    v0 += v3;                 \ 
    v1 = _lrot64(v1, 17)^v2;             \ 
    v3 = _lrot64(v3, 21)^v0;             \ 
    v2 = _lrot64(v2, 32);              \ 
    } while (0); 

    while (len >= 8) { 
    word.i = sip_local64(*w64); 
    v3 ^= word.i; 
    /* Sip Rounds */ 
    _bs_map_SipRound; 
    _bs_map_SipRound; 
    v0 ^= word.i; 
    w64 += 1; 
    len -= 8; 
    } 
    word.i = 0; 
    uint8_t *pos = word.str; 
    uint8_t *w8 = (void *)w64; 
    switch (len) { 
    case 7: 
    pos[6] = w8[6]; 
    case 6: 
    pos[5] = w8[5]; 
    case 5: 
    pos[4] = w8[4]; 
    case 4: 
    pos[3] = w8[3]; 
    case 3: 
    pos[2] = w8[2]; 
    case 2: 
    pos[1] = w8[1]; 
    case 1: 
    pos[0] = w8[0]; 
    } 
    word.str[7] = len_mod; 
    // word.i = sip_local64(word.i); 

    /* last round */ 
    v3 ^= word.i; 
    _bs_map_SipRound; 
    _bs_map_SipRound; 
    v0 ^= word.i; 
    /* Finalization */ 
    v2 ^= 0xff; 
    /* d iterations of SipRound */ 
    _bs_map_SipRound; 
    _bs_map_SipRound; 
    _bs_map_SipRound; 
    _bs_map_SipRound; 
    /* XOR it all together */ 
    v0 ^= v1^v2^v3; 
#undef _bs_map_SipRound 
    return v0; 
} 

#undef sip_local64 
#undef _lrot64 

（在switch情况下告吹是故意的）