DS05_Ch07a幻灯片.pptVIP

* CHAPTER 7 HASHING What is hashing for? For searching But we already have binary search in O( ln n ) time after sorting. And we already have algorithms for sorting in optimal time O( n ln n )... Wait a minute — who said that O( n ln n ) is the optimal time? 已有定理表明： “任何仅通过比较操作排序的算法 最坏情况的计算时间必定是 ?( n log2 n ).” 那么我们需要在比较之外做工作. 插值搜索 : 寻找 key ：从排序 list f [ l ].key, f [ l+1 ].key, ... , f [ u ].key. f[l].key f[u].key l u key i ? n elements If ( f [ i ].key key ) l = i ; Else u = i ; 通过公式搜索 1/8 §1 基本思想 符号表 ( == Dictionary) ::= { name, attribute } 〖例〗 在牛津英文词典中 name = since attribute = a list of meanings M[0] = after a date, event, etc. M[1] = seeing that (expressing reason) …… …… This is the worst disaster in California since I was elected. California Governor Pat Brown, discussing a local flood 〖例〗 编译器的符号表 name = identifier (e.g. int) attribute = a list of lines that use the identifier, and some other fields 2/8 对象: 名字-属性构成的对(paires)组成的集合, 其中名字是唯一的 操作: ? SymTab Create(TableSize) ? Boolean IsIn(symtab, name) ? Attribute Find(symtab, name) ? SymTab Insert(symtab, name, attr) ? SymTab Delete(symtab, name) ? 符号表 ADT: §1 基本思想 3/8 Hash 表 [0] [1] … … [s?1] … … ht [ 0 ] … … ht [ 1 ] … … ht [b?1] … … … … b 存储桶 s 存储槽 对每个标识符 x, 定义 hash 函数 f ( x ) = x 在 ht[ ]中的位置(i.e. 包含 x的存储桶的索引 ) ? T ::= x的可能值 ? n ::= ht[ ]中标识符的总数 ? 表示符密度 ::= n / T ? 负载密度 ? ::= n / (s b) §1 General Idea 4/8 ? 碰撞： 当两个不同的标识符散列到相同的存储桶中, i.e. f ( i1 ) = f ( i2 ) when i1 ? i2 . ? 溢出： 当标识符散列到已满的存储桶中. 如果 s = 1，那么碰撞和溢出同时发生 〖例〗 映射 n = 10 C 库函数 到 一个散列表 ht[ ] ，其中 b = 26 且 s = 2. Slot 1 Slot 0 0 1 2 3 4 5 6 …… 25 负载密度 ? = ? 10 / 52 = 0.19 为了映射字母 a ~ z to 0 ~ 25, 我们如何定义 f ( x ) = ? x [ 0 ] ? ‘a’ acos acos define define float float exp exp char char atan atan ceil ceil floor floor clock ctime 没有溢出时, Tsearch = Tinsert = Tdelete = O( 1 ) §1 General Id