I thought the problem is that you cannot extract the key from the structure (e.g. to use parallel Index).
Anyway, in that case I think the best you can achieve is to have hashvalue of key and do the testing yourself. I do not see what Index functionality you can use in this case.