Dynamic Linear Hashing

Data Science 310

Boston University

Recall: On-Disk Hash Tables

• The hash value tells you which page the item should be on.
• Because pages are large, each page serves as a bucket that stores multiple items.
• Need to deal with full buckets.

• In dynamic hashing, the number of buckets can increase over time.

Recall: A Simplistic Approach to Dynamic Hashing

• Assume that:
  • we’re using keys that are strings
  • h(key) = number of characters in key
  • we use mod (%) to ensure we get a valid bucket number:
    • bucket index = h(key) % number of buckets

• When the hash table gets to be too full:
  • double the number of buckets
  • rehash all existing items. why? % may give a different result

Linear Hashing

• It does not use the modulus to determine the bucket index.

• Rather, it treats the hash value as a binary number, and it uses the i rightmost bits of that number:
  • i = ceil(log₂n) where n is the current number of buckets

• example: n = 3 → i = ceil(log₂3) = 2

Linear Hashing (cont.)

• example: n = 3 → i = ceil(log₂3) = 2

• If there’s a bucket with the index given by the i rightmost bits, put the key there.

h("if")   = 2 = 00000010

h("case") = 4 = 00000100

Where should an item with the key “class” go?

h("if")   = 2 = 00000010

h("case") = 4 = 00000100

h("class") = 5 = 00000101

A. bucket 0

B. bucket 1 ← yes: the rightmost i bits are 01

C. bucket 2

Linear Hashing (cont.)

• If there’s a bucket with the index given by the i rightmost bits, put the key there.

• If not, use the bucket specified by the rightmost i – 1 bits

h("if")   = 2 = 00000010

h("case") = 4 = 00000100

h("class") = 5 = 00000101

h("continue") = 8 = 00001000

h("for") = 3 = 00000011
(11 = 3 is too big, so use 1)

h("extends") = 7 = 00000111

Linear Hashing: Adding a Bucket

• In linear hashing, we keep track of three values:

• n, the number of buckets

• i, the number of bits used to assign keys to buckets

• f, some measure of how full the buckets are

• When f exceeds some threshold, we:
  • add only one new bucket

• increment n and update i as needed

• rehash/move keys as needed

• We only need to rehash the keys in one of the old buckets!

• if the new bucket’s binary index is 1xyz (xyz = arbitrary bits), rehash the bucket with binary index 0xyz

• This is in contrast to hashing with mod (%) which requires rehashing all keys.

Example of Adding a Bucket

• Assume that:
  • our measure of fullness, f = # of items in hash table
  • we add a bucket when f > 2*n

• Continuing with our previous example:
  • n = 3; f = 6 = 2*3, so we’re at the threshold

• adding “switch” exceeds the threshold, so we:

• add a new bucket whose index = 3 = 11 in binary

• increment n to 4 → i = ceil(log₂4) = 2 (unchanged)

Example of Adding a Bucket (cont.)

• Which previous bucket do we need to rehash?
  • new bucket has a binary index of 11

• because this bucket wasn’t there before, items that should now be in 11 were originally put in 01 (using the rightmost i – 1 bits)

• thus, we rehash bucket 01:

h("class") = 5 = 00000101 (leave where it is)

h("for") = 3 = 00000011 (move to new bucket)

h("extends") = 7 = 00000111 (move to new bucket)

Additional Details

• If the number of buckets exceeds 2ⁱ, we increment i and begin using one additional bit.

which bucket should be rehashed?

A. bucket 0 ← yes: 4 = 100, and items that should now be in that bucket were put in 000 = 0 (using the rightmost i – 1 bits)

B. bucket 1  C. bucket 2  D. bucket 3

Additional Details (cont.)

• The process of adding a bucket is sometimes referred to as splitting a bucket.

• example: adding bucket 4  ⇔  splitting bucket 0, because some of 0’s items may get moved to bucket 4

• The split bucket:
  • may retain all, some, or none of its items

• may not be as full as other buckets
  • thus, linear hashing still allows for overflow buckets as needed

More Examples

• Assume again that we add a bucket whenever the # of items exceeds 2n.
• What will the table below look like after inserting the following sequence of keys? (assume no overflow buckets are needed)

"toString":  h("toString")  = 8 = 00001000

"private":   h("private")   = 7 = 00000111

"interface": h("interface") = 9 = 00001001

which bucket should be split/rehashed? ← new bucket is 5 = 101, so rehash bucket 001

Hash Table Efficiency

• In the best case, search and insertion require at most one disk access.

• In the worst case, search and insertion require k accesses, where k is the length of the largest bucket chain.

• Dynamic hashing can keep the worst case from being too bad.

Hash Table Limitations

• It can be hard to come up with a good hash function for a particular data set.

• The items are not ordered by key. As a result, we can’t easily:
  • access the records in sorted order
  • perform a range search
  • perform a rank search – get the kth largest value of some field

• We can do all of these things with a B-tree / B+tree.

Which Index Structure Should You Choose?

• Recently accessed pages are stored in a cache in memory.
• Working set = collection of frequently accessed pages

• If the working set fits in the cache, use a B-tree / B+tree.
  • efficiently supports a wider range of queries (see last slide)

• If the working set can’t fit in memory:
  • choose a B-tree/B+tree if the workload exhibits locality
    • locality = a query for a key is often followed by a query for a key that is nearby in the space of keys

• because the items are sorted by key, the neighbor will be in the cache

• choose a hash table if the working set is very large
  • uses less space for “bookkeeping” (pointers, etc.), and can thus fit more of the working set in the cache

• fewer operations are needed before going to disk