由于在工作中因为业务场景用到的cuckoo hash算法比较多，下面会具体分析下在dpdk代码中的cuckoo实现，在lib/librte_hash/下有其他若干种hash就不一一介绍了，比较简单，先文字介绍下bloom filter和cuckoo hash。

bloom filter：“似于bitmap这样的hashset，所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞”，“带来的问题：一个是误报（false positives），在查询时能提供“一定不存在”，但只能提供“可能存在”，因为存在其它元素被映射到部分相同bit位上，导致该位置1，那么一个不存在的元素可能会被误报成存在；另一个是漏报（false nagatives），同样道理，如果删除了某个元素，导致该映射bit位被置0，那么本来存在的元素会被漏报成不存在。由于后者问题严重得多，所以bloom filter必须确保“definitely no”从而容忍“probably yes”，不允许元素的删除。”[http://coolshell.cn/articles/17225.html]
在一些场景中比如区块链中交易和区块数据的快速判断，使用数组只存储key不存储数据，根据交易和区块的sha256哈希值快速判断当前需要同步给对等节点的交易数据和区块数据是否已同步过，这样虽然可能存在漏报，即交易a和交易c映射的bit置为1后，同步a,c，后面来了交易b，然后映射后的位置bit都为1误以为已经同步过，故不同步，当然这些不成问题，会由其他的对等节点同步。截取bitcoin/src/bloom.h中CBloomFilter类部分声明：

 44 class CBloomFilter
 45 {
 46 private:
 47     std::vector<unsigned char> vData;
 48     bool isFull;
 49     bool isEmpty;
 50     unsigned int nHashFuncs;
 51     unsigned int nTweak;
 52     unsigned char nFlags;

cuckoo hash：“哈希函数是成对的，每一个元素都有两个，分别映射到两个位置，一个是记录的位置，另一个是备用位置。这个备用位置是处理碰撞时用的。cuckoo hashing处理碰撞的方法，就是把原来占用位置的这个元素踢走，被踢出去的元素有一个备用位置可以安置，如果备用位置上还有元素，再把它踢走，如此往复。直到被踢的次数达到一个上限，才确认哈希表已满，并执行rehash操作。”[http://coolshell.cn/articles/17225.html]

下面开始真正分析源码中的实现。
先来看看cuckoo中key的比较函数，求key的hash函数原型和hash表结构：

 66 /** Signature of key that is stored internally. */
 67 typedef uint32_t hash_sig_t;
 68 
 69 /** Type of function that can be used for calculating the hash value. */
 70 typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, uint32_t init_val);
 72
 73 /** Type of function used to compare the hash key. */
 74 typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len);

183 /** A hash table structure. */
184 struct rte_hash {
185     char name[RTE_HASH_NAMESIZE];   /**< Name of the hash. */
186     uint32_t entries;               /**< Total table entries. */
187     uint32_t num_buckets;           /**< Number of buckets in table. */
188     uint32_t key_len;               /**< Length of hash key. */
189     rte_hash_function hash_func;    /**< Function used to calculate hash. */
190     uint32_t hash_func_init_val;    /**< Init value used by hash_func. */
191     rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
192     /**< Custom function used to compare keys. */
193     enum cmp_jump_table_case cmp_jump_table_idx;
194     /**< Indicates which compare function to use. */
195     uint32_t bucket_bitmask;        /**< Bitmask for getting bucket index
196                         from hash signature. */
197     uint32_t key_entry_size;         /**< Size of each key entry. */
198 
199     struct rte_ring *free_slots;    /**< Ring that stores all indexes
200                         of the free slots in the key table */
201     void *key_store;                /**< Table storing all keys and data */
202     struct rte_hash_bucket *buckets;    /**< Table with buckets storing all the
203                             hash values and key indexes
204                             to the key table*/
212 } __rte_cache_aligned;

165 /* Structure that stores key-value pair */
166 struct rte_hash_key {
167     union {
168         uintptr_t idata;
169         void *pdata;
170     };
171     /* Variable key size */
172     char key[0];
173 } __attribute__((aligned(KEY_ALIGNMENT)));

154 /* Structure storing both primary and secondary hashes */
155 struct rte_hash_signatures {
156     union {
157         struct {
158             hash_sig_t current;
159             hash_sig_t alt;
160         };
161         uint64_t sig;
162     };
163 };

175 /** Bucket structure */
176 struct rte_hash_bucket {
177     struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES];
178     /* Includes dummy key index that always contains index 0 */
179     uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];
180     uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
181 } __rte_cache_aligned;

