Hash函数是一种映射关系，通过一种映射关系，将原本的字符串，数字或其他关键信息转换为一个索引值。
用数学关系式表示为：
   index  =  function(key)

数序上有不同的映射关系，不同的key，有可能会获取相同的index，这个时候的index就是有重码，也就是collosion，这就导致了Hash函数的不唯一性，从而在查找index下的关键字时也是有冲突的。

目前一些常用的数学映射关系为：
   1、直接定址法，就是直接使用key作为index
   2、数字分析法，取key中的若干位数作为index，有较多冲突
   3、平法取中法，取key的平方，然后取中间几位作为index（index与key值密切相关），
   4、折叠法，将key从中间分割成几个部分，然后按照一定规则相加获取的结果为index。
   5、除留余数法，将key对某个数值m求余，获取的余数即为index，显然indxe<m，也就是如果key>m，必然会有n-m个冲突存在（n为key关键字的个数）。
   6、随机数法，将key值通过随机数求取index，即function（key）=random（key），伪随机数的均匀性较好，当关键字长度不相等时，用此法构造较为恰当。

解决冲突：
    其实并不是将冲突去掉，而是通过一种变通的方法，将冲突变得可以唯一查找，而不是有冲突就没有唯一的index位置了。
   解决方法有：
    一、开放定址法：
             index = （function（key）+di）mod m
               di：增长序列，m哈希表长，d的求取方法有下面集中。
      1、线性探测再散列，就是查找或插入时，如果发生冲突，就线性排列下去，下面还有冲突，继续排列下去，直到没有冲突时，查找结束或添加index。d=1，2，3，……，m-1
     2、二次探测再散列，d=1^2，-1^2，2^2，-2^2，……，±k^2（k<=m/2）
     3、伪随机探测再散列，d=random（key）
  二、再Hash法
        即将index冲突的key关键字进行另一种Hash算法，得到key关键的index2索引值，从而来降低和避免冲突，当然要将冲突完全避免，则需要多个Hash算法隐含在其中。
 三、链地址法
        当Index发生冲突时，将同一个index下冲突的key值都放在以index开头的链表中，这样index开头的链表中的key都可以比较方便的查找出来。
四、建立溢出表
         建立一个和key关键字一样多的index索引，当index发生冲突时，将所有发生冲突的key或index都放在溢出表中。

Hash表查找：
  

// ——-开放定址Hash表的存储结构————
int hashsize[]=…{997,…};  //Hash表容量递增表，一个合适的素数序列
typedef struct…{
   ElemType *elem;           //数据元素存储基址，动态分配数组
   int              count;          // 当前数据元素的个数
   int              sizeIndex;   //hashsize[sizeIndex]为当前容量
}HashTable;

//——–链接地址Hash表的存储结构—————
typedef struct childchain
{
   ElemType data;   // 数据值
   struct childchain *next;  // 下一个childchain值，NULL结束
}ChildChainHash

  typedef struct mainchain{
    int index;   // 主链的索引值
    ChildChainHash  *child;  // 指向冲突的child子链，当没有冲突时，给予NULL值。
   struct mainchain *main;  //
}MainChainHash;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

采用链接构建Hash的思路，MainChainHash申请一个head指针和若干个变量，然后main指针依次指向下一个MainChainHash指针，而每一个child指针，指向ChildChainHash链中的值，这样一个Hash表就 构造完成了。当主键key使用Hash一下获取的Index时，通过Index索引值知道Child链，从而构造了一个核实的Hash表。

// 采用开放式哈希表的存储结构

