哈希文件组织和哈希索引组织之间有什么区别?

假设您有两个记录,一个带“foo”键,一个带“bar”键。假设记录是64字节的固定长度,“foo”散列为0x4000,“bar”散列为0x0100。

在“散列文件组织”中,有一个函数接受搜索键并直接计算地址。因此,如果将“foo”和“bar”添加到文件中,“foo”的记录将从文件中的地址0x4000开始,“bar”记录将从文件中的地址0x0100开始。

文件看起来像这样:

Address Range         Contents
-------------         --------
0x0000 - 0x00FF       empty space
0x0100 - 0x013F       "bar" record
0x0140 - 0x3FFF       empty space
0x0400 - 0x403F       "foo" record

在“散列索引组织”中,有一个辅助数据结构——索引——它告诉您特定记录的起始位置。假设文件为空,然后添加“foo”。哈希函数计算0x4000的值。将其添加到索引(散列映射或类似的内容)中,由于文件为空,因此分配的值为0。添加第二条记录“bar”时,将添加0x0100的散列键,并且指定的值为0x0040。你有一个索引:

Key     Value
-------------
0x0100  0x0040
0x4000  0x0000

文件看起来是这样的:

Address Range        Contents
-----------------------------
0x0000 - 0x003F      "foo" record
0x0040 - 0x007F      "bar" record

当然,你必须把索引存储在某个地方。它可以在单独的文件中,或者可能在数据文件的前面或后面,或者分散在整个文件中。很多不同的可能性。

在第一种情况下,文件中有很多浪费的空间,但是可以直接查找记录的位置:散列键,结果就是记录的地址。

在第二种情况下,散列键,然后在索引中查找结果以获取记录的键。这里的主要优点是,它可能会在文件中节省大量空间,但是您很难在哪里存储索引。

在这两种情况下,都必须有某种方法来解决散列冲突。