Bidirectional Look Up
Hi,
I have a mapping of zip codes and cities that are used by my application. Note a city can have many zip codes and a zip code can be in more than one city. Also in my application we maintain a preference of use of a zip code within a city and the city within the zip code. This information is in the database and right now I make a database call everytime I need this information.
I need to provide a way to quickly return a city given the zip code or the zip code given the city so I want to cache this information in memory.
Once loaded this object structure will not change and will be only used for lookups. (I need a fast lookup).
One solution would be to have two HashMaps. One with the zip code as the key and a List of Cities as the value. The cities would be ordered in the list according to the preferencedefined by the application. Similarly the second one would have the City as the key and a List of zip codes as the values.
But this would take up lot of memory. It has been estimated the size of one such map would be 1MB.
Is there a way to have a single object that could store this information and provide a quick lookup?
Thanks,
Ab.
[1214 byte] By [
abhi73a] at [2007-10-2 17:04:09]
I agree with previous post. Two different types of access pretty much requires two different structures. Also, 1M is not so much space these days.
But if size is really your concern you can reduce the size requirements by doing some more work than just using off the shelf components like a hash map.
For example, zip codes are essentially a continuous range 00000-99999. Not all are legal, but ignoring that, an array would encode the zip to city structure better than a hash map (hash structures must have holes in them to remain efficient - i.e. empty nodes, which still take up space).
The illegal zip code values put holes in an array structure as well, but if memory serves me correctly, the illegal zip codes also come in contiguous batches so that a little code could eliminate the wastage in the array.
Secondly, Strings waste space by keeping the data values as some form of unicode or even ascii. Huffman encoding of all the city names reduces their size by a factor of about 10 (26 chars insetad of 256 ascii valuse)
The Huffman encoding on the city names not only compresses the names, but acts as a hash code. So if you are looking for Fooville, you huffman encode Fooville, you strip off the first portion (number of bits to be determined by experience with your data) to use as an index to a bucket which has the remaining bits and the associated zipcode.
You may either binary search or brute search the bucket.
I don't in general recommend doing all this work. The reason we make machines bigger and faster is so that we don't have to work so hard making software small and efficient, but if you MUST reduce the size there are almost always ways to do that with a lot of extra work.
> I think below code maybe have some help for you
> http://www.javaresources.biz/content.jsp?id=bf77df720b
> 16f930010b1c7038ab0003&item=Basic
Actually, that code has nothing to do with the OP's problem. Realizing that not everyone on this forum is American, I will provide this link:
http://en.wikipedia.org/wiki/Zip_code
