CS240 IA
2009-03-13 00:12:58 UTC
Hi Everyone,
During the tutorial today, a student asked me to run through an example of
extendible hashing. So here one is:
We want to insert keys 01001, 00001, 01110, 11100, 10110, 10111 into a
table where each block of memory can hold 2 elements.
Initially, we have d = 0, and our dictionary points to one block of empty
memory
d = 0
[] -> () k = 0
Insert 01001
d = 0
[] -> (01001) k = 0
Insert 00001
d = 0
[] -> (01001, 00001) k = 0
Insert 01110, this causes an overflow:
d = 0
[] -> (01001, 00001, 01110) k = 0
Since the block is full and k = d, we need to do a directory split. d
increases to 1 and we increment k in each of the blocks:
d = 1
[0] -> (01001, 00001, 01110) k = 1
[1] -> () k = 1
Since a block is still full and k = d for that block, we have to do
another directory split. d increases to 2 and we increase k for the blocks
that have been split, giving us:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> () k = 1
Insert 11100.
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100) k = 1
Insert 10110.
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100, 10110) k = 1
Insert 10111, this causes an overflow:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100, 10110, 10111) k = 1
Since a block is full and k < d for that block, we split the block and
increment k for these blocks, giving us:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10] -> (10110, 10111) k = 2
[11] -> (11100) k = 2
Note that in that last step we didn't need to increase the global depth
(d), because the local depth (k) was less than d.
The student also asked me to do an example of deleting from an extendible
hash table. While the lecture notes do mention this, and say that it is
just the opposite of insertion, it is somewhat more complicated since you
need to keep track of when to do a global decrease in the size of the
dictionary. As such, I wouldn't worry about this coming up on a future
assignment or the final. However, interested students can check out this
paper, where some of these issues are mentioned:
http://www.ccs.neu.edu/home/donghui/publications/books/e_ds_extendiblehashing.pdf
Best,
Ben Lafreniere (CS240 IA)
During the tutorial today, a student asked me to run through an example of
extendible hashing. So here one is:
We want to insert keys 01001, 00001, 01110, 11100, 10110, 10111 into a
table where each block of memory can hold 2 elements.
Initially, we have d = 0, and our dictionary points to one block of empty
memory
d = 0
[] -> () k = 0
Insert 01001
d = 0
[] -> (01001) k = 0
Insert 00001
d = 0
[] -> (01001, 00001) k = 0
Insert 01110, this causes an overflow:
d = 0
[] -> (01001, 00001, 01110) k = 0
Since the block is full and k = d, we need to do a directory split. d
increases to 1 and we increment k in each of the blocks:
d = 1
[0] -> (01001, 00001, 01110) k = 1
[1] -> () k = 1
Since a block is still full and k = d for that block, we have to do
another directory split. d increases to 2 and we increase k for the blocks
that have been split, giving us:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> () k = 1
Insert 11100.
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100) k = 1
Insert 10110.
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100, 10110) k = 1
Insert 10111, this causes an overflow:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10,11] -> (11100, 10110, 10111) k = 1
Since a block is full and k < d for that block, we split the block and
increment k for these blocks, giving us:
d = 2
[00] -> (00001) k = 2
[01] -> (01001, 01110) k = 2
[10] -> (10110, 10111) k = 2
[11] -> (11100) k = 2
Note that in that last step we didn't need to increase the global depth
(d), because the local depth (k) was less than d.
The student also asked me to do an example of deleting from an extendible
hash table. While the lecture notes do mention this, and say that it is
just the opposite of insertion, it is somewhat more complicated since you
need to keep track of when to do a global decrease in the size of the
dictionary. As such, I wouldn't worry about this coming up on a future
assignment or the final. However, interested students can check out this
paper, where some of these issues are mentioned:
http://www.ccs.neu.edu/home/donghui/publications/books/e_ds_extendiblehashing.pdf
Best,
Ben Lafreniere (CS240 IA)