其中rte_hash_custom_cmp_eq和cmp_jump_table_idx是用于指定哪种类型的key比较函数，用户也可以自己实现，其他字段会在下面使用到的地方作说明，这里仅仅考虑单线程操作hash表，即线程a不会去操作线程b的hash表[设计错误]，也不会出现线程a和b操作hash表[有锁费性能，尽量充分理解业务选择适合的方案]。截取部分如下：

 72  * based on the key size and custom function.
 73  */
 74 enum cmp_jump_table_case {
 75     KEY_CUSTOM = 0,
 76     KEY_16_BYTES,
 77     KEY_32_BYTES,
 78     //more
 86 };
 87 
 88 /*
 89  * Table storing all different key compare functions
 90  * (multi-process supported)
 91  */
 92 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
 93     NULL,
 94     rte_hash_k16_cmp_eq,
 95     rte_hash_k32_cmp_eq,
 96     //more 
 97 };

 34 /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */
 35 static int
 36 rte_hash_k16_cmp_eq(const void *key1, const void *key2,
 37             size_t key_len __rte_unused)
 38 {
 39     uint64_t x0, x1, y0, y1;
 40 
 41     asm volatile(
 42         "ldp %x[x1], %x[x0], [%x[p1]]"
 43         : [x1]"=r"(x1), [x0]"=r"(x0)
 44         : [p1]"r"(key1)
 45         );
 46     asm volatile(
 47         "ldp %x[y1], %x[y0], [%x[p2]]"
 48         : [y1]"=r"(y1), [y0]"=r"(y0)
 49         : [p2]"r"(key2)
 50         );
 51     x0 ^= y0;
 52     x1 ^= y1;
 53     return !(x0 == 0 && x1 == 0);
 54 }
 55 
 56 static int
 57 rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len)
 58 {
 59     return rte_hash_k16_cmp_eq(key1, key2, key_len) ||
 60         rte_hash_k16_cmp_eq((const char *) key1 + 16,
 61                 (const char *) key2 + 16, key_len);
 62 }

以下代码分析省略了些细节。
创建[实现200多行]：

 113 struct rte_hash *
 114 rte_hash_create(const struct rte_hash_parameters *params)
 115 {
 116     struct rte_hash *h = NULL;
 117     struct rte_tailq_entry *te = NULL;
 118     struct rte_hash_list *hash_list;
 119     struct rte_ring *r = NULL;
 120     char hash_name[RTE_HASH_NAMESIZE];
 121     void *k = NULL;
 122     void *buckets = NULL;
 123     char ring_name[RTE_RING_NAMESIZE];
 124     unsigned num_key_slots;
 125     unsigned hw_trans_mem_support = 0;
 126     unsigned i;
 127 
 128     hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 159     num_key_slots = params->entries + 1;
 160 
 161     snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
 162     /* Create ring (Dummy slot index is not enqueued) */
 163     r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots - 1),
 164             params->socket_id, 0);
 165     if (r == NULL) {
 166         RTE_LOG(ERR, HASH, "memory allocation failed\n");
 167         goto err;
 168     }
 169 
 170     snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
 171 
 172     rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 173 
 174     /* guarantee there's no existing: this is normally already checked
 175      * by ring creation above */
 176     TAILQ_FOREACH(te, hash_list, next) {
 177         h = (struct rte_hash *) te->data;
 178         if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
 179             break;
 180     }
 181     h = NULL;
 182     if (te != NULL) {
 183         rte_errno = EEXIST;
 184         te = NULL;
 185         goto err_unlock;
 186     }
 187 
 188     te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
 189     if (te == NULL) {
 190         RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
 191         goto err_unlock;
 192     }
 193 
 194     h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
 195                     RTE_CACHE_LINE_SIZE, params->socket_id);
 196 
 197     if (h == NULL) {
 198         RTE_LOG(ERR, HASH, "memory allocation failed\n");
 199         goto err_unlock;
 200     }
 201 
 202     const uint32_t num_buckets = rte_align32pow2(params->entries)
 203                     / RTE_HASH_BUCKET_ENTRIES;
 204 
 205     buckets = rte_zmalloc_socket(NULL,
 206                 num_buckets * sizeof(struct rte_hash_bucket),
 207                 RTE_CACHE_LINE_SIZE, params->socket_id);
 208 
 209     if (buckets == NULL) {
 210         RTE_LOG(ERR, HASH, "memory allocation failed\n");
 211         goto err_unlock;
 212     }
 213 
 214     const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
 215     const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
 216 
 217     k = rte_zmalloc_socket(NULL, key_tbl_size,
 218             RTE_CACHE_LINE_SIZE, params->socket_id);
 219 
 220     if (k == NULL) {
 221         RTE_LOG(ERR, HASH, "memory allocation failed\n");
 222         goto err_unlock;
 223     }
 270     /* Setup hash context */
 271     snprintf(h->name, sizeof(h->name), "%s", params->name);
 272     h->entries = params->entries;
 273     h->key_len = params->key_len;
 274     h->key_entry_size = key_entry_size;
 275     h->hash_func_init_val = params->hash_func_init_val;
 276 
 277     h->num_buckets = num_buckets;
 278     h->bucket_bitmask = h->num_buckets - 1;
 279     h->buckets = buckets;
 280     h->hash_func = (params->hash_func == NULL) ?
 281         DEFAULT_HASH_FUNC : params->hash_func;
 282     h->key_store = k;
 283     h->free_slots = r;
 302     /* Populate free slots ring. Entry zero is reserved for key misses. */
 303     for (i = 1; i < params->entries + 1; i++)
 304         rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
 305 
 306     te->data = (void *) h;
 307     TAILQ_INSERT_TAIL(hash_list, te, next);
 308     rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 309 
 310     return h;
 320 }
 132 /** Number of items per bucket. */
 133 #define RTE_HASH_BUCKET_ENTRIES     4

