Geohashing (Location Encoding)

What is Geohashing?

Geohashing is a geocoding method that converts two-dimensional geographic coordinates (latitude and longitude) into a single alphanumeric string. This encoding enables efficient proximity searches, spatial indexing, and location-based queries in databases.

Think of it as giving a rectangular cell an address. Many coordinates map to the same cell, and nearby points across a boundary may have different prefixes.

The Problem: 2D Proximity Search

Finding nearby locations with raw coordinates is computationally expensive:

-- Slow: Requires scanning entire table with range checks on TWO columns
SELECT * FROM restaurants 
WHERE lat BETWEEN 37.7 AND 37.8 
  AND lon BETWEEN -122.5 AND -122.4;

Challenges:

• Ordinary composite indexes and spatial indexes behave differently; spatial indexes can support two-dimensional filtering.
• Range queries on multiple dimensions are slow
• Difficult to cache or shard by location
• Complex distance calculations (Haversine formula)

The Solution: Reduce Dimensions

Geohashing solves this by converting (lat, lon) into a single string:

San Francisco: (37.7749, -122.4194) → "9q8yy"

A prefix match gives candidate points in a cell; a radius query still needs cell coverage and an exact distance filter:

-- Fast: Single column index, prefix search
SELECT * FROM restaurants 
WHERE geohash LIKE '9q8%';

How Geohashing Works

1. Divide the World into a Grid

The algorithm recursively divides the world into smaller rectangles using binary space partitioning:

2. Interleave Bits (Z-Order Curve)

Alternate between longitude and latitude bits to create a single binary number:

Example: San Francisco (37.7749, -122.4194)

Step 1: Binary search on longitude [-180, 180]
-122.4194 < 0 → bit 0

Step 2: Binary search on latitude [-90, 90]
37.7749 > 0 → bit 1

Step 3: Longitude [-180, 0]
-122.4194 < -90 → bit 0

Step 4: Latitude [0, 90]
37.7749 < 45 → bit 0

...continue for desired precision...

Binary: 01001110110111001110110110111001

3. Base32 Encoding

Convert binary to base32 using this alphabet:

0123456789bcdefghjkmnpqrstuvwxyz
(vowels removed to avoid accidental words)

Result: 9q8yyk8 (7 characters)

Precision Levels

Geohash length determines the bounding box size:

Each character adds five bits, splitting a cell into 32 subcells. Width and height alternate between factors of four and eight; widths in metres also shrink with latitude. Table dimensions are approximate equatorial maxima.

Implementation Examples

Python

def encode_geohash(lat, lon, precision=7):
    """Encode lat/lon to geohash string"""
    import math
    if not (math.isfinite(lat) and math.isfinite(lon) and -90 <= lat <= 90 and -180 <= lon <= 180):
        raise ValueError("Coordinates must be finite and within latitude/longitude bounds")
    if not isinstance(precision, int) or not 1 <= precision <= 12:
        raise ValueError("Precision must be a whole number from 1 to 12")
    base32 = "0123456789bcdefghjkmnpqrstuvwxyz"
    lat_range, lon_range = [-90, 90], [-180, 180]
    geohash = []
    bits = 0
    bit = 0
    even = True  # Start with longitude
    
    while len(geohash) < precision:
        if even:  # Longitude
            mid = (lon_range[0] + lon_range[1]) / 2
            if lon >= mid:
                bit |= (1 << (4 - bits))
                lon_range[0] = mid
            else:
                lon_range[1] = mid
        else:  # Latitude
            mid = (lat_range[0] + lat_range[1]) / 2
            if lat >= mid:
                bit |= (1 << (4 - bits))
                lat_range[0] = mid
            else:
                lat_range[1] = mid
        
        even = not even
        bits += 1
        
        if bits == 5:
            geohash.append(base32[bit])
            bits = 0
            bit = 0
    
    return ''.join(geohash)

# Example usage
print(encode_geohash(37.7749, -122.4194, 7))  # Output: 9q8yyk8

JavaScript (Using Library)

import ngeohash from 'ngeohash';

const location = { lat: 37.7749, lon: -122.4194 };
const hash = ngeohash.encode(location.lat, location.lon, 7);
console.log(hash); // "9q8yyk8"

