数据结构学习笔记（1）：基本概念 数据结构学习笔记（2）：线性结构 数据结构学习笔记（3-5）：树 数据结构学习笔记（6-8）：图 数据结构学习笔记（9-10）：排序 数据结构学习笔记（11）：散列查找 数据结构学习笔记（12）：综合习题选讲

顺序查找 O ( N ) O(N) O(N)

二分查找（静态查找） O ( 1 o g 2 N ) O(1og_2N) O(1og2​N)

二叉搜索树 O （ h ） O（h） O（h）， h h h为二叉查找树的高度

平衡二叉树 O ( l o g 2 N ) O(log_2N) O(log2​N)

快速搜索到需要的关键词。关键词不方便比较。并且是动态查找的情况居多。

思路一：有序安排对象：全序、半序

思路二：直接“算出”对象位置：散列

计算位置：构造散列函数确定关键词存储位置；

解决冲突：应用某种策略解决多个关键词位置相同的问题时间复杂度几乎是常量： O ( 1 ) O(1) O(1)，即查找时间与问题规模无关！

存放操作：主要注意操作有冲突的时候

查找操作：怎么放进去怎么查找，是一个逆序的过程

装填因子：（Loading Factor）：设散列表空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的装填因子

在没有冲突的情况下，复杂度很小

以关键字key为自变量，通过一个确定的函数 h h h（散列函数），计算出对应的函数值 h ( k e y ) h(key) h(key)，作为数据对象的存储地址。

可能不同的关键字会映射到同一个散列地址上，即 h ( k e y i ) = h ( k e y j ) h(key_i)=h(key_j) h(keyi​)=h(keyj​)（当 k e y i ≠ k e y j key_i \neq key_j keyi​​=keyj​），称为“冲突（Collision）”。 —需要某种冲突解决策略

1.计算简单，以便提高转换速度； 2.关键词对应的地址空间分布均匀，以尽量减少冲突。

取关键词的某个线性函数值为散列地址，即 h ( k e y ) = a ⋅ k e y + b h(key)=a\cdot key+b h(key)=a⋅key+b（ a a a、 b b b为常数）

散列函数为：$h(key)=key \mod \ p $

为了表格均匀一般取素数

一般把 p p p取为表格大小

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

把关键词分割成位数相同的几个部分，然后叠加

换个位置：开放地址法（Open Addressing）

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址

同一位置的冲突对象组织在一起：链地址法

若发生了第 i i i次冲突，试探的下一个地址将增加 d d d，基本公式是： h i ( k e y ) = ( h ( k e y ) + d ) m o d    T a b l e S i z e （ 1 ≤ i < T a b l e S i z e ） h_i(key)=(h(key)+d)\mod TableSize（1\leq i < TableSize） hi​(key)=(h(key)+d)modTableSize（1≤i