前提：搞懂https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/

Why

https://15445.courses.cs.cmu.edu/fall2022/project1/

待补充，可看原论文
设计要点：

  1. Page Fault
  2. Access Memory/Disk
  3. Dynamic File Organization
  4. Balance Radix Search Tree
  5. Static & Dynamic Hash

Concepts

  1. $h$: fixed hash function
  2. $K$: is a key
  3. $K’$: $h(K)$, also $pseudokey$.
    • We choose pseudokeys to be of fixed length, such as 32 bits.
    • The pseudokeys are of fixed length, the keys need not be.
  4. $I(K)$: is associated information: either the record associated with $K$, or a pointer to the record.

Struct

基本结构如下：

  1. Two levels: $directory$ and $leaves$
    • The leaves contain pairs$(K, I(K))$
    • The directory contains pointers to leaf pages
  2. Depth d: the depth $d$ of the directory.

  3. Directory pointers:

    • First, There is a pointer to a leaf that stores all keys $K$ for which the pseudokey $K’ = h(K)$ starts with $d$ consecutive zeros.
      directory第一个指针指向的leaf中所有的$K$有下面的特征：$K’$前$d$位都是0
    • 第二个指针指向的leaf中所有的$k’$前$d$位是0...01，第三个是0...010，后面以此类推。
    • 所以directory总共$2^d$个pointer

  4. Find $K$:

    • 计算出$K’$, 找出其前$d$位.
    • 找到这$d$位对应的是directory哪个pointer
    • 然后可以找到leaf，在leaf中遍历pairs

  5. Leaf header:

    • Each leaf page has a header that contains a local depth $d’$ for the leaf page.
    • 举例directory中 000 pointer指向的leaf: Local depth 2 means that not only does this leaf page contain all keys whose pseudokey begins with 000, but even more, it containsall keys whose pseudokey begins with the 2 bits 00. Thus the 001 pointer also points to this leaf page.
    • $d’ <= d$

Insert

这里以lab的要求为准：

  • 在编程中计算后$d$位比较方便，和上面看前$d$位有所区别，但是原理相同
  • leaf在lab中称为Bucket

Structure

lab中extendible hash table结构如下：

1
2
3
4
int global_depth_;    // The global depth of the directory
size_t bucket_size_;  // The size of a bucket
int num_buckets_;     // The number of buckets in the hash table
std::vector<std::shared_ptr<Bucket>> dir_;  // The directory of the hash table

Bucket结构：

1
2
3
4
template <typename K, typename V>
size_t size_;
int depth_;
std::list<std::pair<K, V>> list_;

所以dir_里面保存了directory pointer，bucket_size_代表每个bucket最大容量是多少，Bucket中的list_保存了上述讲的pairs

Init

初始情况下global_depth为0，总共有$2^0=1$个bucket，所以num_buckets=1，bucket_size每个用例都是不一样的，每个bucket里面都还是空的。

Indexof

For the given key, return the entry index in the directory where the key hashes to.

1
2
3
4
5
template <typename K, typename V>
auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t {
  int mask = (1 << global_depth_) - 1;
  return std::hash<K>()(key) & mask;
}
  • mask
    • 对1左移global_depth位，即在1的二进制后面加global_depth个0，然后-1
    • 比如(1<<4)-1: 1<<4 可以写成二进制形式 10000，然后再减去 1，为 1111。
    • 所以这mask为global_depth个1
  • std::hash<K>()(key) & mask
    • 这里取&为的是将index控制在一定数量的位数上，该位数由globaldepth变量确定，也就是index不能超过$2^d$，比如global_depth=2，有4个bucket，index最大为3，3的二进制是11，正好是global_depth个1
    • 这里意思也就是看后global depth位

Case1

1
auto table = std::make_unique<ExtendibleHashTable<int, std::string>>(2);

这里bucket_size为2

1
2
table->Insert(1, "a");
table->Insert(2, "b");

image-20230426112938666

1
table->Insert(3, "c");

这时候bucket已经满了，正常情况下处理bucket满的策略有两个，double directory和split bucket only。

采用哪个策略需要看global depth和已满的bucket的local depth：

Bucket Full

  • 如果global depth == local depth，需要double directory。为什么呢，这是由两个depth代表的意思决定，两个相等，代表该bucket只有一个directory pointer指向，没有多余的pointer来指向了，只能是增加pointer。至于为什么是double呢，我想这里可能和二进制方便运算有关系吧，也许这样处理起来比较规整？
  • 因为local depth不会大于global depth（两个相等时double directory，global depth都会+1），所以还有一种情况是global depth > local depth，global depth代表了找到key需要看后几位bit，local depth代表了该bucket里面的key后local depth位都是相同的，当global depth > local depth时，因为看的位数的差异，自然会有多个directory pointer指向这个bucket，那么这时候只需要split bucket就好了，有多余的pointer能指向新的bucket。

