请问搜索指纹速度有关问题

请教搜索指纹速度问题？
小弟在做一个指纹识别的项目。已经将采集到的指纹存储到了数据库。
现采集了1000个人的指纹信息，编号是1-1000。编号-人员姓名-指纹特征。
在识别中，我用for循环进行搜索。
比如张三按下指纹，要for 1 to 1000将其指纹信息与数据库中的指纹信息进行对比。如果有配对的，则显示张三的名字；如果没有，则提示无此人信息。

功能已经实现。但现在的问题是速度问题。
假设张三的指纹信息在数据库中排在比较靠前的位置，很快搜到。但如果他的指纹信息处于非常靠后(比如999)或者数据库中根本没有他的指纹信息(要通过全部搜索完数据库才能确定这一点)，那速度就比较慢了！

现在1000个人还行，6秒左右。但如果是5000人呢，那速度就太慢了！

请教有什么办法解决这个指纹搜索的速度问题吗？
------解决思路----------------------
按指纹特征排序，二分查找。
------解决思路----------------------
指纹特征算出一个哈希值，不就可以排序、查找了，这比直接比较指纹特征要快多了。
就算考虑哈希值可能有重复，二分查找到一个匹配的哈希值后，前后相同的哈希值也只有极少几个，只有在这几个人中比较指纹特征就能最终确定了。
这是非常基本的搜索算法啊！