Optimize search by hash in MySQL

Optimize search by hash in MySQL

I have an InnoDB table with a lot of fields, one of them is a unique hash
of 32 bytes (typical md5 result).
I have to do a lot of queries searching by that hash, but my table starts
to be big (500.000 records), and this search takes a lot of time:
SELECT id FROM table WHERE key='Bj8DzS7RmCG41nLdgOp0kEhNtrfPo3KF' This
took about 0.7s
I could create an index of this "hash" 32-bytes varchar column, but this
table grows a lot and if I have to optimize table (to re-index), it takes
a lot of time to do it (about 10 minutes in my case), locking all the
other live queries.
So, what is the best way to optimize a query where you have to search by a
32-bytes varchar field ?