Status SearchHash(HashTable H, KeyType k, int &p, int &c)
…{
     // 开放地址哈希表H中查找关键字k的元素，若查找成功，以p指示待查数据，
   // 元素在表中位置，并返回SUCESS，否则，以p指示插入位置，并返回UNSUCESS，
   // c用以计冲突次数，其初值置零，供建表插入时参考
  p  = Hash(k);   // 求得hash地址表
  while( H.elem[p].key != NULLKEY &&   //该位置中填有记录
           !EQ( k,H.elem[p].key)                 // 并且关键字不相等
          collision( p, ++c) ;                  // 求得下一探索地址p
   if (EQ(K, H.elem[p].key ) )
          return SUCCESS;                 // 查找成功，p返回待查数据元素位置
   else
         return UNSUCESS;              // 查找不成功.( H.elem[p].key == NULLKEY )
                                                      // p返回的是插入的位置
}// SearchHash

Status InsertHash( HashTable &H, ElemType e)
…{
     // 查找不成功时，插入数据元素e到开放定址Hash表H中，并返回OK，
    // 若冲突次数过大，需重新构建Hash表
   c = 0;
   if( SearchHash( H,e.key,p,c ))
        return DUPLICATE;           // 表中已有与e有相同关键字的元素
  else if ( c <hashsize[H.sizeindex]/2 )  //冲突次数c未达到上限时，（c的阈值可调）
  …{
         H.elem[p] = e; ++H.count; return OK;    // 插入e
   }
   else 
  …{
     RecreateHashTable(H);
    return UNSUCESS;    // 重建hash表
  }
}  // InsertHash
摘抄自严蔚敏的C数据结构中Hash章节。
Hash表最大的特点：
    不管n有多大，即表有多长，我们总可以选择一个合适的装填因子以便将来平均查找长度限定在一个范围之内。

查找长度
链地址：
          S=1+α /2
线性探测：
          S = 1/2 (1+1/(1-α ) )
伪随机探测：
          S = -1/α ln(1-α )

This pdf:  pdf

This pdf : A Quick Introduction to Bloom Filters

Bloom Filters – Short Tutorial

Matei Ripeanu, Adriana Iamnitchi

1.      Introduction

Bloom filters [2] are compact data structures for probabilistic representation of a set in order to support membership queries (i.e. queries that ask: “Is element X in set Y?”).  This compact representation is the payoff for allowing a small rate of false positives in membership queries; that is, queries might incorrectly recognize an element as member of the set. 

We succinctly present Bloom filters use to date in the next section.  In Section 3 we describe Bloom filters in detail, and in Section 4 we give a hopefully precise picture of space/computing time/error rate tradeoffs. 

2.      Usage

Since their introduction in [2], Bloom filters have seen various uses:

• Web cache sharing ([3]) Collaborating Web caches use Bloom filters (dubbed “cache summaries”) as compact representations for the local set of cached files.  Each cache periodically broadcasts its summary to all other members of the distributed cache.  Using all summaries received, a cache node has a (partially outdated, partially wrong) global image about the set of files stored in the aggregated cache.  The Squid Web Proxy Cache [1] uses “Cache Digests” based on a similar idea.
• Query filtering and routing ([4, 6, 7]) The Secure wide-area Discovery Service [6], subsystem of Ninja project [5], organizes service providers in a hierarchy.  Bloom filters are used as summaries for the set of services offered by a node.  Summaries are sent upwards in the hierarchy and aggregated.  A query is a description for a specific service, also represented as a Bloom filter.  Thus, when a member node of the hierarchy generates/receives a query, it has enough information at hand to decide where to forward the query: downward, to one of its descendants (if a solution to the query is present in the filter for the corresponding node), or upward, toward its parent (otherwise).

The OceanStore [7] replica location service uses a two-tiered approach: first it initiates an inexpensive, probabilistic search (based on Bloom filters, similar to Ninja) to try and find a replica.  If this fails, the search falls-back on (expensive) deterministic algorithm (based on Plaxton replica location algorithm).  Alas, their description of the probabilistic search algorithm is laconic. (An unpublished text [11] from members of the same group gives some more details.  But this does not seem to work well when resources are dynamic.) 

• Compact representation of a differential file ([9]).  A differential file contains a batch of database records to be updated.  For performance reasons the database is updated only periodically (i.e., midnight) or when the differential file grows above a certain threshold.  However, in order to preserve integrity, each reference/query to the database has to access the differential file to see if a particular record is scheduled to be updated.  To speed-up this process, with little memory and computational overhead, the differential file is represented as a Bloom filter.
• Free text searching ([10]).  Basically, the set of words that appear in a text is succinctly represented using a Bloom filter

3.      Constructing Bloom Filters

Consider a set

of  n elements.  Bloom filters describe membership information of A using a bit vector V of length m. For this, k hash functions,  with , are used as described below:

The following procedure builds an m bits Bloom filter, corresponding to a set A and using  hash functions:

Procedure BloomFilter(set A, hash_functions, integer m)                   returns filter    filter = allocate m bits initialized to 0    foreach a_i  in A:                foreach hash function h_j:            filter[h_j(a_i)] = 1    end foreach    end foreach    return filter 

Therefore, if a_i is member of a set A, in the resulting Bloom filter V all bits obtained corresponding to the hashed values of a_i are set to 1.  Testing for membership of an element elm is equivalent to testing that all corresponding bits of V are set: 

Procedure MembershipTest (elm, filter, hash_functions) returns yes/no foreach hash function h_j:    if filter[h_j(elm)] != 1 return No end foreach return Yes 

Nice features:  filters can be built incrementally: as new elements are added to a set the corresponding positions are computed through the hash functions and bits are set in the filter.  Moreover, the filter expressing the reunion of two sets is simply computed as the bit-wise OR applied over the two corresponding Bloom filters.

4.      Bloom Filters – the Math (this follows the description in [3])

One prominent feature of Bloom filters is that there is a clear tradeoff between the size of the filter and the rate of false positives.  Observe that after inserting n keys into a filter of size m using k hash functions, the probability that a particular bit is still 0 is:

.                                                                  (1)

(Note that we assume perfect hash functions that spread the elements of A evenly throughout the space {1..m}.  In practice, good results have been achieved using MD5 and other hash functions [10].)

Hence, the probability of a false positive (the probability that all k bits have been previously set) is:

                                  (2)

In (2) p_err is minimized for  hash functions.  In practice however, only a small number of hash functions are used.  The reason is that the computational overhead of each hash additional function is constant while the incremental benefit of adding a new hash function decreases after a certain threshold (see Figure 1).

Figure 1: False positive rate as a function of the number of hash functions used.  The size of the Bloom filter is 32 bits per entry (m/n=32).  In this case using 22 hash functions minimizes the false positive rate.  Note however that adding a hash function does not significantly decrease the error rate when more than 10 hashes are already used.
Figure 2: Size of Bloom filter (bits/entry) as a function of the error rate desired.  Different lines represent different numbers of hash keys used. Note that, for the error rates considered, using 32 keys does not bring significant benefits over using only 8 keys. 

(2) is the base formula for engineering Bloom filters. It allows, for example, computing minimal memory requirements (filter size) and number of hash functions given the maximum acceptable false positives rate and number of elements in the set (as we detail in Figure 2).

 (bits per entry)                                                    (3)

To summarize: Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries.  The main design tradeoffs are the number of hash functions used (driving the computational overhead), the size of the filter and the error (collision) rate.  Formula (2) is the main formula to tune parameters according to application requirements.

5.      Compressed Bloom filters

Some applications that use Bloom filters need to communicate these filters across the network.  In this case, besides the three performance metrics we have seen so far: (1) the computational overhead to lookup a value (related to the number of hash functions used), (2) the size of the filter in memory, and (3) the error rate, a fourth metric can be used: the size of the filter transmitted across the network. M. Mitzenmacher shows in [8] that compressing Bloom filters might lead to significant bandwidth savings at the cost of higher memory requirements (larger uncompressed filters) and some additional computation time to compress the filter that is sent across the network.  We do not detail here all theoretical and practical issues analyzed in [8]. 

6.      References

1.         http://www.squid-cache.org/.

2.         Bloom, B. Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13 (7). 422-426.

3.         Fan, L., Cao, P., Almeida, J. and Broder, A., Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. in Proceedings of ACM SIGCOMM’98, (Vancouver, Canada, 1998).

4.         Gribble, S.D., Brewer, E.A., Hellerstein, J.M. and Culler, D., Scalable, Distributed Data Structures for Internet Service Construction. in Proceedings of the Fourth Symposium on Operating Systems Design and Implementation  (OSDI 2000), (San Diego, CA, 2000).

5.         Gribble, S.D., Welsh, M., Behren, R.v., Brewer, E.A., Culler, D., Borisov, N., Czerwinski, S., Gummadi, R., Hill, J., Joseph, A.D., Katz, R.H., Mao, Z., Ross, S. and Zhao, B. The Ninja Architecture for Robust Internet-Scale Systems and Services. Special Issue of Computer Networks on Pervasive Computing.

6.         Hodes, T.D., Czerwinski, S.E., Zhao, B.Y., Joseph, A.D. and Katz, R.H. An Architecture for Secure Wide-Area Service Discovery. Wireless Networks.

7.         Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C. and Zhao, B., OceanStore: An Architecture for Global-Scale Persistent Storage. in Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), (Cambridge, MA, 2000).

