# Open vSwitch系列之数据结构解析深入分析Hmap

```/* A hash map. */
struct hmap {
struct hmap_node **buckets; /* Must point to 'one' iff 'mask' == 0. 哈希桶 其实就是哈希数组的意思.指针数组. 当mask=0始终指向成员one的地址*/
size_t n; /* 保存该hash-map中的所有hmap_node节点个数 */
};
/* A hash map node, to be embedded inside the data structure being mapped. */
struct hmap_node {
size_t hash;                /* Hash value. 哈希值*/
struct hmap_node *next;     /* Next in linked list. 单向链表*/
};```

1、初始化hmap的函数

```/* Initializes 'hmap' as an empty hash table. */
void
hmap_init(struct hmap *hmap)
{
hmap->one = NULL;
hmap->n = 0;
}```

```#define hmap_insert(HMAP, NODE, HASH) \
hmap_insert_at(HMAP, NODE, HASH, SOURCE_LOCATOR)
//插入hmap
static inline void
hmap_insert_at(struct hmap *hmap, struct hmap_node *node, size_t hash,
const char *where)
{
hmap_insert_fast(hmap, node, hash); // 快速插入，在链表头插入。新节点作为链表头
if (hmap->n / 2 > hmap->mask) {// if成立则需要调整hmap的大小，即hash桶buckets指针数组大小。 注：因为除2操作，保证链表个数最大为2。
hmap_expand_at(hmap, where);
}
}
//快速插入
static inline void
hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash)
{
node->hash = hash;
node->next = *bucket; // 调整链表
*bucket = node; //调整链表
hmap->n++;
}
// 扩充hmap大小
void
hmap_expand_at(struct hmap *hmap, const char *where)
{
COVERAGE_INC(hmap_expand);
}
}
static void
resize(struct hmap *hmap, size_t new_mask, const char *where)
{
struct hmap tmp;
size_t i;
//初始化临时hmap
hmap_init(&tmp);
tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1))
for (i = 0; i <= tmp.mask; i++) {
tmp.buckets[i] = NULL;
}
}
//将已经存在hmap中元素迁移到临时hmap tmp中
for (i = 0; i <= hmap->mask; i++) {
struct hmap_node *node, *next;
int count = 0;
for (node = hmap->buckets[i]; node; node = next) {
next = node->next;
hmap_insert_fast(&tmp, node, node->hash);
count++;
}
if (count > 5) {
static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
COVERAGE_INC(hmap_pathological);
VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%"PRIuSIZE" nodes, %"PRIuSIZE" buckets)",
where, count, hmap->n, hmap->mask + 1);
}
}
//交换两个hmap的结构并且释放到临时hmap，其实在释放临时的tmp的时候其实释放的是hmap，因为交换了嘛！！！
hmap_swap(hmap, &tmp);
hmap_destroy(&tmp);
}```

2）临时变量bucket进行*操作后，取值为0，即为NULL。

3）代码*bucket = node; 则将one置为0xbffff03c。

```if (hmap->n / 2 > hmap->mask) {
hmap_expand_at(hmap, where);
}```

```hmap_swap(hmap, &tmp); //将hmap结构中对应数据进行交换
hmap_destroy(&tmp);// 这个释放其实原先hmap中内存。 但是首次buckets存储的内容是one的地址，因此不会调用free函数。```

1608 篇文章96 人订阅

0 条评论

## 相关文章

### Python基础学习笔记之（二）（华工大神）

Python中每一个.py脚本定义一个模块，所以我们可以在一个.py脚本中定义一个实现某个功能的函数或者脚本，这样其他的.py脚本就可以调用...

1214

3497

2054

1313

### Java中的private、protected、public和default的区别(详解)

（1）对于public修饰符，它具有最大的访问权限，可以访问任何一个在CLASSPATH下的类、接口、异常等。它往往用于对外的情况，也就是对象或类对外的一种接口...

853

1443

### 深入理解JVM--(1)运行时的数据区域划分--java虚拟机栈

之前我们了解了程序计数器，接下来了解第二个线程私有的数据区域--虚拟机栈。 虚拟机栈是线程私有的，每创建一个线程，虚拟机就会为这个线程创建一个虚拟机栈，虚...

3225

### Java static 静态方法 并发(是否线程安全)

public class TestUitl { public static User setName(User user,String name) { ...

8946

### 看看你对队列的了解有多少？

1.1队列概念及基本操作 队列(Queue) 简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中...

3625

21710