Open hashing
From Wikipedia, the free encyclopedia
Open hashing is any hash method, where the data indexed by the hash is stored externally to the hash table. The data is initially divided up into groups, for instance each group might store ten items, and allocation be done on a first come, first served basis. In this case the 1st item goes in group 0, as does the 2nd etc, and 11th - 20th items would be in group 1. Each group is normally stored in its own file or 'chunk' of a file or memory, so that the system can quickly load up the entire group, these group storage areas are often called 'buckets'. The key that identifies a bucket is now put into the hash table (in this case it is as simple as the bucket number). Now, when we are looking for an item, we look up its entry in the hash table, and this tells us which bucket it is in. We then load up the bucket and retrieve the desired item from it. The advantage of Open hashing over Closed hashing is that the data stored in the bucket can be of variable size. Hash tables normally require the items stored in them to be the same size, since then it makes finding the n'th item as simple as 'Hash_Table_Start + (n * Item_Length). Hence, if we store a fixed length 'bucket pointer' in the hash table, we can put variable length data in the buckets.