8.         Mitzenmacher, M., Compressed Bloom Filters. in Twentieth ACM Symposium on Principles of Distributed Computing (PODC 2001), (Newport, Rhode Island, 2001).

9.         Mullin, J.K. A second look at Bloom filters. Communications of the ACM, 26 (8). 570-571.

10.       Ramakrishna, M.V. Practical performance of Bloom filters and parallel free-text searching. Communications of the ACM, 32 (10). 1237-1239.

11.       Rhea, S. and Weimer, W., Data Location in the OceanStore. in unpublished, (1999), UC Berkeley.

Bloom Filter概念和原理

焦萌 2007年1月27日

 

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x₁, x₂,…,x_n}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置h_i(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。   

 

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有h_i(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y₁就不是集合中的元素。y₂或者属于这个集合，或者刚好是一个false positive。

错误率估计

前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设kn<m且各个哈希函数是完全随机的。当集合S={x₁, x₂,…,x_n}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：

其中1/m表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中，需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它，因此这个概率就是（1-1/m）的kn次方。令p = e^-kn/m是为了简化运算，这里用到了计算e时常用的近似：

 

令ρ为位数组中0的比例，则ρ的数学期望E(ρ)= p’。在ρ已知的情况下，要求的错误率（false positive rate）为：

(1-ρ)为位数组中1的比例，(1-ρ)^k就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。p’只是ρ的数学期望，在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明^[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将p和p’代入上式中，得：

   

   

相比p’和f’，使用p和f通常在分析中更为方便。

最优的哈希函数个数

既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。

 

先用p和f进行计算。注意到f = exp(k ln(1 − e^−kn/m))，我们令g = k ln(1 − e^−kn/m)，只要让g取到最小，f自然也取到最小。由于p = e^-kn/m，我们可以将g写成

根据对称性法则可以很容易看出当p = 1/2，也就是k = ln2· (m/n)时，g取得最小值。在这种情况下，最小错误率f等于(1/2)^k ≈ (0.6185)^m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持错误率低，最好让位数组有一半还空着。

 

需要强调的一点是，p = 1/2时错误率最小这个结果并不依赖于近似值p和f。同样对于f’ = exp(k ln(1 − (1 − 1/m)^kn))，g’ = k ln(1 − (1 − 1/m)^kn)，p’ = (1 − 1/m)^kn，我们可以将g’写成

同样根据对称性法则可以得到当p’ = 1/2时，g’取得最小值。

位数组的大小

下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为є，下面我们来求位数组的位数m。

 

假设X为全集中任取n个元素的集合，F(X)是表示X的位数组。那么对于集合X中任意一个元素x，在s = F(X)中查询x都能得到肯定的结果，即s能够接受x。显然，由于Bloom Filter引入了错误，s能够接受的不仅仅是X中的元素，它还能够є (u - n)个false positive。因此，对于一个确定的位数组来说，它能够接受总共n + є (u - n)个元素。在n + є (u - n)个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示

个集合。m位的位数组共有2^m个不同的组合，进而可以推出，m位的位数组可以表示

   

个集合。全集中n个元素的集合总共有

   

个，因此要让m位的位数组能够表示所有n个元素的集合，必须有

   

即：

   

上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在错误率不大于є的情况下，m至少要等于n log₂(1/є)才能表示任意n个元素的集合。

 

上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小，这时f = (1/2)^k = (1/2)^{mln2 / n}。现在令f≤є，可以推出

这个结果比前面我们算得的下界n log₂(1/є)大了log₂ e ≈ 1.44倍。这说明在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。

总结

在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

 

自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现。可以预见，随着网络应用的不断深入，新的变种和应用将会继续出现，Bloom Filter必将获得更大的发展。

参考资料

[1] A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485–509, 2005.

[2] M. Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Transactions on Networking 10:5 (2002), 604—612.

[3] www.cs.jhu.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf

[4] http://166.111.248.20/seminar/2006_11_23/hash_2_yaxuan.ppt

Dictionary是一种抽象数据类型，用来存储可以用键值（key）索引的数据项，基本的操作包括插入、查找和删除。它是一个相对比较广义的概念，并没有规定具体的实现，比如在底层用什么数据结构存储数据项。因此，只要存储的每一个数据项是一对(key, value)，并可以用key索引到这一项，就可以将这样的数据类型称为Dictionary。

 

Direct-address Tables和Hash Tables都是Dictionary的具体实现方式。Direct-address Tables其实就是普通的数组，数组的第k项只被用来存储键值为k的数据项。显然，要应用这种数据结构必须给每一个可能的键值预留一个数组项，因此它只适用于键值的集合比较小的情况。虽然Direct-address Tables看起来比较浪费内存，但也有它的优点：插入、查找和删除操作的时间复杂度为O(1)。

 

Hash Tables是Dictionary的一种有效实现，它解决了Direct-address Tables在键值集合比较大的情况下不适用的问题。假设U表示所有可能的键值的集合，K表示实际要存储的键值的集合。在|U|远远大于|K|的时候，Hash Tables只分配和|K|大小成比例的数据表项，然后通过哈希函数将K映射到各个表项中。Hash Tables通过将取值范围很大的键值映射到较小的集合中，极大地节省了存储空间，但同时引入了碰撞（Collision）的因素，即几个键值映射到同一表项的情况。由于处理碰撞而增加的复杂度，常常使查找或删除等操作的时间复杂度不再为O(1)，在最差的情况下甚至为O(n)（n = |K|）。但在实际中，通过选择合适的哈希函数，上述操作的时间复杂度常常能控制在接近O(1)。

The most important techniques behind Yahoo! are: hashing, hashing and hashing!

——前雅虎首席科学家Udi Manber

计算机科学中的一类基本问题是如何在内存中找到一段指定的信息（a “key”），这类问题常常被称为字典问题（dictionary problem）。对这类问题可以提出很多解决方案，但考虑的关键因素之一就是：如何在数据量快速增长的同时仍然保证查找的速度。Hashing就是满足这个条件的一种高效解决方案。

 

在解释hashing之前先来看一看key这个概念。根据NIST的定义，key是一组数据中的一部分，通过这部分信息来存储、索引整组信息。比如如果要给一组客户记录排序，就可以将客户姓名选作key，从而根据姓名按照字典序排列。这里要注意的一点是，key的选择不是绝对的，在不同的应用场合下，对同一组信息可能选择不同的key。例如，如果要将上面提到的客户记录作成财务汇报，那么key就可以选作客户的交易金额，从而根据交易金额进行排序。

 

Key的取值范围通常很大并且分布不均，哈希函数的目的就是将key映射到分布相对均匀且较小的整数集合。从很大的集合到较小的集合，从分布不均到分布均匀，这是哈希函数的两个基本特点。对于哈希函数的使用者来说，哈希函数既有随机性，又有确定性。随机性是指给定一个key，哈希函数的使用者完全不能预测这个key到底会被映射到哪个整数；确定性是指给定一个key，同一个哈希函数总会将它映射到同一个整数。

 

哈希函数的随机性保证了其对输入key的加密特性。通常情况下，哈希函数的输出值能够唯一标识输入的key，因此就像现实世界中的“指纹”能够唯一标识一个人一样，哈希函数的输出值也被叫做“数字指纹”（digital fingerprint）。当然，这只是哈希函数期望达到的境界，理论上由于哈希函数将大集合映射到了小集合，碰撞的可能一定存在。最近，山东大学的王小云教授（已经被挖到了清华）就破解了国际上流行的MD5和SHA-1两大哈希算法，在密码界引起了轩然大波。实际上，破解的过程就是进行碰撞攻击（collision attack），从而找到两个key映射到同一输出值的情况，这样就可以伪造数字指纹。

 

哈希函数的输出值能够唯一标识一个key，这本身就反映了哈希函数的确定性。在哈希表中，哈希函数被用来生成key的存储地址，正是由于确定性的存在，使得存储后的查找成为可能。哈希表最大的特点，就是它不随数据量的增大而速度变慢，因为记忆数据存储位置的任务交给了哈希函数。每一次查找数据的时间都是恒定的，即哈希函数的计算时间（不考虑碰撞的情况下）。这里我们可以看到哈希函数另一大作用：作为存储信息的载体。

 

如果我们想记录某个集合的哈希表地址，一般情况下我们会考虑将这个集合的哈希表地址存储在内存中，这无疑要消耗大量的空间，而且常常不可实现。在计算机科学中，时间换空间的情况经常发生，这里再一次印证了这个观点。为了不占用内存，我们设计合适的哈希函数来存储地址信息，在需要新的地址时，通过占用一定的CPU时间算出新地址。如同不同的情况下存储模式不同一样，在不同的应用场合中，也需要设计满足特定要求的哈希函数。例如，密码学中的哈希算法更多地考虑如何躲避恶意的攻击和伪造，而用在检错和纠错领域的哈希算法则更多地考虑如何将改动过的数据区分开来。具体的哈希算法会在后面介绍，这里就不多讲了。

从哈希存储到Bloom Filter

焦萌 2007年1月28日

先解释一下什么是哈希函数。哈希函数简单来说就是一种映射，它可取值的范围（定义域）通常很大，但值域相对较小。哈希函数所作的工作就是将一个很大定义域内的值映射到一个相对较小的值域内。

传统的哈希存储

假设要哈希的集合为S，它有n个元素。传统的哈希方法是，将哈希区域组织成h（h > n）个格子的列表，每一个格子都能存储S中的一个元素。存储时将S中的每一个元素映射到{0, 1, … , h-1}的范围内，然后以这个值为索引将此元素存储到对应的格子内。由于哈希函数将一个大集合映射到一个小集合中，所以存在将大集合中的多个元素映射到同一位置的情况，这就是所谓的碰撞（Collision）。当碰撞发生时，有多种策略可供选择，比如用链表将映射到同一位置的元素串起来，或者在碰撞发生时再进行哈希映射直到找到空位为止等等。

传统的哈希方法不会发生错误，而且存储的元素还可以复原。如果哈希函数选择得当，碰撞出现的情况比较少，那么查找某一个元素也很快。但是，如果你哈希某个集合只是为了判断某个元素是否在这个集合中，那么你会发现好像存储整个集合有点浪费。按传统的哈希方法判断某个元素是否属于集合时，会把这个元素和它映射位置上的元素进行匹配，如果完全匹配则说明属于集合，如果不匹配则不属于。在绝大部分查找都不能匹配的情况下（这常常是实际中的情况），我们会发现匹配的过程经常用不到整个元素，因为元素的一部分就可以判断不匹配了。基于“部分信息就能判断不匹配”这个思路，Burton Bloom（Bloom Filter的发明者）提出了一种改进的方法。

改进的哈希存储

在这种改进的方法中，哈希区域和前面一样仍然被组织成格子的列表。但这次并不直接将集合元素存在格子里，而是将每一个元素编码然后将编码存在格子里。假设每个集合元素要占b位，编码后要占c（c < b）位。由于编码位数少于元素位数，不同元素的编码有可能相同，因此在查找元素时可能会出现错误。编码位数取决于你期望的错误率：编码位数越多，错误就越少，反之则越大；当错误少到一定程度（大约2^-b），编码位数就足以存下整个元素，因此就变回了传统的哈希存储。

这种方法对传统的哈希存储进行了改良，允许用户在错误率和存储空间之间作权衡。这里我们已经能够看到Bloom Filter的一点端倪。如果说这种方法已经孕育了“正确率换空间”的思想的话，那么Bloom Filter更是这个思想的大胆实践，它完全摆脱了传统的哈希存储方法，在存储空间使用和减少错误率方面又进了一步。

Bloom Filter

在Bloom Filter中，哈希区域的每一位都被当成是独立的可寻址的单元。在对集合元素进行编码时，同时使用若干个独立的哈希函数，将每一个哈希函数映射的地址都置为1。这种编码方法可谓是另辟蹊径，摆脱了原来一个格子一个格子的存储方法。在改进的哈希存储中，编码位数是和正确率交换的筹码，而在Bloom Filter中，筹码变成了哈希函数的个数以及整个哈希区域（即位数组）的大小。如果想具体知道合适的哈希函数个数和位数组大小，请参阅第一篇Bloom Filter概念和原理。

和前面两种哈希存储方法相比，Bloom Filter最大的优势自然是它的空间效率。另外，由于Bloom Filter不用处理碰撞（Collision），因此它在增加或查找集合元素时所用的时间完全恒定（哈希函数的计算时间），无论集合元素本身有多大，也无论多少集合元素已经加入到了位数组中。由于Bloom Filter和改进的哈希存储都对集合元素进行了编码，因此想要从哈希区域中恢复集合元素并不容易。但同时，如果你不想让别人直接看到集合元素，这样的编码处理倒可以看成是一种加密，有效保护了你的隐私。

Bloom Filter很大的一个缺点就是不能删除元素。由于Bloom Filter不处理碰撞，有可能多个哈希函数都映射到了同一位，因此不能简单地在删除时将1置为0。后面我们会看到，Counting Bloom Filter通过将每一位扩展为一个Counter来解决这一问题。

参考资料

[1] B. Bloom. Space/Time Tradeoffs in Hash Coding with Allowable Errors. Communications of the ACM 13:7 (1970), 422—426.

[2] http://www.cs.berkeley.edu/~pbg/cs270/notes/lec27.pdf

[3] http://security.riit.tsinghua.edu.cn/seminar/2006_11_16/hash_function_yaxuan.ppt

ppPhone—基于Kademlia协议的P2P VoIP系统设计与实现

dolf cao(dolf.cao@gmail.com)

摘 要：点对点（P2P）技术和基于IP的语音VoIP（Voice Over IP）技术是当前Internet应用技术研究的两个热点，将二者相结合的P2P VoIP技术已经成为VoIP技术发展的一个趋势。本文从分析传统VoIP系统的不足入手，讨论了未来VoIP系统的发展趋势，提出了一种基于Kademlia协议的纯P2P的P2P VoIP架构，并在此基础上实现了一个P2P VoIP系统——ppPhone。

关键词：Kademlia；DHT；P2P VoIP；G.729；对等网；分布式哈希表

ppPhone—A Kademlia Based P2P VoIP System Design And Implementation

dolf cao(dolf.cao@gmail.com)

Abstract：Peer-to-Peer and Voice Over IP are the research hotspot in current Internet application technology. P2P VoIP Technology that combine the P2P and VoIP is a trend of VoIP development. This paper analysis the shortage of current P2P VoIP systems at first, then discuss the development trend of future VoIP system, and based on previous analysis, we put forward a kademlia protocol based pure P2P VoIP architecture, then we implement our kademlia based P2P VoIP system—ppPhone.

Key words：Kademlia；DHT；P2P VoIP;G.729
 

1 引言

点对点P2P（peer to peer）技术和基于IP的语音VoIP(Voice Over IP) 技术是当前互联网应用技术研究的两个热点。最近几年发展起来的P2PVoIP系统更是这两种技术融合后的一个重要发展方向。它通过利用P2P技术的高扩展性和健壮性的特点，给传统VoIP产业带来了更高效的沟通模式。P2P VoIP系统是指将P2P技术与VoIP技术相结合,P2P技术用于资源的查找定位及共享,来共同完成语音通信过程的系统。

当前，以Skype为代表的P2P VoIP系统发展迅速,已经成为人们日常生活中不可或缺的一种重要的联系手段。另外,诸如HeadCall， Gizmo， WengoPhone等P2P VoIP系统也拥有广大的用户群。相对于传统的C/S模式的VoIP系统，P2P VoIP系统具有稳定性好、部署简单及易用性好等优点；就目前的发展趋势来说，传统VoIP系统正逐渐的向基于P2P技术的方向发展。

但是由于目前的P2P VoIP系统多为商用系统，其核心技术是私有的，没有公开，而且多为国外系统，并且当前的P2P VoIP系统还有许多问题需要解决，因此有必要研究P2P VoIP系统，尤其是考虑到军队等国家重要部门的特殊性，更有必要研究自己的P2P VoIP系统。

Kademlia协议是一个广泛应用的基于分布式哈希表（DHT）的P2P协议，当前的许多P2P文件共享软件如Emule，BitTorrent，BitSprit，BitComet等都使用Kadmelia协议来实现底层的网络拓扑。协议的广泛应用证明，Kademlia协议是一个简单高效的P2P协议。

目前较成熟的适用于VoIP系统的P2P协议主要有Chord，Pastry，Tapestry，CAN和Kademlia。相比较于另外四种协议，Kademlia协议具有实现简单、查找效率高、资源定位准确以及更加成熟等优点，因此我们选用Kademlia协议作为底层协议来实现P2P VoIP系统——ppPhone。
 

2 Kademlia协议简介

P2P技术按照节点信息存储与搜索方式的不同，主要分为非结构化和结构化的P2P。

非结构化P2P系统中，每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息(如某个文件)会在那个节点上存储。因此，在非结构化P2P系统中，信息搜索的算法难免带有一定的盲目性，例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最近的n个节点开始，层层转发直到找到目标或超出了跳数的上限为止)。典型的非结构化P2P系统主要有：Gnutella，Napster等。非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等，网络的层次是单一的，而且节点之间无需维护拓扑信息。

结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，他们必须知道这些信息(或索引)可能存在于那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。但是，结构化P2P也引入了新的问题：

首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上。

其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点。

DHT（分布式哈希表）的引入基本解决了上述问题，因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。其中比较有代表性的有：缓冲阵列路由协议(CARP)；一致性哈希；Chord；内容寻址网络（CAN）；Pastry；Kademlia；P-Grid。

2.1 DHT

DHT（Distributed Hash Table），分布式哈希表技术使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。

DHT能够容纳数量巨大的节点数目，并且能不断处理新加入的节点，同时能够妥善地处理节点离开，具有很好的容错性。

将DHT作为应用层拓扑，可以构建更加复杂的应用，例如分布式文件系统，点对点文件共享，内容分发系统，协同web缓存，应用层组播，分布式域名解析以及即时消息服务。

2.2 Kademlia协议

Kademlia协议是美国纽约大学的PetarP. Maymounkov和David Mazieres在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on the XOR metric》。Kademlia通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT 拓扑结构，能够以比较快的速度执行路由查询。

Kademlia协议的每个节点保持一个哈希值、关键字对，并且将这个对保存在DHT中若干距节点逻辑距离在一定范围内的最“近”的节点上。

异或运算提供了一种在Kad网络上进行可靠距离度量的方法。由于异或运算的非负性、对称性、单向性、传递性以及三角不等性，从而能够保证距离与节点的一一对应的特性。

Kademlia协议实现了K-Bucket来实现节点查询。K-Bucket中保存以用户ID哈希值、对方IP地址和对方UDP端口这样的数据结构为单元的列表，列表首部保存最近最少访问的节点，尾部是最近最多访问的节点。当DHT接收到新节点加入请求时，如果此时K-Bucket没有满，那么就把新节点加入尾部；如果此时K-Bucket已经满了，就先对首部的节点发送消息，手部节点有响应的话那么忽略新节点加入请求，同时把首部有反馈的节点移动到尾部，如果首部节点没有反馈，则删除就删除尾部节点，加入新节点。这种新节点加入的处理方式能够很好的解决拒绝服务攻击，即使有很多节点同时到达要求加入网络，K-Bucket用自己的更新机制处理节点加入请求，而不会过载，从而避免了拒绝服务攻击的影响。

Kademlia协议定义了四种远程RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

PING 操作的作用是探测一个节点，用以判断其是否仍然在线。

STORE 操作的作用是通知一个节点存储一个<key , value>对。

FIND_NODE 操作使用一个160bit 的ID 作为参数。本操作的接受者返回它所知道的更接近目标ID 的K 个节点的(IP address ,UDP port , Node ID)信息。

FIND_VALUE 操作和FIND_NODE 操作类似，不同的是它只需要返回一个节点的( IP address , UDP port , Node ID)信息。如果本操作的接受者收到同一个key 的STORE 操作，则会直接返回存储的value 值。

采用Kademlia协议实现P2P VoIP系统是一个尝试，因为现在比较成型的P2P VoIP系统如Skype等P2P协议是私有的，而且下一小节将会介绍到Kademlia协议当前的应用，证明Kademlia协议是一个成熟的协议，用于P2P VoIP系统能避免许多不成熟的协议可能遇到的问题。

2.3 Kademlia协议应用

Kademlia协议应用范围较广，主要是P2P文件共享程序底层使用Kademlia协议来搭建Overlay，实现资源的存储、搜索和定位。

采用Kademlia协议实现的P2P文件共享程序主要有Emule，BitTorrent，BitSiprit，BitComet等。经过实践证明Kademlia协议是简单可靠的。目前Internet上大约有一半的网络流量为P2P流量，其中大部分为P2P文件共享程序产生的流量，而目前Emule，BitTorrent，BitSprit，BitComet都是很流行的P2P文件共享软件，因此可以不夸张地说，采用Kademlia协议的网络产生的流量占了很大一块Internet的流量。
 

3 ppPhone系统设计

3.1 ppPhone功能需求

ppPhone作为一个VoIP系统，应能实现以下功能：

l 新用户注册：系统注册新用户以及新用户加入网络；

l 用户退出：用户退出网络；

l 用户发布：在用户注册了一个用户名之后，将用户名及用户相关信息（IP地址及端口）发布到DHT中逻辑距离相近的节点上。

l 用户检索：给定一个用户名，将用户名哈希后，在DHT中查找到用户相关信息（IP地址及端口），并且将用户相关信息（IP地址及端口）返回。

l 语音通信：根据查找得到的用户相关信息（IP地址及端口），建立起语音通信信道，并且实现语音呼叫信令及语音编解码（采用G.729）。

l NAT及防火墙穿越：当用户处于内网或者防火墙之后时，提供一种用户穿越NAT和防火墙的方法。

l 与传统电话网及移动电话网互联互通：通过公共交换电信网（PSTN）与传统电信网实现互联，从而使得用户可以呼叫传统电话以及移动电话。

3.2 系统设计

系统主要概念和术语定义如下：

l 用户：ppPhone的终端实体，拥有唯一用户名、密码、姓名、年龄、性别、好友列表等属性。

l 结点：用户的载体，是连接到P2P网络的个人PC。

l 引导结点：一个P2P网络结点，为要加入P2P网络的结点提供一些联系人组成它的路由表。

l 注册服务器：为用户提供注册和认证功能，存储用户的用户名、密码、好友列表等信息，用户登录时对用户进行身份认证。注册服务器还保证用户名的全球唯一性。

l PSTN服务器：提供ppPhone网络节点与传统电话网及移动电话网通信的接口。

3.2.1 系统体系结构

在ppPhone中，所有的节点共同组成Overlay，注册（认证）服务器主要用于新用户的注册以及用户登录时的验证。用户通过PSTN服务器与传统电话网及移动电话网进行通信。ppPhone的体系结构不同于Skype，ppPhone中并没有超级节点（Super Node），所有的节点是完全对等的，实现完全相同的功能。因此ppPhone是一个纯P2P的VoIP系统。ppPhone系统体系结构如图1所示。

图1 ppPhone系统体系结构

3.2.2 系统模块设计

ppPhone系统主要包括用户界面、DHT模块、语音通信模块、注册服务器以及Bootstrap服务器共5个模块。系统模块与功能设计如图2所示。

图2 ppPhone系统模块图
 

4 ppPhone系统实现

基于上述设计，我们实现了ppPhone的原型系统，其中与传统电话网及移动电话网互联的部分由于条件限制还未能实现，其余各个功能均实现，系统运行良好，用户定位准确及时，语音通信质量较好。

4.1 系统平台

ppPhone在Windows XP上使用Visual Studio 2005开发，程序设计语言为C++，P2P模块基于Kademlia协议实现，语音编解码使用G.729的Codec，通信信令为自定义的信令。

4.2 系统具体实现

ppPhone流程主要有注册/认证、加入Kad网、发布用户ID、查找用户ID，呼叫的建立和释放、语音传输等。系统流程如图3所示。

图3 ppPhone系统流程图

用户在第一次启动时需到注册服务器注册，注册自己的用户名ID，密码等信息；若已注册，直接登录，到注册服务器进行身份认证。用户客户端注册/认证完毕后就可以加入Kad网，首先设置本地TCP、UDP端口，设置引导结点IP地址、端口号，然后就可以调用Kademlia协议模块加入DHT网络。用户节点在加入DHT网络时向整个网络发布用户ID，首先哈希用户ID，然后进行异或运算搜索与用户ID逻辑距离最近的一些结点，把用户ID，及所在的结点IP地址等信息存储到上面。为了保证这些结点的存活性和适应不断变化的网络拓扑结构，用户节点需要周期性的刷新发布信息。当用户节点试图呼叫某个用户时，需要在DHT网络上搜索该用户ID，找到该用户ID的发布信息，从而得到该用户ID所在结点的IP地址及端口号，即可建立语音通信信道。一旦用户查找到要呼叫的终端IP地址，就可以根据特定的信令协议向其发出呼叫请求，并随时可以终止呼叫。当呼叫建立后，语音数据就可以在两个终端间传送。

ppPhone系统主要有3个线程，其中一个DHT网络控制线程，一个DHT网络信息更新线程以及一个语音通信线程。网络底层通信链路Berkeley套接字。DHT网络控制线程初始化时，首先在端口20028开一个Listen Socket，不断侦听，在接受到DHT网络的数据包时进行处理；只要系统继续运行，此线程即一直在运行，不会退出。DHT网络信息更新线程是一个定时器，主要用于确认节点是否在线，此线程会周期性的向K-Bucket中的节点发送PING消息，没有响应的节点会被认为已经失效，从而保证K-Bucket中节点的有效性，当用户因为意外原因离开网络后，此线程也能及时发现。语音通信线程主要用于信令的传输以及语音数据的发送和接收。

5 总结

本文阐述了一个基于Kademlia协议的P2P VoIP系统的实现过程，初步实现了VoIP系统的功能；使用P2P来完成用户的查找与定位，能够有效的避免集中式服务器诸如单点故障等问题，并且能够以较好的速度来完成用户的查找和定位。相比较于传统的VoIP系统，P2P VoIP系统不需要配置即零配置、运营成本低、系统可靠性高，但是又有不便于管理等特点。在运营成本受限或者部署较大规模的VoIP系统时，P2P VoIP系统是一个很好的选择。
 

参考文献

【1】 Kademlia : A Peer-to-peer Information System Based on the XOR Metric. PetarP. Maymounkov, David Mazieres.

【2】 开源P2P文件共享项目BitTorrent www.bittorrent.com

【3】 开源P2P文件共享项目 Emule www.emule-project.net

【4】 开源P2P文件共享项目 BitSpirit http://www.bitspirit.com.cn/

【5】 开源P2P文件共享项目 BitComet www.bitcomet.com

【6】 基于混合结构P2P技术的IP电话软件原型与实现 汪亮宇硕士论文 北京航空航天大学

【7】 Skype www.skype.com

【8】 采用G.729的语言实时通信DLL(含测试源代码)

http://www.newasp.net/code/vc/2407.html

【9】 NetTalk http://nettalk.nwtbb.com/

【10】 Emule中Kademlia网络深入解析

http://dolfcao.spaces.live.com/

【11】 ppPhone系统实现 http://sourceforge.net/projects/ppphone