Double Directory

这里global depth和local depth相等，所以执行double directory逻辑，假设原先满的bucket是bucket j：

  1. global depth = global depth+1

  2. directory翻倍，多出来的pointer按顺序指向原pointer

    • 比如原先directory size为4，double后变成8，那么多出来的dir_[4]指向dir_[0]，dir_[5]指向dir_[1]，6指向2，7指向3。
    • 假设这里每个directory pointer只有一个对应的bucket，那么这里的操作就是每个bucket多了个pointer指向。
    • 这里其实也好理解，比如原先pointer是010，double directory后，无非就是多了一位二进制，对应到directory要么是0010，要么是1010，因为local depth目前还没有到+1的地步，所以这两个先指向同一个bucket也可以。

  3. 创建一个新的bucket z，设置bucket j、bucket z的local depth=global depth

  4. 对bucket j的里面所有的key执行rehash操作，判断该key是留在bucket j还是移动到bucket z。

  5. 重试插入操作，一般情况下会插入成功，某些情况下会插入失败，比如rehash时候所有的key还是在bucket j，这时候就需要重新执行插入逻辑，重新判断是需要 double directory还是split bucket。

  6. 一般情况下如果选择的hash函数合适的话，那么一次split即可。极端情况下会退化生成静态hash那样解决冲突，同时应该设定最大的directory depth）。

Rehash

rehash过程其实就是看bucket j里面所有的key是放在bucket j还是bucket z。在double directory的情况下，多看了一位，所以是新增二进制位（也可以说是从低到高第global depth/local depth位，此时global depth=local depth）为1的话就放在bucket z。

这里实现的方式有两种，一种是直接调用erase将key从bucket中移除，另外一种是使用先将key放到hashmap<directory index, value list>，然后根据hashmap的key重新将value分配到bucket，因为每次只涉及到两个bucket，所以hashmap的length不大于2，理想情况是2，极端情况是1，也就是上面讲的所有的key都还在bucket j。

因为directory中可能有多个index指向bucket j，所以这里还得更新下别的index指向。这里处理的逻辑是，遍历所有的index，如果这个index之前指向的是bucket j，但是对应的新增的二进制位是1的话，就需要将这个index指向bucket z。

Insert

回到table->Insert(3, "c");，此时执行double directory和Rehash逻辑

image-20230506153403500

1
table->Insert(4, "d");

image-20230506153552617

1
table->Insert(5, "e");

需要插入index为01的位置，执行double directory逻辑

image-20230506154531571

1
table->Insert(6, "f");

此时需要插入index=10对应的bucket，该bucket已经满了，因为global depth > local depth，所以执行split bucket逻辑即可。

Split Bucket

  1. 创建一个新的bucket z，设置bucket j、bucket z的local depth= local depth + 1
  2. 对bucket j的里面所有的key执行rehash操作，判断该key是留在bucket j还是移动到bucket z。
    • 这里和double directory的逻辑有点区别，但是大体相似。这里看的是从低到高第local depth位是否为1，因为只变了local depth。同样也得处理多个index指向同一个bucket的情况。
  3. 重试插入的操作和double directory操作一样

Insert

1
table->Insert(6, "f");

image-20230506160229598

1
table->Insert(7, "g");

image-20230506160405852

1
table->Insert(8, "h");

image-20230506160507560

1
table->Insert(9, "i");
1
2
3
4
5
6
7
8
9
dir_ global depth: 3
0 local depth(2): [4,8,]
1 local depth(3): [1,9,]
2 local depth(2): [2,6,]
3 local depth(2): [3,7,]
4 local depth(2): [4,8,]
5 local depth(3): [5,]
6 local depth(2): [2,6,]
7 local depth(2): [3,7,]

Case2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
auto table = std::make_unique<ExtendibleHashTable<int, int>>(2);
table->Insert(4, 0);
table->Insert(12, 0);
table->Insert(16, 0);
table->Insert(64, 0);
table->Insert(31, 0);
table->Insert(10, 0);

table->Insert(51, 0);
table->Insert(15, 0);
table->Insert(18, 0);
table->Insert(20, 0);

