利用可扩展 hash 方法对以下记录进行 hash 存储: 3, 5, 7, 12, 16 设 hash 函数 h(x)= x mod 8,其中散列函数 h(k)是一个 b(足够大)位二进制序列,序列的前d位用作索引,来区分每个元素属于哪个桶。 现要求每个桶至多包含2个元素,以上元素按从左往右的顺序依次添加。开始时只使用 序列的前1位作索引(即d=1),当桶满时进行分裂,d相应增大。请画出添加完以上 所有元素后,最终的索引结构
时间: 2024-03-26 21:41:16 浏览: 60
首先,根据散列函数 h(x)= x mod 8,将给定的记录 hash 存储。得到以下结果:
| 桶0 | 桶1 | 桶2 | 桶3 | 桶4 | 桶5 | 桶6 | 桶7 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 16 | 5 | | 7 | 3 | 12 | | |
由于要求每个桶至多包含2个元素,因此桶0和桶1需要分裂。此时,将序列的前2位用作索引,得到以下结果:
| 桶00 | 桶01 | 桶10 | 桶11 | 桶2 | 桶3 | 桶4 | 桶5 | 桶6 | 桶7 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 16 | | 5 | | 7 | 3 | 12 | | | |
现在,桶01、桶10、桶11需要分裂。将序列的前3位用作索引,得到以下结果:
| 桶000 | 桶001 | 桶010 | 桶011 | 桶100 | 桶101 | 桶110 | 桶111 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 16 | | 5 | | 7 | 3 | 12 | |
由于每个桶至多包含2个元素,现在的索引结构已经满足要求。最终的索引结构如下:
```
+----+----+----+----+----+----+----+----+
| 00 | 01 | 10 | 11 | 2 | 3 | 4 | 5 |
+-------+----+----+----+----+----+----+----+----+
| 000 | 16 | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 001 | | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 010 | 5 | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 011 | | | | 7 | | | | |
+-------+----+----+----+----+----+----+----+----+
| 100 | | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 101 | 3 | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 110 | 12 | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
| 111 | | | | | | | | |
+-------+----+----+----+----+----+----+----+----+
```
阅读全文