当前课程知识点:Data Structures and Algorithm Design Part II > 09.Dictionary > C.Hashing.Hash-Function > 09C-1
返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part II》慕课在线视频列表
好 接下来的这一节我们就来介绍散列策略中的第一项
也是最重要的技术 散列函数的设计与定制
在上一节我们已经看到
散列策略具有诸多的优势和巨大的潜力
然而尽管如此 冲突却是这一策略的致命缺陷
然而更糟糕的是 从理论上讲 这一缺陷是无法根本消除的
依然回到我们电话键盘的实例
借助字符来助记电话号码的策略 尽管十分精巧
但同样不难举出冲突的实例
比如有时你需要找某个人
但对应的号码却有可能属于某个学院
你要找的或许是欧几里得 但这个电话却有可能属于小黄鸭
你可能需要联系太阳鸟 但接听这个电话的却可能是只臭虫
凡此种种 皆是冲突
我们知道散列函数无非是一个映射
其功能无非是将词条空间中的元素映射到散列表地址空间
而在通常的情况下 前者要远远的大于后者
因此绝不可能是一个单射
当然面对这种现实 我们并非无可作为
这方面的一条好消息是 在一般的实际应用中
我们还是可以在一定的程度上得到一个近似的单射
比如黑白打印机经常要做的一件事就是
将原本是彩色的图像 转换为黑白灰度
从映射的角度来看 这样一种转换也是散列
对于这个散列而言
数据项的取值范围应该是图像中各像素可能取的颜色种类数
也就是2的24次方
而散列表的长度呢 也就是灰度的级别 2的8次方
二者之间的差异 已高达10的4至5次方
然而尽管经过了如此之大幅度的压缩
对我们辨识灰度图像中的物体 并没有多大的影响
当然这主要得益于图像中各像素在空间上是有一个分布的
然而即便离开这个条件 一般意义上的散列
也是有可能做得足够实用的
为此我们需要做两件事 这也是实现散列的两项基本任务
首先我们需要精心的设计散列表及其对应的散列函数
消除掉一些能够导致冲突的先天性因素
从而尽可能的压低日后发生冲突的概率
这也是本节讨论的主题
当然既然无论如何都不可能从根本上消除冲突
所以我们也应该在事先准备好充分的预案
日后一旦发生冲突 我们就可照此预案及时予以排解
关于冲突的排解技巧 我们将留到下一节
-A.introduction
--07A-1
--07A-2
--07A-3
--07A-4
--07A-5
-A.introduction--Homework
-B1.BST : search
--07B1-1
-B1.BST : search--Homework
-B2.BST : insertion
--07B2-1
--07B2-2
-B2.BST : insertion--Homework
-B3.BST : removal
--07B3-1
--07B3-2
--07B3-3
--07B3-4
-B3.BST : reomval--Homework
-C.balance+equivalence
--07C-1
--07C-2
--07C-3
--07C-4
--07C-5
-C.balance+equivalence--Homework
-D1.AVL : rebalance
--07D1-1
--07D1-2
--07D1-3
--07D1-4
--07D1-5
-D1.AVL : rebalance--Homework
-D2.AVL : insertion
--07D2-1
--07D2-2
--07D2-3
-D2.AVL : insertion--Homework
-D3.AVL : removal
--07D3-1
-D3.AVL : removal--Homework
-D4.AVL : (3+4)-construction
--07D4-1
--07D4-2
--07D4-3
--07D4-4
-D4.AVL : (3+4)-construction--Homework
-Homework
--Homework
-A1.Splay_Tree.splay1
--08A1-1
--08A1-2
--08A1-3
--08A1-4
--08A1-5
--08A1-6
--08A1-7
--Homework
-A2.Splay_Tree.splay2
--08A2-1
--08A2-2
--08A2-3
--08A2-4
--08A2-5
--08A2-6
--08A2-7
--Homework
-A3.Splay_Tree.implementation
--08A3-1
--08A3-2
--08A3-3
--08A3-4
--08A3-5
--08A3-6
--08A3-7
--Homework
-B1.B-Tree.motivation
--08B1-1
--08B1-2
--08B1-3
--08B1-4
--08B1-5
--08B1-6
--Homework
-B2.B-Tree.structure
--08B2-1
--08B2-2
--08B2-3
--08B2-4
--08B2-5
--08b2-6
--08B2-7
--08B2-8
--Homework
-B3.B-Tree.search
--08B3-1
--08B3-2
--08B3-3
--08B3-4
--08B3-5
--08B3-6
--Homework
-B4.B-Tree.insertion
--08B4-1
--08B4-2
--08B4-3
--08B4-4
--08B4-5
--Homework
-B5.B-Tree.removal
--08B5-1
--08B5-2
--08B5-3
--08B5-4
--08B5-5
--Homework
-XA1.Red-Black.motivation
--08XA1-1
--08XA1-2
--08XA1-3
--08XA1-4
--Homework
-XA2.Red-Black.structure
--08XA2-1
--08XA2-2
--08XA2-3
--08XA2-4
--08XA2-5
--08XA2-6
--08XA2-7
--Homework
-XA3.Red-Black.insertion
--08XA3-1
--08XA3-2
--08XA3-3
--08XA3-4
--08XA3-5
--08XA3-6
--Homework
-XA4.Red-Black.removal
--08XA4-1
--08XA4-2
--08XA4-3
--08XA4-4
--08XA4-5
--08XA4-6
--08XA4-7
--08XA4-8
--08XA4-9
-Homework
--Homework
-B.hashing.principle
--09B-1
--09B-2
--09B-3
--09B-4
--09B-5
--09B-6
--Homework
-C.Hashing.Hash-Function
--09C-1
--09C-2
--09C-3
--09C-4
--09C-5
--09C-6
--09C-7
--09C-8
--09C-9
--09C-A
--09C-B
--Homework
-D1.Hashing.Solving-Collision-1
--09D1-1
--09D1-2
--09D1-3
--09D1-4
--09D1-5
--Homework
-D2.Hashing.Solving-Collision-2
--09D2-1
--09D2-2
--09D2-3
--09D2-4
--09D2-5
--09D2-6
--09D2-7
--09D2-8
--Homework
-E.Bucketsort
--09E-1
--09E-2
--09E-3
--Homework
-Homework
--Homework
-A1.motivation
--10A1-1
--10A1-2
--10A1-3
--Homework
-A2.Basic_Implementations
--10A2-1
--10A2-2
--10A2-3
--Homework
-B1.Complete_Binary_Heap.structure
--10B1-1
--10B1-2
--10B1-3
--10B1-4
--Homework
-B2.Complete_Binary_Heap.insertion
--10B2-1
--10B2-2
--10B2-3
--10B2-4
--Homework
-B3.Complete_Binary_Heap.removal
--10B3-1
--10B3-2
--10B3-3
--10B3-4
--Homework
-B4.Complete_Binary_Heap.heapification
--10B4-1
--10B4-2
--10B4-3
--10B4-4
--10B4-5
--Homework
-C.Heapsort
--10C-1
--10C-2
--10C-3
--10C-4
--Homework
-XA1.Leftist_Heap.structure
--10XA-1
--10XA1-2
--10XA1-3
--10XA1-4
--10XA1-5
--10XA1-6
--Homework
-XA2.Leftist_Heap.merge
--10XA2-1
--10XA2-2
--10XA2-3
--10XA2-4
--Homework
-XA3.Leftist_Heap.insertion+removal
--10XA3-1
--10XA3-2
-Homework
--Homework
-A.ADT
--11A-1
--11A-2
--11A-3
--Homework
-B1.Pm
--11B1-1
--11B1-2
--Homework
-B2.brute-force
--11B2-1
--11B2-2
--11B2-3
--11B2-4
--Homework
-C1.Kmp.memorization
--11C1-1
--11C1-2
--11C1-3
--11C1-4
--Homework
-C2.Kmp.lookup-table
--11C2-1
--11C2-2
--11C2-3
--Homework
-C3.Kmp.understanding_next[]
--11C3-1
--11C3-2
--11C3-3
--Homework
-C4.Kmp.constructing_next[]
--11C4-1
--11C4-2
--11C4-3
--Homework
-C5.Kmp.amortization
--11C5-1
--11C5-2
--Homework
-C6.Kmp.improvement
--11C6-1
--11C6-2
--11C6-3
--11C6-4
--11C6-5
-D1.BM_BC.begin_with_the_end
--11D1-1
--11D1-2
--11D1-3
--11D1-4
-D2.BM_BC.bad_character
--11D2-1
--11D2-2
-D3.BM_BC.constructing_bc[]
--11D3
-D4.Bm_BC.performance
--11D4-1
--11D4-2
-E1.Bm_GS.good-suffix
--11E1-1
--11E1-2
--11E1-3
-E2.Bm_GS.constructing_gs[]
--11E2
-E3.Bm_GS.performance
--11E3-1
--11E3-2
-F1.KR.fingerprint
--11F1-1
--11F1-2
--11F1-3
-F2.KR.hashing
--11F2-1
--11F2-2
--11F2-3
--11F2-4
-Homework
--Homework
-A1.Quicksort.algorithm
--12A1-1
--12A1-2
--12A1-3
--12A1-4
-- 12A1-5
--Homework
-A2.Quicksort.performance
--12A2-1
--12A2-2
--12A2-3
--Homework
-A4.Quicksort.Variation
--12A4-1
--12A4-2
--12A4-3
--12A4-4
--12A4-5
-B1.Selection.mode
--12B1-1
--12B1-2
--12B1-3
--12B1-4
--12B1-5
-B2.Selection.Median
--12B3-1
--12B3-2
--12B3-3
--12B3-4
--12B3-5
--12B3-6
--Homework
-C1.Shellsort.Shell's sequence
--12C1-1
--12C1-2
--12C1-3
--12C1-4
--12C1-5
--Homework
-C2.Shellsort.Inversion
--12C2-1
--12C2-2
--12C2-3
-Homework
--Homework