FPGA智能网卡-hash桶冲突_1000个桶的hash表插入50个元素,假设hash算法的打撒是均匀的,不发生冲突的概率

为什么需要hash来管理flow表

智能网卡芯片主要依据流的五元组来管理flow表；比如ipv4的报文，流的五元组是SIP(32bit)+DIP(32bit)+SPORT(16bit)+DPORT(16bit)+PROTO(8bit)，一共104bit；但是flow表的数量往往达不到如此大的规模；所以选择使用hash来压缩流表的地址空间；这可能会带来hash冲突问题；

什么是hash冲突

当不同的五元组的key通过hash算法得到相同的值，可以理解为是hash冲突；

计算hash冲突的概率

如下图所示，一般使用hash桶和hash slot来解决hash冲突的问题；我们可以假设hash表规格为k x m; 也就是k个hash桶，每个hash桶里面装有m个slot 元素；

下面开始计算概率，
对于hash表而言，比如有k个bucket；插入条目数为n，每个bucket里面含有 m 个slot ，那么对于bucket中hash冲突为m的概率为
p = Cnm x (1/k)m x (1-1/k)(n-m)

那么对于m =3， k = 8M, n = 1M的情况下： p(K=8M,m=3) = C1M3 x (1/8M)3 x (1-1/8M)(1M-3),
期望值E = p(m=3) x k = p(m=3)x8M = 2298;
如果对于m =4， k = 8M, n = 1M的情况下： p(k=8m,m=4) = C1M4 x (1/8M)4 x (1-1/8M)(1M-4),
期望值E = p(m=4) x k = p(m=4)x8M = 71；
其实我们不难计算出 p(k=8M,m=4) = (1/32)p(K=8M,m=3) 

其实我们不难计算出 p(k=16M,m=3) = (1/8)p(K=8M,m=3)

结论

• 以下可以作为结论，但是以上推导过程很不严谨；哈哈；

• 解决hash冲突可以通过两个办法
  方法一,增加hash桶的数量;
  方法二，增加hash桶slot的个数；
  但是增加hash桶slot的个数，对于解决hash冲突更加明显；以上对于工程上面的计算完全够了，自己也只是个码农，呜呜呜 。。。