当前课程知识点:Data Structures and Algorithm Design Part II > 09.Dictionary > B.hashing.principle > 09B-4
返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part II》慕课在线视频列表
实际上 我们刚才介绍的数组方法并非一无是处
就原理而言 只需再向前略作改进 也就成为了散列
为此需要首先统一一些名词
比如在这里数组中的每一个单元将被称作为桶bucket
其中可能直接存放某一个词条
也可能存放的是一个词条的间接引用
而以上所说的数组 在这里将被称为是桶数组
bucket array
或者直接的称之为散列表 hash table
我们也统一的将散列表的长度记作M
而这里的核心技巧恰恰就在于散列表长度的选取
首先散列表至少应该能够足以容纳所有的待存放元素
因此这个不等号也就必须满足
其次正如我们已经看到的 直接应用数组的方法
它的致命缺点在于 所使用的空间远远过大
因此所谓的散列表
也可以认为是对这个空间做了一个适当的压缩
既然散列表的长度关乎我们的空间效率
所以这种压缩 必须是实质性的
也就是说 在数量级上M要实质的远远小于R
尽管M必须大于N
但是为了实现尽可能高的效率
M还是应该与N尽可能的同阶
这样我们实际所花费的空间量
就能够控制在线性的范围以内
那么这种思路如何兑现呢
你应该记得 在此前那种朴素的数组方法中
对于任何一个关键码 我们都可以在O(1)的时间内
直接得到对应的记录 或者它的间接引用
而在做过空间压缩的现在 这个功能又当如何实现呢
如果将这种确定目标词条位置的功能 称作为定址
那么具体的定址方法也就是我们所说的散列hashing
为了完成散列定制 我们需要在事先确定一个散列函数
借助这个函数
可以将任意关键码转换为对应的词条或它的入口
在这个原理图中
原先一蹴而就的过程 被分解为了两步
也就是将任意给定的关键码
通过hash function转换为散列表中的某一个桶单元
并且进而通过这个桶单元 找到目标词条
尽管整个过程多了一些曲折
但是正如我们最终将要看到的
只要散列函数设计与实现得当
我们就可以将整个过程所需要的时间控制在期望的常数范围以内
那么这里的散列表应当如何压缩并得到呢
相应的散列函数 又当如何设计呢
-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