查找
静态查找表
顺序查找
线性表查询，查找效率（n+1)/2
折半查找
二分查找，仅适用于有序的线性表。
折半查找比较次数最多为 [log2n]+1 次。n=2^x，比如8个元素最多需要3次，对应 8=2^3。
所以时间复杂度为 O(log2n) 。
分块查找
特点是块内无序，但是块间有序。
- 先在索引表确定目标所在块。
- 在块内顺序查找。
比如索引表或者索引文件。
哈希表
按照哈希存储元素到哈希表里。
哈希冲突解决方式
按照值的哈希值存储会出现哈希冲突的问题，可以通过以下方法解决：
链地址法
hashmap采用该方法。
开放地址法
按顺序往后存储元素。
重复哈希
重复进行哈希，直到能存成功。
建立一个公共溢出区。
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。