Hash查找因为其O(1)的查找性能而著称被对查找性能要求高的应用所广泛采用。它的基本思想是:
(1) 创建一个定长的线性Hash表一般可以初始化时指定length;
(2) 设计Hash函数,将关键字key散射到Hash表Φ其中hash函数设计是最为关键的,均匀分布、冲突概率小全在它;
(3) 通常采用拉链方法来解决hash冲突问题即散射到同一个hash表项的关键字,以鏈表形式来表示(也称为桶backet);
(4) 给定关键字key就可以在O(1) + O(m)的时间复杂度内定位到目标。其中m为拉链长度,即桶深