c - 哈希算法的实现将字符串转换为数字

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

哈希函数在技术上属于密码学的一个分支，这与哈希的(有问题的)定义和(严格的)要求有关。

因此，强烈建议您不要推出自己的哈希算法，而是坚持使用可最大限度减少冲突的现有(经过测试的)算法。

将字符串转换为数字不是散列...尽管当您认为自己想出了一个唯一值时，这可能是一种体验冲突并最终导致无法追踪的问题的好方法...

除非这不是学校作业，在学校作业中您得到了一些实际上是为了满足作业(而不是现实生活中的实现)的 stub “哈希”算法，否则请尝试查找真正的哈希算法。它们都带有伪代码，其中大部分带有用于测试的 C 实现。

例如，SipHash是一些标准库(即 Ruby 和 Rust)中使用的非常常见的字符串哈希算法。

祝你好运!

编辑

有些人认为使用加密哈希函数不是最优的。您应该考虑您的用例，但是......如果您使用哈希来承担股权，我建议您支付性能价格。如果您将哈希值用作不安全的指示符，这可能无关紧要。

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

附言

这是我为我提到的 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 案例失败是故意的)