以上创建过程主要包括：设置key-value的个数num_key_slots；创建无锁环形buffer；加写锁先判断是否已存在名字一样的hash表，如果有的话则跳转至err_unlock，释放写锁和相关的资源[代码被省略]，没有的话创建并关联hash表；每个桶可以容纳4个数据[至于为什么是4而不是其他值，会在最后说明]，计算多少个桶并申请空间用于存储hash值和状态等信息；计算存储num_key_slots个key_entry_size 的空间用于存储key和value的指针[这里桶里并不存储实际的数据]；最后给hash表各个变量关联；把hash表加入到全局hash_list中并释放写锁；

查找：

 698 static inline int32_t
 699 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
 700                     hash_sig_t sig, void **data)
 701 {
 702     uint32_t bucket_idx;
 703     hash_sig_t alt_hash;
 704     unsigned i;
 705     struct rte_hash_bucket *bkt;
 706     struct rte_hash_key *k, *keys = h->key_store;
 707 
 708     bucket_idx = sig & h->bucket_bitmask;
 709     bkt = &h->buckets[bucket_idx];
 710 
 711     /* Check if key is in primary location */
 712     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 713         if (bkt->signatures[i].current == sig &&
 714                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 715             k = (struct rte_hash_key *) ((char *)keys +
 716                     bkt->key_idx[i] * h->key_entry_size);
 717             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 718                 if (data != NULL)
 719                     *data = k->pdata;
 720                 /*
 721                  * Return index where key is stored,
 722                  * substracting the first dummy index
 723                  */
 724                 return bkt->key_idx[i] - 1;
 725             }
 726         }
 727     }
 728 
 729     /* Calculate secondary hash */
 730     alt_hash = rte_hash_secondary_hash(sig);
 731     bucket_idx = alt_hash & h->bucket_bitmask;
 732     bkt = &h->buckets[bucket_idx];
 733 
 734     /* Check if key is in secondary location */
 735     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 736         if (bkt->signatures[i].current == alt_hash &&
 737                 bkt->signatures[i].alt == sig) {
 738             k = (struct rte_hash_key *) ((char *)keys +
 739                     bkt->key_idx[i] * h->key_entry_size);
 740             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 741                 if (data != NULL)
 742                     *data = k->pdata;
 743                 /*
 744                  * Return index where key is stored,
 745                  * substracting the first dummy index
 746                  */
 747                 return bkt->key_idx[i] - 1;
 748             }
 749         }
 750     }
 751 
 752     return -ENOENT;
 753 }