// Decode back to coordinates
const coords = ngeohash.decode(hash);
console.log(coords); // { latitude: 37.775, longitude: -122.419 }

// Get bounding box
const bbox = ngeohash.decode_bbox(hash);
// [minLat, minLon, maxLat, maxLon]

Proximity Search Patterns

1. Prefix Matching

Find all points within the same geohash cell:

SELECT * FROM places 
WHERE geohash LIKE '9q8yy%'
ORDER BY geohash;

2. Neighbor Search

Geohash cells have 8 neighbors. To search nearby:

choose a precision suited to the requested radius
compute every cell intersecting the query circle (including the centre)
retrieve candidates using bound parameters and indexed cell prefixes
filter candidates using actual geographic distance
sort by distance and apply the requested result limit

A fixed set of eight neighbours is not enough for every radius or latitude. Checking result count before the distance filter can terminate too early. For broader searches, use a tested cell-covering routine or a database's native spatial query.

Edge Cases and Limitations

1. Geohash Boundary Problem

Points at geohash boundaries may be close but have different prefixes:

Two points can lie metres apart on opposite sides of a cell edge.
A query limited to the first point's cell misses the second point.

Solution: Always check neighboring cells for proximity searches.

2. Shape Distortion

Geohash cells are rectangles, not squares. Near poles, cells become very narrow:

• At equator: Cell is roughly square
• At 60° latitude: A cell has roughly half its equatorial physical width; angular dimensions are unchanged
• At poles: Cell is extremely elongated

3. Dateline and Pole Issues

• International Date Line: Longitude wraps from 180° to -180°
• Poles: Longitude becomes meaningless at ±90° latitude

Solution: Use alternative systems (S2 Geometry) for global applications.

Geohashing vs. Alternatives

Real-World Use Cases

Illustrative nearby-driver lookup

// Find drivers near user (37.7749, -122.4194)
const userHash = geohash.encode(37.7749, -122.4194, 6); // "9q8yyk"
const nearby = geohash.neighbors(userHash);

db.drivers.find({ 
  geohash: { $in: [userHash, ...nearby] },
  available: true 
});

MongoDB Geospatial Indexes

// Create geohash index
db.places.createIndex({ geohash: 1 });

// Query uses index efficiently
db.places.find({ geohash: /^9q8yy/ }).explain();

Redis Geo Commands

Redis internally uses geohash for geospatial features:

GEOADD locations -122.4194 37.7749 "San Francisco"
GEOSEARCH locations FROMLONLAT -122.4 37.7 BYRADIUS 10 km WITHDIST

Caching Location Data

# Cache key uses geohash for locality
cache_key = f"restaurants:{geohash[:5]}"
results = cache.get(cache_key)

if not results:
    results = db.query(f"WHERE geohash LIKE '{geohash[:5]}%'")
    cache.set(cache_key, results, ttl=300)

Interview Tips 💡

When discussing geohashing in system design interviews:

1. Explain the problem first: "We need to efficiently find nearby locations, which is hard with 2D coordinates..."
2. Justify geohash choice: "Geohashing converts 2D to 1D, enabling prefix-based searches and single-column indexes..."
3. Mention precision: "We'd use 6-character hashes for city-level searches (~1km cells)..."
4. Address edge cases: "We'd check neighboring cells since points near boundaries might have different hashes..."
5. Discuss alternatives: "For a global app, we might consider S2 Geometry to avoid pole distortion..."
6. Show awareness of libraries: "In production, we'd use proven libraries like ngeohash or Redis GEO commands..."

Related Concepts

• Quadtrees — Alternative hierarchical spatial indexing
• Consistent Hashing — Similar hashing concept for distributed systems
• Database Sharding — Can shard by geohash for geographic data
• Bloom Filters — Another space-efficient probabilistic structure
• Caching — Geohash enables location-based cache keys

Sources and a boundary test

Redis GEOADD specifies longitude before latitude and its supported coordinate bounds; GEOSEARCH supports radius/box searches. Test a point on each side of a cell boundary and the international date line. A fast query with false negatives is not a correct proximity search.