Start here: the problem it solves#
TL;DRthe 30-second version
- A geohash turns a (latitude, longitude) point into a short base32 string, so that nearby points share a long leading prefix.
- You build it by interleaving the two coordinates' bits — one longitude bit, then one latitude bit, alternating — and reading every five bits as one base32 character.
- Each bit answers one yes/no question: is the point in the upper or lower half of the current range? A 1 keeps the upper half, a 0 the lower, and the cell shrinks to that half.
- Each base32 character is five bits, so each character shrinks the cell by about 32 times: 5 characters ≈ 4.9 km, 6 ≈ 1.2 km, 7 ≈ 150 m, 8 ≈ 38 m.
- The catch: two points close together but on opposite sides of a cell edge share almost no prefix. So a real proximity query checks the cell plus its 8 neighbours.
- Real systems: Redis GEO (a 52-bit interleaved integer), Elasticsearch's geohash_grid, and the original geohash.org short links.
You are building the back end for a maps app. A user is standing somewhere, and you want to answer one question fast: which of the million restaurants in your database are within two kilometres of them? Every restaurant has a latitude and a longitude, and so does the user.
The obvious approach is to scan the table. For each restaurant, compute the distance to the user, and keep the ones under two kilometres. That is a million distance calculations for a single query, and it repeats for every user on every map pan. At any real traffic it falls over.
The usual database fix is an index, but the standard index does not help here. A B-tree can find every restaurant with latitude between two values quickly, and separately every one with longitude between two values. It cannot find the ones that satisfy both at once without pulling a long strip of the map and filtering it. Two separate one-dimensional indexes do not make a two-dimensional one.
The idea that almost works: cut the map in half#
Start with the simplest way to describe roughly where a point is. Take the whole range of longitude, from -180 to 180 degrees, and ask one question: is the point in the eastern half or the western half? Write down a 1 for east and a 0 for west. You have just narrowed the point to one half of the globe with a single bit.
Now do the same again inside the half you kept. If the point was in the eastern half, split that half at its own midpoint and ask again: east or west of there? Each question is one bit, and each bit halves the range that is left. After ten longitude questions the range is 360 degrees divided by 2 to the tenth, about a third of a degree — a few dozen kilometres wide.
This is just binary search on the coordinate. The sequence of bits is the path of yes/no turns that walks you down to the point. And here is the property we were after: two points that are near each other in longitude take the same turns for a long time before they part, so their bit sequences share a long prefix.
The mechanism: interleave the bits, then base32#
Run the halving on both coordinates at once and take turns between them. The first bit is a longitude question over -180 to 180. The second bit is a latitude question over -90 to 90. The third is longitude again, inside the half the first bit kept, and so on, alternating longitude and latitude the whole way down. Longitude goes first, by convention.
- Hold a rectangle of the globe, starting with the whole world: latitude -90 to 90, longitude -180 to 180.
- For a longitude bit, split the rectangle down the middle left-to-right. If the point is in the eastern half, write 1 and keep that half; otherwise write 0 and keep the western half.
- For a latitude bit, split the rectangle top-to-bottom. If the point is in the northern half, write 1 and keep it; otherwise write 0 and keep the southern half.
- Alternate longitude, latitude, longitude, latitude. Every five bits, read them as a number from 0 to 31 and map it to a base32 character.
The alphabet is a specific base32: the digits 0 through 9 and the letters b through z, but with a, i, l and o left out so no two characters are easy to confuse. Five bits make a number from 0 to 31, and that number indexes into the 32-character alphabet. So each character you add is five more bits — five more halvings, split between the two coordinates.
This is the whole encoding. You have derived the geohash: interleave the latitude and longitude bits, longitude first, and group them five at a time into base32. The name comes from Gustavo Niemeyer, who built it in 2008 for the geohash.org URL shortener so a place could be shared as a short link.
The first ten bits of a point in San Francisco (37.77, -122.42), longitude in the top row, latitude in the bottom
Because the bits alternate, the two coordinates get almost the same number of bits. In a six-character geohash there are 30 bits: 15 for longitude and 15 for latitude. That splits the world into a grid of cells about 1.2 km wide and 0.6 km tall at the equator, and the geohash string is the address of the cell your point falls in.
Go deeperHow fast the cell shrinks, exactly
Each character is five bits. Two or three of those bits go to longitude and the rest to latitude, so both coordinate ranges get divided by roughly 2 to the 2.5, which is about 5.7, per character. The area is width times height, so it shrinks by about 5.7 times 5.7, which is roughly 32 — exactly one base32 character's worth of information. That is the rule of thumb: one more character, about 32 times smaller.
So the precision climbs fast. A 1-character geohash is a cell about 5,000 km across. Five characters gets you to about 4.9 km, six to 1.2 by 0.6 km, seven to about 150 m, eight to 38 by 19 m, and nine to under 5 m. Redis carries the equivalent of 52 bits, 26 per coordinate, which pins a point to roughly 0.6 m at the equator.
One wrinkle: the cells are rectangles in latitude and longitude, not squares on the ground. A degree of longitude is about 111 km at the equator but shrinks toward the poles as the meridians converge, so a geohash cell is physically narrower the farther north or south you go. The string length fixes the number of bits, not the metres.
A worked example, and why nearby means shared prefix#
Take a point in San Francisco at latitude 37.7749 and longitude -122.4194, and encode it to six characters. The first bit asks whether -122.4194 is in the eastern or western half of -180 to 180. The midpoint is 0, and -122 is well to the west, so the bit is 0 and we keep the western half, -180 to 0. The next bit does the same for latitude: 37.77 is north of the equator, so the bit is 1 and we keep 0 to 90. Keep alternating for 30 bits and the string comes out as "9q8yyk".
Now take a second point about a kilometre away, still in the same part of the city. For the first many bits it takes exactly the same turns, because it is in the same halves of the map — same western half, same northern half, same and same. Its geohash comes out as "9q8yym": the two points agree on the first five characters and only differ in the last. The shared prefix "9q8yy" is not a coincidence. It is the run of turns the two points took together before the map got fine enough to tell them apart.
Compare that to a point in New York, at 40.71, -74.01. It is in the same northern half but the opposite side of the country in longitude, so it diverges on an early bit and its geohash is "dr5reg". It shares nothing with San Francisco — not even the first character. Shared prefix length tracks distance: the closer two points are, the more leading characters they share.
PredictYou shorten every stored geohash from 6 characters to 5 before indexing. What happens to a "near me" prefix search?
Hint: Fewer characters means a larger cell. Think about how many points now share each prefix.
A 5-character prefix is a cell about 4.9 km across instead of 1.2 km, so many more points share each prefix. Your prefix search now returns a wider net: more candidates, including some farther away than you wanted, which you then filter by true distance. Shorten too far and you are back to scanning large regions; keep it too long and a single cell is smaller than your search radius, so you miss neighbours in adjacent cells. The precision you index at has to match the radius you query — which is exactly why real queries pick a cell size near the search radius and then also check the neighbour cells.
The sharp edge: neighbours across a cell boundary
Shared prefix tracks distance, but not perfectly, and the gap matters. Two points can be a stone's throw apart on the ground and still share almost no prefix, if a cell boundary happens to run between them. This is the one thing you have to design around.
Picture two points 60 metres apart, but with a cell edge between them. One sits at the top of its cell; the other is just over the line, at the bottom of the cell above. On the map they are neighbours. In geohash terms they took different turns at the bit where that boundary was decided, so from that bit on their strings diverge. Two points 60 metres apart can share only three characters, while two points a kilometre apart in the middle of a cell share five. Nearness on the ground does not guarantee a shared prefix.
This comes from how the interleaving walks the map. Threading the bits together traces a path called a Z-order, or Morton, curve — a line that visits every cell in a zig-zag. Most of the time the curve keeps neighbours together, but at the edges of the big zig-zags it jumps across the map, and two cells that are neighbours on the ground can sit far apart along the curve. Those jumps are the boundaries where close points get different prefixes.
Cost and precision#
Encoding is cheap and fixed. To produce an n-character geohash you do 5n halvings, each a comparison and an assignment, so encoding is O(n) with a tiny constant — a handful of operations for a typical seven- or eight-character hash. There is no tree to walk and no structure to keep in memory; the string is computed straight from the coordinates.
- A geohash is a short string, usually 5 to 12 characters. It is its own index key: you store it in whatever sorted index you already have, so there is no separate spatial data structure to build or balance.
- Precision is set by length. Each character is 5 bits and shrinks the cell about 32 times: 5 chars ≈ 4.9 km, 6 ≈ 1.2 by 0.6 km, 7 ≈ 150 m, 8 ≈ 38 by 19 m, 9 ≈ 5 m. You pick the length to match the radius you search at.
- A near-me query is a prefix scan for the point's cell plus its 8 neighbour cells, then a true-distance filter on the candidates. That is 9 cheap range scans and a small amount of arithmetic, instead of a full-table distance scan.
- Cells are rectangles in latitude and longitude, so their ground size shrinks toward the poles and is never exactly square. The string length controls the bit count, not the metres, so physical precision varies a little with where you are on Earth.
Geohash, quadtree, S2, and H3
Geohash is one of several ways to give a point a sortable spatial key, and the others fix specific weaknesses of it. They are worth knowing because production systems pick between them deliberately.
- Quadtree — a tree that splits a square into four quadrants only where points are dense, so crowded areas get finer cells and empty areas stay coarse. It adapts to the data, but it is a structure you build and hold in memory, and there is no simple string whose prefix means proximity. Geohash is the flat, stateless cousin: a fixed grid and a string you can index anywhere.
- S2 (Google) — projects the Earth onto the six faces of a cube and numbers cells along a Hilbert curve instead of a Z-order curve. The Hilbert curve has no long jumps, so neighbours stay close in the key far more often, and cells are closer to equal-area across the globe. The trade is more complex math and 64-bit cell ids rather than a readable string.
- H3 (Uber) — tiles the world with hexagons instead of rectangles. Every hexagon has six neighbours all at the same distance, which makes movement and radius queries more uniform than a grid of rectangles with eight unequal neighbours. It is the choice when even neighbour spacing matters, at the cost of hexagons not nesting perfectly across zoom levels.
Strengths, limits, and when to reach for it
Geohash makes one clean bargain: it flattens a two-dimensional location into a one-dimensional, human-readable, indexable key. Whether that is the right bargain depends on what you need from the key.
- It is simple and portable. The key is a short string that indexes in any ordinary database, shares in a URL, and needs no special spatial structure. This is the whole reason to use it.
- Prefix means proximity, mostly. A shared prefix is a strong hint that two points are close, which turns near-me into a prefix scan. But it is one-way: close points usually share a prefix, yet points across a boundary may not, so you must query the 8 neighbours.
- Precision is quantised to characters. You get 4.9 km, then 1.2 km, then 150 m — not a smooth dial. If your radius sits between two levels you either over-fetch at the coarser level or stitch neighbours at the finer one.
- Cells are not equal-area and not square. Ground size varies with latitude, so a fixed length means different physical precision in different places. For equal-area work, S2 or H3 fit better.
- The limits — reach for a quadtree when point density varies wildly and you want the index to adapt, for S2 when you need smooth neighbours and near-equal-area cells at global scale, and for H3 when uniform neighbour distance drives your algorithm.
Geohash vs the neighbours, at a glance
| Geohash | Quadtree | S2 | H3 | |
|---|---|---|---|---|
| Key | base32 string | tree path | 64-bit id (Hilbert) | 64-bit id (hex) |
| Cell shape | lat/lng rectangle | square | near-equal-area quad | hexagon |
| Adapts to density? | no, fixed grid | yes | no | no |
| Prefix = proximity? | yes, with edge gaps | path prefix, edge gaps | smoother (Hilbert) | by resolution |
| Neighbours | 8, unequal | 8, unequal | 8, unequal | 6, equal |
| Best when | simple, portable keys | clustered data | global, equal-area | uniform movement |
The four tools all answer the same question — give a point a sortable key that keeps nearness — and differ in what they optimise. Geohash optimises for simplicity and portability. Quadtree optimises for uneven data. S2 optimises for smooth, equal-area cells at planet scale. H3 optimises for even neighbour spacing. A lot of systems use more than one: a geohash for the human-facing short link, and S2 or H3 underneath for the heavy indexing.
Where geohash runs in the wild
- geohash.org — the original use, by Gustavo Niemeyer in 2008: a service that turns a place into a short URL like geohash.org/9q8yyk, so a location can be shared as a link. This is where the encoding and its base32 alphabet were defined.
- Redis GEO — GEOADD stores each member's position as a 52-bit interleaved geohash integer used as the score in a sorted set, and GEOSEARCH answers radius queries by scanning the score ranges of the target cell and its 8 neighbours. GEOHASH returns the familiar 11-character string.
- Elasticsearch — the geohash_grid aggregation buckets documents by geohash prefix at a chosen precision, which is how map tools draw heat maps and clustered pins: each bucket is one cell, and zooming just lengthens the prefix.
- Data pipelines and sharding — geohash prefixes are a common way to shard or partition spatial data so that nearby points land on the same node, and to join or bucket location data in analytics without a full spatial index.
Common misconceptions & gotchas
Does a shared prefix guarantee two points are close?
A shared prefix means they fall in the same cell at that precision, so yes, a long shared prefix means they are close. The reverse is not guaranteed: two close points on opposite sides of a cell edge can share almost no prefix. That is why a proximity search checks the cell plus its 8 neighbours rather than trusting a single prefix.
Why longitude first, and does it matter?
It is a convention fixed by the original geohash.org definition: bit 1 is longitude, bit 2 is latitude, alternating. It matters only in that everyone must agree, so encoders and decoders interoperate. One consequence: longitude spans 360° but latitude only 180°, so at even character lengths — where the two get equal bit counts — cells come out about twice as wide as they are tall; at odd lengths, longitude's one extra bit roughly squares them up.
Are geohash cells squares?
No. They are rectangles in latitude and longitude, and because a degree of longitude shrinks toward the poles, the same-length geohash covers less ground the farther you are from the equator. If you need equal-area cells, use S2; if you need equal neighbour spacing, use H3.
How do I pick the precision?
Match the cell size to your search radius. If you look for things within a kilometre, index at 6 characters (about 1.2 km) so a cell is close to the radius, then query that cell and its 8 neighbours. Too short a prefix returns too many candidates; too long a prefix makes a cell smaller than your radius, so you would have to stitch together many neighbour cells to cover it.
QuizA driver-tracking service stores each driver's 7-character geohash and finds nearby drivers with a single prefix match on the rider's 7-character geohash. Riders complain that drivers one block away sometimes don't appear. What is the bug?
- It only searches the rider's own cell, so a driver just across a cell boundary — a block away — is in a different cell and is missed. It must also search the 8 neighbour cells.
- 7 characters is too coarse, so distant drivers are wrongly included
- Geohash prefixes are random, so a prefix match cannot find nearby points at all
- The drivers' geohashes are stale and need re-encoding on every query
Show answer
It only searches the rider's own cell, so a driver just across a cell boundary — a block away — is in a different cell and is missed. It must also search the 8 neighbour cells. — A 7-character cell is about 150 m across. A driver a block away can easily sit in the neighbouring cell, sharing only 6 characters, so a single-prefix search for the rider's exact cell misses them. The fix is the standard one: compute the rider's cell and its 8 neighbours and prefix-scan all nine, then filter by true distance. Forgetting the neighbour ring is the most common geohash bug.
In an interview
Lead with the problem and the shape of the answer. Finding points near a location by scanning and computing distances is O(n) per query and does not scale, and two one-dimensional indexes cannot answer a two-dimensional range. A geohash gives each point a short string such that nearby points share a prefix, so near-me becomes a prefix scan on an ordinary sorted index. Name where it runs: Redis GEO, Elasticsearch's geohash_grid, and the original geohash.org links.
Then explain the mechanism in two moves. First, binary-search each coordinate — one bit per halving — and interleave the two bit streams, longitude first. Second, group the bits five at a time into base32. Be ready to say why the prefix works: a shared prefix is a shared run of halvings, which is a shared region of the map. Mention that each character shrinks the cell about 32 times, so you pick the length to match your search radius.
The senior signal is naming the boundary problem before you are asked. Say plainly that a shared prefix means close but close does not guarantee a shared prefix, so a real query searches the cell and its 8 neighbours. If pushed on alternatives, contrast a quadtree (adapts to density), S2 (Hilbert curve, smoother neighbours, near-equal-area), and H3 (hexagons, equal neighbour spacing). Then open the simulator: encode a point bit by bit and watch the cell shrink, then encode a near point and a far one and watch the prefixes agree or diverge.
References & further reading
- Geohash — Wikipedia — the algorithm, the base32 alphabet, the precision table, and the worked example
- geohash.org — the original service (Gustavo Niemeyer, 2008) — where the encoding was defined; turns a place into a short URL
- Redis — GEOADD / GEOSEARCH and the geospatial index — stores a 52-bit interleaved geohash as a sorted-set score; radius search scans a cell and its neighbours
- Elasticsearch — Geohash grid aggregation — buckets documents by geohash prefix at a chosen precision, for map heat maps and clustering
- Google S2 — S2 Geometry library — the Hilbert-curve, near-equal-area alternative; useful contrast to geohash's Z-order grid
- Uber H3 — hexagonal hierarchical spatial index — the hexagon alternative with uniform neighbour distance
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.