根据sig值[key的hash值]索引到可能在哪个桶，然后先在primary location试着查找，一共可能要比较RTE_HASH_BUCKET_ENTRIES次，如果桶上的hash有效且等于该hash值，那么根据索引和key-value大小计算出该key-value位置，并对key的内容进行比较，相同的话则取得指向实际数据的指针；没有找到对sig再求hash，在secondary location位置上找，过程同上，找不到就返回-ENOENT；

删除：

 813 static inline int32_t
 814 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
 815                         hash_sig_t sig)
 816 {
 817     uint32_t bucket_idx;
 818     hash_sig_t alt_hash;
 819     unsigned i;
 820     struct rte_hash_bucket *bkt;
 821     struct rte_hash_key *k, *keys = h->key_store;
 822     int32_t ret;
 823 
 824     bucket_idx = sig & h->bucket_bitmask;
 825     bkt = &h->buckets[bucket_idx];
 826 
 827     /* Check if key is in primary location */
 828     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 829         if (bkt->signatures[i].current == sig &&
 830                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 831             k = (struct rte_hash_key *) ((char *)keys +
 832                     bkt->key_idx[i] * h->key_entry_size);
 833             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 834                 remove_entry(h, bkt, i);
 835 
 836                 /*
 837                  * Return index where key is stored,
 838                  * substracting the first dummy index
 839                  */
 840                 ret = bkt->key_idx[i] - 1;
 841                 bkt->key_idx[i] = 0;
 842                 return ret;
 843             }
 844         }
 845     }
 846 
 847     /* Calculate secondary hash */
 848     alt_hash = rte_hash_secondary_hash(sig);
 849     bucket_idx = alt_hash & h->bucket_bitmask;
 850     bkt = &h->buckets[bucket_idx];
 851 
 852     /* Check if key is in secondary location */
 853     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 854         if (bkt->signatures[i].current == alt_hash &&
 855                 bkt->signatures[i].sig != NULL_SIGNATURE) {
 856             k = (struct rte_hash_key *) ((char *)keys +
 857                     bkt->key_idx[i] * h->key_entry_size);
 858             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 859                 remove_entry(h, bkt, i);
 860 
 861                 /*
 862                  * Return index where key is stored,
 863                  * substracting the first dummy index
 864                  */
 865                 ret = bkt->key_idx[i] - 1;
 866                 bkt->key_idx[i] = 0;
 867                 return ret;
 868             }
 869         }
 870     }
 871 
 872     return -ENOENT;
 873 }

 785 static inline void
 786 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
 787 {
 808     rte_ring_sp_enqueue(h->free_slots,
 809             (void *)((uintptr_t)bkt->key_idx[i]));
 811 }

删除过程同查找有一大部分相同的，primary location找不到在secondary location上找，在找到对应的数据后，从桶中删除元素[并非删除指针指向的数据，交给用户自己处理]；这里remove_entry把索引值强转成void *压入ring buffer，作用会在hash表插入过程中说明；

