数据结构-查找（B树、散列表）

查找表

查找表是由同一类型的数据元素（或记录）构成的集合。

根据操作可分为

静态查找表：只做查找操作的查找表动态查找表：查找时插入或删除数据的查找表

常见查找方式：

顺序表查找

**方法：**线性表+顺序遍历+等值比较

有序表查找

方法： 线性表+排序+折半查找/插值查找/斐波那契搜索等

插值查找：基于二分查找，将查找点的选择改进为自适应选择，提高查找效率 斐波那契搜索：就是在二分查找的基础上根据斐波那契数列进行分割的

线性索引查找

方法： 创建索引

稠密索引： 每个记录各对应一个索引项分块索引： 特点：块间有序，块内无序 索引结构：最大关键码+块内个数+首元素指针倒排索引： 索引结构：次关键码+记录号

二叉排序树

方法： 建立二叉排序树 特点：左子树小于根节点，右子树大于根节点，并不重复 优点：

查找次数小于树深度插入删除不移动元素，时间性能好 缺点：查找性能取决于树的形状，极端情况下性能会很差。

平衡二叉树（AVL）

方法： 建立二叉平衡树 优化的二叉排序树，左右子树深度相差不能大于一。

多路查找树（B树）

方法： 建立多路查找树 多路查找树：每个节点的孩子数多于两个，每个节点可以存储多个元素。 B树是一种平衡的多路查找树。 2-3树： 2-3-4树： 2-3树、2-3-4树都是特殊的多路查找树

散列表（哈希表）查找

方法： 建立关键字与存储位置之间的对应关系（散列函数）

散列函数的构造方法：

直接定址法数字分析法平方取中法折叠法除留余数法随机数法

哈希冲突：关键字不同的元素被映射到了同一个内存位置

处理散列冲突的方法:

开放定址法： 一旦发生冲突就去找下一个散列地址 1. 线性探测再散列： 顺序寻找 2. 二次探测再散列： 下一个散列地址为1^2 , (-1)^2, 2^2 , (-2)^2 , 3^2 , ( -3)^2…… 3. 伪随机探测再散列： 随机生成下一个散列地址再哈希法： 准备多种散列函数，一旦冲突就换一种散列函数链地址法： 为每个冲突分别建立单链表，一旦冲突则加入对应链表（同义冲突）建立公共溢出区： 建立溢出表（顺序），所有的冲突都加入溢出表（非同义冲突）

散列表的查找性能

无冲突时为O(1)，冲突时取决于

散列表是否均匀处理冲突的方法散列表的填装因子