Home

总纲

1. 一个数组。
2. 拉链法(同一个bucket里的节点以doubly linked list组织起来，同时节点之间的内存地址尽量最短)。
3. 二叉树用来管理空闲节点。

rehash的过程如下(rehash)：

1. 把现在的数据move到old_table。
2. malloc一个新数组给到m_entries。
3. 调用build_tree在这个数组上构建一颗完美平衡二叉树，root节点的下标给到m_root。
4. old_table里的每一个元素插入到新表中。
5. rehash完成。

插入过程如下(insert_index_no_check)：

1. 通过index找到当前bucket所在的节点e。
2. 如果该节点e处于空闲状态，那么非常好，把该节点e从二叉树中删除，节点从空闲状态转换为使用状态，直接插入数据并返回。
3. 如果该节点e被使用，那么又分两种情况。
4. 待插入数据k和当前使用该节点e的数据vic的bucket不同(这个节点e的prev不为空，循着链表找到该bucket的第一个节点h，第一个节点h肯定不是当前节点e，从而推断出bucket不同)，那么要把占用该节点e的数据vic踢出，插入k，然后再递归调用insert_index_no_check以插入被踢出的数据vic。
5. 待插入数据k和当前使用该节点e的数据vic的bucket相同，说明他们应该处于同一个doubly linked list，请求二叉树分配一个空闲节点f，存入数据k，把节点f插入到doubly linked list的尾部。
6. 插入完成。