earlier I write about lowlevel fs and relayfs, as an example.
What I've said there, that I do not understand the use of a hash
table, was true then, but
now I do. I still do not see why a hash function is used, but a hash
table for inodes and entries
is very usefull.
When writing a lowlevel fs, you have to find a way your fs will
administer (right spelling?)
the inodes. The highlevel does that for you, at the lowlevel your fs
has to do that.
Now, It became clear to me that there are various ways to set up the
way inodes stored:
one big linked list, or one seperate index, or with the help of a
hashtable (and a little bit of linked list).
You'll need to have some system here, your fs has to determine the
right inode 'record' in memory
knowing the inode number.
Now, with one linked list :
inodea -> inodeb -> inodec ->.....
your fs has to walk through all the inode one by one, which is not
If you have a lot of inodes, well obvious very inefficient.(O(n))
Second an index, like we know from databases.
How to maintain it, I do not know, but you'll need to have an array
which has the same size as the number of inodes.
With a good search function this is of order O(logn). But it's necessary to
The third is used in relayfs, which is a combination of a sort of
index (a hash table) and a linked list.
A hash function is used to create a value like:
hashfunction(inode) % tabelsize. (A)
This is not an unique operation. The modulo operation is responseable for that.
The value tablesize+1 has the same result as 1 (which is 1).
Now with relayfs al the inodes with the same result are kept in one
linked list. A hashtable
(with as parameter the result of A) points to the first record. Maybe
this is the record looked
for, then ready. If not, this record points to another record with the
same value A. And so on.
I still do not understand the reason the (complicated) hash function
is used, especially, the most important
operation is the modulo. This make the whole function not unique.
Maybe some of you use another way.
Well, maybe some of you know all this. But maybe not.