table->Insert(7, 0);
table->Insert(23, 0);
table->Insert(11, 0);
table->Insert(19, 0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
[Init] bucket_size:2
===========[Insert]key: 4 ,value:0
[FindBucket] key:4, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,]
===========[Insert]key: 12 ,value:0
[FindBucket] key:12, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,]
===========[Insert]key: 16 ,value:0
[FindBucket] key:16, dir_index:0
key_bucket is full
global_depth: 0 local depth: 0
before RedistributeBucket
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,]
after RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,]
1 local depth(1): []
[FindBucket] key:16, dir_index:0
key_bucket is full
global_depth: 1 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,]
1 local depth(1): []
after RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,]
1 local depth(1): []
2 local depth(2): []
3 local depth(1): []
[FindBucket] key:16, dir_index:0
key_bucket is full
global_depth: 2 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,]
1 local depth(1): []
2 local depth(2): []
3 local depth(1): []
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): []
1 local depth(1): []
2 local depth(2): []
3 local depth(1): []
4 local depth(3): [4,12,]
5 local depth(1): []
6 local depth(2): []
7 local depth(1): []
[FindBucket] key:16, dir_index:0
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,]
1 local depth(1): []
2 local depth(2): []
3 local depth(1): []
4 local depth(3): [4,12,]
5 local depth(1): []
6 local depth(2): []
7 local depth(1): []
===========[Insert]key: 64 ,value:0
[FindBucket] key:64, dir_index:0
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): []
2 local depth(2): []
3 local depth(1): []
4 local depth(3): [4,12,]
5 local depth(1): []
6 local depth(2): []
7 local depth(1): []
===========[Insert]key: 31 ,value:0
[FindBucket] key:31, dir_index:7
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,]
2 local depth(2): []
3 local depth(1): [31,]
4 local depth(3): [4,12,]
5 local depth(1): [31,]
6 local depth(2): []
7 local depth(1): [31,]
===========[Insert]key: 10 ,value:0
[FindBucket] key:10, dir_index:2
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,]
2 local depth(2): [10,]
3 local depth(1): [31,]
4 local depth(3): [4,12,]
5 local depth(1): [31,]
6 local depth(2): [10,]
7 local depth(1): [31,]
===========[Insert]key: 51 ,value:0
[FindBucket] key:51, dir_index:3
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,]
2 local depth(2): [10,]
3 local depth(1): [31,51,]
4 local depth(3): [4,12,]
5 local depth(1): [31,51,]
6 local depth(2): [10,]
7 local depth(1): [31,51,]
===========[Insert]key: 15 ,value:0
[FindBucket] key:15, dir_index:7
key_bucket is full
global_depth: 3 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,]
2 local depth(2): [10,]
3 local depth(1): [31,51,]
4 local depth(3): [4,12,]
5 local depth(1): [31,51,]
6 local depth(2): [10,]
7 local depth(1): [31,51,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,]
3 local depth(2): [31,51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,]
7 local depth(2): [31,51,]
[FindBucket] key:15, dir_index:7
key_bucket is full
global_depth: 3 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,]
3 local depth(2): [31,51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,]
7 local depth(2): [31,51,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,]
3 local depth(3): [51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,]
7 local depth(3): [31,]
[FindBucket] key:15, dir_index:7
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,]
3 local depth(3): [51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,]
7 local depth(3): [31,15,]
===========[Insert]key: 18 ,value:0
[FindBucket] key:18, dir_index:2
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,]
===========[Insert]key: 20 ,value:0
[FindBucket] key:20, dir_index:4
key_bucket is full
global_depth: 3 local depth: 3
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(3): [4,12,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,]
after RedistributeBucket
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(3): [31,15,]
[FindBucket] key:20, dir_index:4
insert success
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(3): [31,15,]
===========[Insert]key: 7 ,value:0
[FindBucket] key:7, dir_index:7
key_bucket is full
global_depth: 4 local depth: 3
before RedistributeBucket
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(3): [31,15,]
after RedistributeBucket
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): []
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
[FindBucket] key:7, dir_index:7
insert success
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
===========[Insert]key: 23 ,value:0
[FindBucket] key:23, dir_index:7
insert success
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,23,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
===========[Insert]key: 11 ,value:0
[FindBucket] key:11, dir_index:11
insert success
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,11,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,23,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,11,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
===========[Insert]key: 19 ,value:0
[FindBucket] key:19, dir_index:3
key_bucket is full
global_depth: 4 local depth: 3
before RedistributeBucket
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,11,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,23,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(3): [51,11,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
after RedistributeBucket
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(4): [51,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,23,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(4): [11,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]
[FindBucket] key:19, dir_index:3
insert success
PrintDir:
dir_ global depth: 4
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(4): [51,19,]
4 local depth(4): [4,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(4): [7,23,]
8 local depth(3): [16,64,]
9 local depth(2): []
10 local depth(2): [10,18,]
11 local depth(4): [11,]
12 local depth(4): [12,]
13 local depth(2): []
14 local depth(2): [10,18,]
15 local depth(4): [31,15,]

Case3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TEST(ExtendibleHashTableTest, GetNumBuckets2) {
auto table = std::make_unique<ExtendibleHashTable<int, std::string>>(4);

table->Insert(4, "a");
table->Insert(12, "a");
table->Insert(16, "a");
table->Insert(64, "a");
table->Insert(31, "a");
table->Insert(10, "a");
table->Insert(51, "a");
table->Insert(15, "a");
table->Insert(18, "a");
table->Insert(20, "a");
table->Insert(7, "a");
table->Insert(23, "a");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
[Init] bucket_size:4
===========[Insert]key: 4 ,value:a
[FindBucket] key:4, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,]
===========[Insert]key: 12 ,value:a
[FindBucket] key:12, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,]
===========[Insert]key: 16 ,value:a
[FindBucket] key:16, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,]
===========[Insert]key: 64 ,value:a
[FindBucket] key:64, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,64,]
===========[Insert]key: 31 ,value:a
[FindBucket] key:31, dir_index:0
key_bucket is full
global_depth: 0 local depth: 0
before RedistributeBucket
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,64,]
after RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): []
[FindBucket] key:31, dir_index:1
insert success
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): [31,]
===========[Insert]key: 10 ,value:a
[FindBucket] key:10, dir_index:0
key_bucket is full
global_depth: 1 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): [31,]
after RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,]
2 local depth(2): []
3 local depth(1): [31,]
[FindBucket] key:10, dir_index:2
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,]
2 local depth(2): [10,]
3 local depth(1): [31,]
===========[Insert]key: 51 ,value:a
[FindBucket] key:51, dir_index:3
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,51,]
2 local depth(2): [10,]
3 local depth(1): [31,51,]
===========[Insert]key: 15 ,value:a
[FindBucket] key:15, dir_index:3
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,51,15,]
2 local depth(2): [10,]
3 local depth(1): [31,51,15,]
===========[Insert]key: 18 ,value:a
[FindBucket] key:18, dir_index:2
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,]
===========[Insert]key: 20 ,value:a
[FindBucket] key:20, dir_index:0
key_bucket is full
global_depth: 2 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [31,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,]
4 local depth(3): [4,12,]
5 local depth(1): [31,51,15,]
6 local depth(2): [10,18,]
7 local depth(1): [31,51,15,]
[FindBucket] key:20, dir_index:4
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,]
4 local depth(3): [4,12,20,]
5 local depth(1): [31,51,15,]
6 local depth(2): [10,18,]
7 local depth(1): [31,51,15,]
===========[Insert]key: 7 ,value:a
[FindBucket] key:7, dir_index:7
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,15,7,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(1): [31,51,15,7,]
6 local depth(2): [10,18,]
7 local depth(1): [31,51,15,7,]
===========[Insert]key: 23 ,value:a
[FindBucket] key:23, dir_index:7
key_bucket is full
global_depth: 3 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [31,51,15,7,]
2 local depth(2): [10,18,]
3 local depth(1): [31,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(1): [31,51,15,7,]
6 local depth(2): [10,18,]
7 local depth(1): [31,51,15,7,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(2): [31,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(2): [31,51,15,7,]
[FindBucket] key:23, dir_index:7
key_bucket is full
global_depth: 3 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(2): [31,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(2): [31,51,15,7,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(3): [4,12,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,7,]
[FindBucket] key:23, dir_index:7
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): []
2 local depth(2): [10,18,]
3 local depth(3): [51,]
4 local depth(3): [4,12,20,]
5 local depth(2): []
6 local depth(2): [10,18,]
7 local depth(3): [31,15,7,23,]

Case4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
auto table = std::make_unique<ExtendibleHashTable<int, int>>(4);
table->Insert(4, 4);
table->Insert(12, 12);
table->Insert(16, 16);
table->Insert(64, 64);
table->Insert(5, 5);
table->Insert(10, 10);
table->Insert(51, 51);
table->Insert(15, 15);
table->Insert(18, 18);
table->Insert(20, 20);
table->Insert(7, 7);
table->Insert(21, 21);
table->Insert(11, 11);
table->Insert(19, 19);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
[Init] bucket_size:4
===========[Insert]key: 4 ,value:4
[FindBucket] key:4, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,]
===========[Insert]key: 12 ,value:12
[FindBucket] key:12, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,]
===========[Insert]key: 16 ,value:16
[FindBucket] key:16, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,]
===========[Insert]key: 64 ,value:64
[FindBucket] key:64, dir_index:0
insert success
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,64,]
===========[Insert]key: 5 ,value:5
[FindBucket] key:5, dir_index:0
key_bucket is full
global_depth: 0 local depth: 0
before RedistributeBucket
PrintDir:
dir_ global depth: 0
0 local depth(0): [4,12,16,64,]
after RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): []
[FindBucket] key:5, dir_index:1
insert success
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): [5,]
===========[Insert]key: 10 ,value:10
[FindBucket] key:10, dir_index:0
key_bucket is full
global_depth: 1 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 1
0 local depth(1): [4,12,16,64,]
1 local depth(1): [5,]
after RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,]
2 local depth(2): []
3 local depth(1): [5,]
[FindBucket] key:10, dir_index:2
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,]
2 local depth(2): [10,]
3 local depth(1): [5,]
===========[Insert]key: 51 ,value:51
[FindBucket] key:51, dir_index:3
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,51,]
2 local depth(2): [10,]
3 local depth(1): [5,51,]
===========[Insert]key: 15 ,value:15
[FindBucket] key:15, dir_index:3
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,51,15,]
2 local depth(2): [10,]
3 local depth(1): [5,51,15,]
===========[Insert]key: 18 ,value:18
[FindBucket] key:18, dir_index:2
insert success
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,]
===========[Insert]key: 20 ,value:20
[FindBucket] key:20, dir_index:0
key_bucket is full
global_depth: 2 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 2
0 local depth(2): [4,12,16,64,]
1 local depth(1): [5,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [5,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,]
4 local depth(3): [4,12,]
5 local depth(1): [5,51,15,]
6 local depth(2): [10,18,]
7 local depth(1): [5,51,15,]
[FindBucket] key:20, dir_index:4
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [5,51,15,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,]
4 local depth(3): [4,12,20,]
5 local depth(1): [5,51,15,]
6 local depth(2): [10,18,]
7 local depth(1): [5,51,15,]
===========[Insert]key: 7 ,value:7
[FindBucket] key:7, dir_index:7
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [5,51,15,7,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(1): [5,51,15,7,]
6 local depth(2): [10,18,]
7 local depth(1): [5,51,15,7,]
===========[Insert]key: 21 ,value:21
[FindBucket] key:21, dir_index:5
key_bucket is full
global_depth: 3 local depth: 1
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(1): [5,51,15,7,]
2 local depth(2): [10,18,]
3 local depth(1): [5,51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(1): [5,51,15,7,]
6 local depth(2): [10,18,]
7 local depth(1): [5,51,15,7,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,]
2 local depth(2): [10,18,]
3 local depth(2): [51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,]
6 local depth(2): [10,18,]
7 local depth(2): [51,15,7,]
[FindBucket] key:21, dir_index:5
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,21,]
2 local depth(2): [10,18,]
3 local depth(2): [51,15,7,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,21,]
6 local depth(2): [10,18,]
7 local depth(2): [51,15,7,]
===========[Insert]key: 11 ,value:11
[FindBucket] key:11, dir_index:3
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,21,]
2 local depth(2): [10,18,]
3 local depth(2): [51,15,7,11,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,21,]
6 local depth(2): [10,18,]
7 local depth(2): [51,15,7,11,]
===========[Insert]key: 19 ,value:19
[FindBucket] key:19, dir_index:3
key_bucket is full
global_depth: 3 local depth: 2
before RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,21,]
2 local depth(2): [10,18,]
3 local depth(2): [51,15,7,11,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,21,]
6 local depth(2): [10,18,]
7 local depth(2): [51,15,7,11,]
after RedistributeBucket
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,21,]
2 local depth(2): [10,18,]
3 local depth(3): [51,11,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,21,]
6 local depth(2): [10,18,]
7 local depth(3): [15,7,]
[FindBucket] key:19, dir_index:3
insert success
PrintDir:
dir_ global depth: 3
0 local depth(3): [16,64,]
1 local depth(2): [5,21,]
2 local depth(2): [10,18,]
3 local depth(3): [51,11,19,]
4 local depth(3): [4,12,20,]
5 local depth(2): [5,21,]
6 local depth(2): [10,18,]
7 local depth(3): [15,7,]