插入：

 493 static inline int32_t
 494 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
 495                         hash_sig_t sig, void *data)
 496 {
 497     hash_sig_t alt_hash;
 498     uint32_t prim_bucket_idx, sec_bucket_idx;
 499     unsigned i;
 500     struct rte_hash_bucket *prim_bkt, *sec_bkt;
 501     struct rte_hash_key *new_k, *k, *keys = h->key_store;
 502     void *slot_id = NULL;
 503     uint32_t new_idx;
 504     int ret;
 505     unsigned n_slots;
 506     unsigned lcore_id;
 508 
 512     prim_bucket_idx = sig & h->bucket_bitmask;
 513     prim_bkt = &h->buckets[prim_bucket_idx];
 514     rte_prefetch0(prim_bkt);
 515 
 516     alt_hash = rte_hash_secondary_hash(sig);
 517     sec_bucket_idx = alt_hash & h->bucket_bitmask;
 518     sec_bkt = &h->buckets[sec_bucket_idx];
 519     rte_prefetch0(sec_bkt);

 540     if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)
 541          return -ENOSPC;

 544     new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
 545     rte_prefetch0(new_k);
 546     new_idx = (uint32_t)((uintptr_t) slot_id);
 547 
 548     /* Check if key is already inserted in primary location */
 549     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 550         if (prim_bkt->signatures[i].current == sig &&
 551                 prim_bkt->signatures[i].alt == alt_hash) {
 552             k = (struct rte_hash_key *) ((char *)keys +
 553                     prim_bkt->key_idx[i] * h->key_entry_size);
 554             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 555                 /* Enqueue index of free slot back in the ring. */
 556                 enqueue_slot_back(h, cached_free_slots, slot_id);
 557                 /* Update data */
 558                 k->pdata = data;
 559                 /*
 560                  * Return index where key is stored,
 561                  * substracting the first dummy index
 562                  */
 563                 return prim_bkt->key_idx[i] - 1;
 564             }
 565         }
 566     }
 568     /* Check if key is already inserted in secondary location */
 569     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 570         if (sec_bkt->signatures[i].alt == sig &&
 571                 sec_bkt->signatures[i].current == alt_hash) {
 572             k = (struct rte_hash_key *) ((char *)keys +
 573                     sec_bkt->key_idx[i] * h->key_entry_size);
 574             if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 575                 /* Enqueue index of free slot back in the ring. */
 576                 enqueue_slot_back(h, cached_free_slots, slot_id);
 577                 /* Update data */
 578                 k->pdata = data;
 579                 /*
 580                  * Return index where key is stored,
 581                  * substracting the first dummy index
 582                  */
 583                 return sec_bkt->key_idx[i] - 1;
 584             }
 585         }
 586     }
 587 
 588     /* Copy key */
 589     rte_memcpy(new_k->key, key, h->key_len);
 590     new_k->pdata = data;
 591 
 614         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 615             /* Check if slot is available */
 616             if (likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) {
 617                 prim_bkt->signatures[i].current = sig;
 618                 prim_bkt->signatures[i].alt = alt_hash;
 619                 prim_bkt->key_idx[i] = new_idx;
 620                 break;
 621             }
 622         }
 623 
 624         if (i != RTE_HASH_BUCKET_ENTRIES) {
 627             return new_idx - 1;
 628         }
 636         ret = make_space_bucket(h, prim_bkt);
 637         if (ret >= 0) {
 638             prim_bkt->signatures[ret].current = sig;
 639             prim_bkt->signatures[ret].alt = alt_hash;
 640             prim_bkt->key_idx[ret] = new_idx;
 643             return new_idx - 1;
 644         }

 648     /* Error in addition, store new slot back in the ring and return error */
 649     enqueue_slot_back(h, cached_free_slots, (void *)((uintptr_t) new_idx));
 653     return ret;
 654 }

以上代码删除了一些根据编译设置不同而相关的代码[对齐不太好办]，应该不影响分析。这段代码先计算出primary和secondary桶，然后进行预取；然后检查free_slots是否还有空闲，对应着hash表结构的注释“Ring that stores all indexes of the free slots in the key table”，和删除一个元素后的操作remove_entry，只是把hash表key_idx的索引值压入buffer，后期插入的时候需要获得一个；然后查找主和备，如果存在key一样的则更新data，否则就拷贝key和保存data地址，行589〜590；以上查找primary location时的代码段和secondary location的判断条件：

if (prim_bkt->signatures[i].current == sig && prim_bkt->signatures[i].alt == alt_hash)
if (sec_bkt->signatures[i].current == alt_hash && sec_bkt->signatures[i].alt == sig)

