The question you need to ask is "How unique has the hash key to be?". If the answer is "Absolutely", then you have a problem, you need to store almost as many bits as there are in the message (compression helps though). Otherwise the number of bits of uniqueness dictates what you can do. A simple CRC type checksum of an appropriate number of bits is likely cheaper to calculate than an MD5.