murmurhash源码分析

Posted by 111qqz on Wednesday, March 22, 2017

TOC

分析levelDB源码的时候遇到的…发现是一个广泛应用的hash算法,而且是纯c写的,于是找来了源码看。

**MurmurHash** 是一种非[加密](https://zh.wikipedia.org/wiki/)型[哈希函数](https://zh.wikipedia.org/wiki/),适用于一般的哈希检索操作。[[1]](https://zh.wikipedia.org/wiki/Murmur#cite_note-Hadoop-1)[[2]](https://zh.wikipedia.org/wiki/Murmur#cite_note-2)[[3]](https://zh.wikipedia.org/wiki/Murmur#cite_note-3)由Austin Appleby在2008年发明,[[4]](https://zh.wikipedia.org/wiki/Murmur#cite_note-4)[[5]](https://zh.wikipedia.org/wiki/Murmur#cite_note-5) 并出现了多个变种,[[6]](https://zh.wikipedia.org/wiki/Murmur#cite_note-Murmur160-6) 都已经发布到了[公有领域](https://zh.wikipedia.org/wiki/)(public domain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。[[7]](https://zh.wikipedia.org/wiki/Murmur#cite_note-StackExchange-7)

最初的实现是C++的,但是被移植到了其他的流行语言上,包括 Python,[11]C,[12]C#,[9][13]Perl,[14]Ruby,[15]PHP,[16]Haskell,[17]Scala[18]Java[19][20]JavaScript[21][22]等。

这个算法已经被若干开源计划所采纳,最重要的有libstdc++ (4.6版)、Perl[23]nginx (不早于1.0.1版)[24]Rubinius[25]、 libmemcached (MemcachedC语言客户端驱动)[26]、maatkit[27]Hadoop[1]、Kyoto Cabinet[28]以及RaptorDB[29]

虽然说破天就是一个hash函数。。似乎没什么好分析的?

不过由于是第一次分析有现实意义的代码,所以简单一点也不是罪过吧orz

以及这次分析代码的重点不在hash算法本身…而是算法之外的其他东西…

大概感受下有现实意义的工程代码的布局之类orz

hash函数本身没有分析…这个没什么好分析的吧…应该是类似一种构造,看懂每一步很容易,但是你还是想不出来啊?而且一堆"magic number”

代码很短,也就200行,分析见注释。

/**
 * `main.c' - murmurhash
 *
 * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <inttypes.h>
#include "murmurhash.h"

static void
usage () {
  fprintf(stderr, "usage: murmur [-hV] [options]\n");
}

static void   //函数类型和函数名不一行写是什么风格orz...
help () {
  fprintf(stderr, "\noptions:\n");
  fprintf(stderr, "\n  --seed=[seed]  hash seed (optional)");
  fprintf(stderr, "\n");
}

static char *
read_stdin () {
  size_t bsize = 1024;
  size_t size = 1;
  char buf[bsize];
  char *res = (char *) malloc(sizeof(char) * bsize);
  char *tmp = NULL;

  // memory issue
  if (NULL == res) { return NULL; } //申请内存失败了...

  // cap
  res[0] = '\0';

  // read
  if (NULL != fgets(buf, bsize, stdin)) {
    // store
    tmp = res; //异常安全? 
    // resize
    size += (size_t) strlen(buf);
    // realloc
    res = (char *) realloc(res, size);

    // memory issues
    if (NULL == res) {
      free(tmp);
      return NULL;
    }

    // yield
    strcat(res, buf); //将buf连接到res后面...
  //  printf("buf:%s res:%s\n",buf,res);
    return res;
  }

  free(res);


  return NULL;
}

#define isopt(opt, str) (0 == strncmp(opt, str, strlen(str))) 
//比较opt和str前strlen(str)个字符。

#define setopt(opt, key, var) {                       \
    char tmp = 0;                                     \
    size_t len = strlen(key) + 1;                     \
    for (int i = 0; i < len; ++i) { tmp = *opt++; }   \
    var = opt;                                        \
}
// key是"seed",让len = strlen(key)+1,是为了把seed和‘=’跳过去。。。
// 因此seed,‘=’,后面的数字之间不支持有空格。
// 得到的var是*char型的seed.


int
main (int argc, char **argv) { //argc是命令行的参数个数,**argv是字符串数组
  char *buf = NULL;
  char *key = NULL;
  char *seed = NULL;
  uint32_t h = 0;

  // parse opts
  {
    char *opt = NULL;
    char tmp = 0;

 //   for ( int i = 0 ;  i < argc ; i++)  printf("Argument %d is %s.\n", i, argv[i]);
    opt = *argv++; // unused,因为第0个参数就是“murmur”,跳过。
    

    while ((opt = *argv++)) { //argv参数最后会变成null,退出循环...
//	printf("opt: %s argv:%s\n",opt,*argv);

      // flags
      if ('-' == *opt++) {
        switch (*opt++) {
          case 'h':
            return usage(), help(), 0; //直接用了return和逗号表达式...避免了break,代码简洁了(?

          case 'V':
            fprintf(stderr, "%s\n", MURMURHASH_VERSION);
            return 0;

          case '-': //参数不要带空格。。。
            if (isopt(opt, "seed")) {
              setopt(opt, "seed", seed);
            }
            break; //是break而不是return,说明在--seed参数后面还可以跟其他参数。。
            //如果跟了多了--seed参数,前面的参数会被最有一个覆盖掉,hash结果与最后一个seed对应。
          default:
            tmp = *opt--;//这个tmp好像没什么用啊?
            // error
            fprintf(stderr, "unknown option: `%s'\n", opt);
            usage();
            return 1;
        }
      }
    }
  }

  if (NULL == seed) { //赞! 避免了手残把等号写成赋值号的可能,下面也都用了这种写法。
    seed = "0";
  }

#define hash(key) murmurhash(key, (uint32_t) strlen(key), (uint32_t) atoi(seed));
                        //atoi,把字符串转成了int型,然后被强转了。。。
  if (1 == isatty(0)) { return 1; } //isatty 判断文件描述词是否位终端机(?,是为1,不是为0
  else if (ferror(stdin)) { return 1; }
  else {
    buf = read_stdin();
    if (NULL == buf) { return 1; }
    else if (0 == strlen(buf)) { buf = ""; }
    h = hash(buf);
    printf("%" PRIu32 "\n", h);
    //PRIu32是头文件inttypes.h包含的宏,用于平台独立的printf编码。。
    //会自动根据平台去对应相应的类型说明符。。。
    do {
      key = read_stdin();
      if (NULL == key) { break; }
      else if (0 == strlen(buf)) { buf = ""; }
      h = hash(buf);
      printf("%d" PRIu32 "\n", h);
    } while (NULL != key);
  }

#undef hash

  return 0;
}




/**
 * `murmurhash.h' - murmurhash
 *
 * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
 */

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include "murmurhash.h"

uint32_t
murmurhash (const char *key, uint32_t len, uint32_t seed) {
  uint32_t c1 = 0xcc9e2d51;
  uint32_t c2 = 0x1b873593;
  uint32_t r1 = 15;
  uint32_t r2 = 13;
  uint32_t m = 5;
  uint32_t n = 0xe6546b64;
  uint32_t h = 0;
  uint32_t k = 0;
  uint8_t *d = (uint8_t *) key; // 32 bit extract from `key'
  const uint32_t *chunks = NULL;
  const uint8_t *tail = NULL; // tail - last 8 bytes
  int i = 0;
  int l = len / 4; // chunk length

  h = seed;

  chunks = (const uint32_t *) (d + l * 4); // body
  tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key'

  // for each 4 byte chunk of `key'
  for (i = -l; i != 0; ++i) {
    // next 4 byte chunk of `key'
    k = chunks[i];

    // encode next 4 byte chunk of `key'
    k *= c1;
    k = (k << r1) | (k >> (32 - r1));
    k *= c2;

    // append to hash
    h ^= k;
    h = (h << r2) | (h >> (32 - r2));
    h = h * m + n;
  }

  k = 0;

  // remainder
  switch (len & 3) { // `len % 4'
    case 3: k ^= (tail[2] << 16);
    case 2: k ^= (tail[1] << 8);

    case 1:
      k ^= tail[0];
      k *= c1;
      k = (k << r1) | (k >> (32 - r1));
      k *= c2;
      h ^= k;
  }

  h ^= len;

  h ^= (h >> 16);
  h *= 0x85ebca6b;
  h ^= (h >> 13);
  h *= 0xc2b2ae35;
  h ^= (h >> 16);

  return h;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付