可以思考下“为什么要这么写？如果只判断第一个条件而不加上第二个条件会有什么问题？两个if第一个等号左值不一样？”；然后修改primary桶元素的信息，行614〜622，这里有空位置插入成功则返回，否则进入make_space_bucket函数：

 409 static inline int
 410 make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
 411 {
 412     static unsigned int nr_pushes;
 413     unsigned i, j;
 414     int ret;
 415     uint32_t next_bucket_idx;
 416     struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES];
 417 
 418     /*
 419      * Push existing item (search for bucket with space in
 420      * alternative locations) to its alternative location
 421      */
 422     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 423         /* Search for space in alternative locations */
 424         next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;
 425         next_bkt[i] = &h->buckets[next_bucket_idx];
 426         for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
 427             if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE)
 428                 break;
 429         }
 430 
 431         if (j != RTE_HASH_BUCKET_ENTRIES)
 432             break;
 433     }
 435     /* Alternative location has spare room (end of recursive function) */
 436     if (i != RTE_HASH_BUCKET_ENTRIES) {
 437         next_bkt[i]->signatures[j].alt = bkt->signatures[i].current;
 438         next_bkt[i]->signatures[j].current = bkt->signatures[i].alt;
 439         next_bkt[i]->key_idx[j] = bkt->key_idx[i];
 440         return i;
 441     }
 442 
 443     /* Pick entry that has not been pushed yet */
 444     for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++)
 445         if (bkt->flag[i] == 0)
 446             break;
 447 
 448     /* All entries have been pushed, so entry cannot be added */
 449     if (i == RTE_HASH_BUCKET_ENTRIES || nr_pushes > RTE_HASH_MAX_PUSHES)
 450         return -ENOSPC;
 451 
 452     /* Set flag to indicate that this entry is going to be pushed */
 453     bkt->flag[i] = 1;
 454 
 455     nr_pushes++;
 456     /* Need room in alternative bucket to insert the pushed entry */
 457     ret = make_space_bucket(h, next_bkt[i]);
 458     /*
 459      * After recursive function.
 460      * Clear flags and insert the pushed entry
 461      * in its alternative location if successful,
 462      * or return error
 463      */
  464     bkt->flag[i] = 0;
 465     nr_pushes = 0;
 466     if (ret >= 0) {
 467         next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;
 468         next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;
 469         next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
 470         return i;
 471     } else
 472         return ret;
 473 
 474 }

如果不能在primary location上插入的话，则尝试调用make_space_bucket在secondary location上进行首次插入(b)；这个会引起refresh操作，即secondary location被占用了，然后相应的数据要被重新hash等，故会形成递归调用；以上实现大致是：422〜433行对该桶上的元数(a)的alt重新求索引到哪个桶，有空位置了break，为要插入的元素(b)让出位置；435〜441行更新(a)[由primary变成secondary，则secondary变成primary如此反复，即第一次插入是主，被踢一次变成备，再被踢一次变成主...]，然后返回并更新(b)；如果没有找到则要递归，在递归前需要标示什么时候hash表满了，返回-ENOSPC，444〜455行干了这个事；如果递归返回到464行清标示[要反返回成功要么-ENOSPC]，并根据返回值进行更新(a)，466〜470行干了这个事；最后结束，633〜644行更新(b)；
在以上过程中refresh会在一定的条件下终止：nr_pushes > RTE_HASH_MAX_PUSHES[100]或某个桶上的slot都make_space_bucket过。

还有一些接口比较简单，基本都是以上增删查过程的补充，可以对着声明和注释看下该接口实现的功能。

整个过程梳理一下，总结下hash表中有几个关键性成员变量的作用：由于实际的数据并不存在于hash表中，但会拷贝key的数据，由rte_hash_key中key表示，只是存储了该数据起始地址，和key的地址；故key_store用来存储key和value的address，但是我怎么知道rte_hash_key存在哪个地方呢？是由rte_hash_bucket结构中key_idx的索引值乘以一个偏移量key_entry_size来决定的；其实由可以看出来k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size)；buckets用于表明key有没有存在，在创建的时候作用也说明了if (bkt->signatures[i].current == sig && bkt->signatures[i].sig != NULL_SIGNATURE)；free_slots用于存储key_store哪些是空着的，毕竟key_store有元素的时候不一定是连续占位的。

问题：
为什么桶内的元素个数为4?
答：在论文中http://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
“the space-optimal bucket size depends on the target false positive rate ε: when ε > 0.002, having two entries per bucket yields slightly better results than using four entries per bucket; when ε decreases to 0.00001 < ε ≤ 0.002, four entries per bucket minimizes space”；“because it achieves the best or close-to-best space efficiency for the false positive rates”；“b = 4 entries per bucket that saves one bit per item. ”；
“每个桶（bucket）有4路槽位（slot）。当哈希函数映射到同一个bucket中，在其它三路slot未被填满之前，是不会有元素被踢的，这大大缓冲了碰撞的几率。笔者自己的简单实现上测过，采用二维哈希表（4路slot）大约80%的占用率（CMU论文数据据说达到90%以上，应该是扩大了slot关联数目所致）”

参考：
http://coolshell.cn/articles/17225.html
https://en.wikipedia.org/wiki/Bloom_filter
https://en.wikipedia.org/wiki/Cuckoo_hashing