## Hash 结构

哈希表默认是支持动态扩容的，即当哈希表存放键值对大于 3/4 哈希桶的个数时，会 2 倍扩容。
哈希冲突时，Vector 长度认为是没有限制的。

### Hash 结构内存分布及结构体描述

哈希结构内存分布如下图所示：
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118093909785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzaDEzNDE3,size_16,color_FFFFFF,t_70)

### Hash 冲突时是如何解决的

哈希冲突解决分 2 中情况（具体代码在 lookup() 函数中）：
1、Key 和 Vlaue 都保存时
Hash 结构体中 log2_pair_size 不等于 0 是，存储的是 hash_pair_indirect_t 结构。使用 alloc_len 保存 hash_pair_t 结构数量。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094032581.png)
2、只保存 Key 时。
Hash结构体中 log2_pair_size= 0， 存储的是指针 hash_pair_t*，变成 vec_head_t 结构存储

![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094044324.png)

### Hash函数操作：

- 哈希函数创建 (hash.h)
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094145927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzaDEzNDE3,size_16,color_FFFFFF,t_70)
- Hash 函数操作
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094223110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzaDEzNDE3,size_16,color_FFFFFF,t_70)

### Mhash学习

- Mhash 结构及相关实现描述
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094425710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzaDEzNDE3,size_16,color_FFFFFF,t_70)
- Mhash 操作函数
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20191118094445227.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pzaDEzNDE3,size_16,color_FFFFFF,t_70)

### Hash 和 Mhash 的不同

1、对 Key 的处理， Hash 结构 Key 是需要使用的自己存储的，而 Mhash 结构内部会保存 Key 内容。
2、Mhash 和  Hash 都是不支持多核操作的，在使用中需要注意加锁。
3、Mhash 底层使用的是 Hash 操作函数。

### MHash使用的一些问题：

1、Mhash_free 函数存在内存泄露
对 key_tmps 内存释放是在源码中没有的；在 mhash_init 函数中是有的。

```
always_inline void
mhash_free (mhash_t * h)
{
  if (mhash_key_vector_is_heap (h))
    heap_free (h->key_vector_or_heap);
  else
    vec_free (h->key_vector_or_heap);
  vec_free (h->key_vector_free_indices);
   /*对key_tmps内存释放是在源码中没有的*/
   {
    int i;
    for (i = 0; i < vec_len (h->key_tmps); i++)
      vec_free (h->key_tmps[i]);
  }
  vec_free (h->key_tmps);
  hash_free (h->hash);
}

2、mhash_set和mhash_unset 对key_tmps的使用
always_inline void
mhash_sanitize_hash_user (mhash_t * mh)
{
  uword * hash = mh->hash;
  hash_t * h = hash_header (hash);
  h->user = pointer_to_uword (mh);
}

static uword mhash_set_tmp_key (mhash_t * h, void * key)
{
  u8 * key_tmp;
  int my_cpu = os_get_cpu_number();

  vec_validate(h->key_tmps, my_cpu);
  key_tmp = h->key_tmps[my_cpu];

  vec_reset_length (key_tmp);

  if (mhash_key_vector_is_heap (h))
    {
      uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;

      if (is_c_string)
	vec_add (key_tmp, key, strlen (key) + 1);
      else
	vec_add (key_tmp, key, vec_len (key));
    }
  else
    vec_add (key_tmp, key, h->n_key_bytes);

  h->key_tmps[my_cpu] = key_tmp;

  return ~0;
}


mhash_sanitize_hash_user (h);
/*i 一直返回全FF，但是怎么去查询hash对的*/
  i = mhash_set_tmp_key (h, key);

  p = hash_get_pair (h->hash, i);
```

`i = mhash_set_tmp_key (h, key); ` 操作是i返回的是全 F，如何来查询 Vlaue 的呢？
答案就在 Hash 函数中 mhash_key_to_mem，如果 Key 是全 F 就从 key_tmps 获取 Key。

```
static uword								\
  mhash_key_sum_##N_KEY_BYTES (hash_t * h, uword key)			\
  {									\
    mhash_t * hv = uword_to_pointer (h->user, mhash_t *);		\
    return mhash_key_sum_inline (mhash_key_to_mem (hv, key),		\
				 (N_KEY_BYTES),				\
				 hv->hash_seed);			\
  }									\
```