About hash function

Posted on   |   In

日常工作中经常会遇到哈希算法，出于好奇想多了解一些关于哈希的理论。
在Ceph中（一种分布式存储系统），从Object到PG的映射就是采用了一种哈希算法，名为“rjenkins”。所以就是从这里作为切入点，看了一些资料。

哈希算法的作用

哈希，也称作散列，它的作用其实就是通过一个函数（hash function），将输入值映射为一个输出的值，并且尽量保证这个映射是一对一的。

哈希算法的好坏

怎样的哈希算法才是一个好的哈希算法？从他的作用或者说目的上看，它最重要的衡量标准是是否有碰撞（collision），或者是否有尽可能少的碰撞。这里有个概念 funneling，翻译成中文是“漏斗效应”[注1]，其实就是很多input被映射到少量的几个output上，产生了大量的碰撞。好的hash算法应该是可以通过测试或者理论证明这个算法是no funnel的。
这里有两个概念：完美哈希函数（PHF，Perfect Hash Function）和最小完美哈希函数（MPHF，Minimal Perfect Hash Function）。完美哈希函数，就是没有冲突的哈希函数，也就是将N个KEY值映射到M个整数上，这里M>=N，并且对于任意的KEY1，KEY2，H(KEY1)！=H(KEY2)。当M==N，则H是最小完美哈希函数。
当然它的另一个衡量标准是速度快，前提是在相同硬件条件下。也就是说每次哈希的运算次数少或者消耗的CPU指令周期少。

哈希模型

1
2
3
4
5
6
7
8
initialize the internal state;
  for (each block of the input)
  {
    combine (the internal state, the current input block);
    mix( the internal state);
  }
  value = postprocess( the internal state );
  return (value);

也就是说一个hash过程主要包括：initialize, combine, mix, postprocess这几个过程。

参考

  1. Jenkins关于他新的hash算法以及相关理论的介绍
    http://burtleburtle.net/bob/hash/evahash.html
  2. 几种hash算法的对比
    http://burtleburtle.net/bob/hash/examhash.html

附言：
好长时间没写东西了，今天来这里扫扫灰：）