Course contentsShow
← Computer Science
Lesson 410 of 2,87210. Hash TablesFree lesson

Hashing Integers

Techniques for hashing integer keys including identity, modulo, and bit manipulation approaches.

Hashing Integers

What You'll Learn

You'll learn practical techniques for converting integer keys into hash table indices, including identity hashing, modulo operations, and bit manipulation.

The Core Idea

When your hash table uses integers as keys (like student IDs, ages, or product codes), you need a strategy to convert those integers into valid array indices. The simplest techniques are:

Identity Hashing

If your integers are already small and densely packed (like 0-99), you can use the integer itself as the index. This is perfect when keys naturally fit your table size.

hash(42) = 42  // Use the key directly

Think of it like apartment numbers 1-100 in a building—each number directly corresponds to a door.

Modulo Method (Division Method)

For larger integers, use modulo to wrap them into your table size:

hash(key) = key % table_size

If your table has 10 slots, hash(12345) = 12345 % 10 = 5. This squeezes any integer into your available range.

Bit Manipulation

For performance, you can use bitwise AND when table size is a power of 2:

hash(key) = key & (table_size - 1)

With a table size of 8 (binary 1000), table_size - 1 = 7 (binary 0111). The AND operation keeps only the last 3 bits, giving values 0-7. This is faster than modulo on many processors.

When to Use Which

  • Identity: Keys are already 0 to N-1
  • Modulo: General-purpose, works with any table size
  • Bit masking: Maximum speed, requires power-of-2 table sizes

Key Takeaway: Integer hashing transforms any integer key into a valid table index using identity mapping, modulo arithmetic, or bit manipulation—choose based on your key distribution and performance needs.