Quick Index
Overview


This discussion is about one of the core concepts for hash tables -- load ratio.

We'll explain "load ratio" by example, below.

We'll also refer to load ratio as keysPerBucket.

Note that in the examples, to help picture what is going on, we'll use keysPerBucket (loadRatio) values of e.g., 3. In reality, keysPerBucket would be about 0.75. The math does not change.

Terms


The terms used to define load ratio are a bit implicit.

We'll define load ratio using explicit terms.

Term Used
in Examples
Below		Common Term
in Literature		Note
keysPerBucketloadRatioaverage number of keys per bucket
keyCountsizekey count
bucketCountlengthbucket count (hash table length)


Equations


keysPerBucket (Governing Equation)
keysPerBucket a.k.a. "load ratio"
keysPerBucket = keyCount / bucketCount
bucketCount
bucketCount a.k.a. "length" (hash table length)
bucketCount = keyCount / keysPerBucket
keyCount (size)
keyCount a.k.a. "size"
keyCount = bucketCount * keysPerBucket


Simple Example


Compute keysPerBucket

Given:
	keyCount = 15
	bucketCount = 5
Compute:
	keysPerBucket = 15/5 = 3
	(keysPerBucket is an average)
Compute bucketCount

Given:
	keyCount = 15
	keysPerBucket = 3
Compute:
	bucketCount = 15 / 3 = 5
Compute keyCount

Given:
	bucketCount = 5
	keysPerBucket = 3
Compute:
	keyCount = 5 * 3 = 15


Example (Given Initial Capacity And Max Load Ratio)


Given:

initCapacity = 15
maxLoadRatio = 3

Assumptions:


Therefore:

keyCount = initCapacity = 15
keysPerBucket = maxLoadRatio = 3

Compute bucketCount
See Equations above.

keyCount = 15
keysPerBucket = 3
bucketCount = 15 / 3 = 5

In other words, initially five buckets






























Data Structures And Algorithms (DSA) (Chapter 601 - Hash Table Concepts)










Chapter 601 - Hash Table Concepts Load Ratio (Keys Per Bucket)

Chapter Top Search Site Contents