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