CODEWITHSUNDEEP
databasehashindexinghashtable
user1902535
user1902535

Reputation: 155

Whats is wrong with this extendible hashing solution?

I'm trying to grasp the concept of extendible hashing, but I'm getting confused about the distribution of values to the buckets.

For example:

Say I want to insert 6 values from scratch: 17, 32, 14, 50, 35, 21

What would be wrong with this as a solution:

Global depth = 2
Bucket size = 2

00[] --> [][]
01[] --> [][]
10[] --> [][]
11[] --> [][]

Does this mean only one value for each hash value will be pointed to the bucket, so then you increment the global depth? Or would this work?

I understand the beginning of the process, I am just confused at this point.

Upvotes: 1

Views: 272

Answers (2)

Ujjwal
Ujjwal

Reputation: 79

There is nothing wrong in the solution that you've provided just that the global depth need not be increased. The solution is perfectly compatible with the given global depth.

Assuming that we choose the directory and the corresponding bucket using the 2 left most bits. Then, the solution would look like the following
Also the numbers in the binary format would look like the following

17 - 010001
32 - 100000
14 - 001110
50 - 110010
35 - 100011
21 - 010101

directory ------------- buckets
00-----------------------> 14 |
01-----------------------> 17 | 21
10-----------------------> 32 | 35
11-----------------------> 50 |

Hope this helps.

Upvotes: 3

norekhov
norekhov

Reputation: 4318

You shouldn't increment global depth. The whole idea of the hash is to select such function that it would put items in a buckets more or less equally.

That depends on a hash function. You can use something as complex as md5 as a hash and than you will get 1 element in 1 bucket but you're not really guaranteed that there will be only 1.

So a general implementation should use binary search on buckets and some other search inside bucket. You can't and you shouldn't change hash function on the fly.

Upvotes: 0

Related Questions