View
2
Download
0
Category
Preview:
Citation preview
1
Hashingدرهمسازی
Part-12
Arash Vaezi
2
درروش.است(O(nاز...وعنصریکحذفواضافهعملیاتوجستجوباساختاریکواقعدردرهمسازی
.استnازمستقلاساساهمسازی
همسازدرتابع.میشودانجامکلیدبررویکهاستپردازشیتوسطآدرسبهکلیدتبدیلدرهمسازیازمنظور
(hashing function),برراآنمعادلآدرسودادهانجامرویبرمحاسباتی,گرفتهراکلیدیکهاستتابعی
.میگرداند
مفهوم
:داریمکافیمقداربهحافظهکهکنیمفرضاگر
3
درروش.است(O(nاز...وعنصریکحذفواضافهعملیاتوجستجوباساختاریکواقعدردرهمسازی
.استnازمستقلاساساهمسازی
همسازدرتابع.میشودانجامکلیدبررویکهاستپردازشیتوسطآدرسبهکلیدتبدیلدرهمسازیازمنظور
(hashing function),برراآنمعادلآدرسودادهانجامرویبرمحاسباتی,گرفتهراکلیدیکهاستتابعی
.میگرداند
مفهوم
U(universe of keys)
n
(actual
keys)
k1
k2
k3
k5
k4
k6
k7k8
T[0] T[|U|-1]
i
:داریمکافیمقداربهحافظهکهکنیمفرضاگر
یکآرایهبهاندازهدامنهمیگیریم:آدرسدهیمستقیم
.حافظهخیلیبیشترازتعدادکلیدهاست:مشکل
4
Hash Tables• Notation:• U – Universe of all possible keys.• K – Set of keys actually stored in the dictionary.• |K| = n.
• When U is very large,• Arrays are not practical.• n
Hashing
• Hash function h: Mapping from U to the slots of a hash table T[0..m–1].
h : U {0,1,…, m–1}
• With arrays, key k maps to slot A[k].• With hash tables, key k maps or “hashes” to slot T[h[k]].• h[k] is the hash value of key k.
Hashing0
m–1
h(k1)
h(k4)
h(k2)
h(k3)
U(universe of keys)
(actual
keys)
k1
k2
k3
k4
Hashing0
m–1
h(k1)
h(k4)
h(k2)=h(k5)
h(k3)
U(universe of keys)
K
(actual
keys)
k1
k2
k3
k5
k4
collision
Methods of Resolution• Chaining:• Store all elements that hash to the same slot in a
linked list.
• Store a pointer to the head of the linked list in the hash table slot.
k2
0
m–1
k1 k4
k5 k6
k7 k3
k8
ههایتوزیعکلیدهادرخون,خوبباشدوکلیدهارابهطورمتوازنبیناندیسهایآرایهپخشکندhashاگرتابع
.آرایهیکنواختخواهدبودوعمالبهروشآدرسدهیمستقیمنزدیکمیشود
k2
Collision Resolution by Chaining
0
m–1
U(universe of keys)
(actual
keys)
k1
k2
k3
k5
k4
k6
k7k8
k1 k4
k5 k6
k7 k3
k8
Hashing0
10
ℎ(𝑘) = 𝑘2 𝑚𝑜𝑑 11
11
load factor(میکنیمتعریف(باردهیضریب,بارگیریفاکتور:
𝛼 =𝑛
𝑚
n=وکلیدهاتعدادm=استآرایهاندازه.
𝑂(1بامیشودبرابرمتوسططوربهخونههربرایجستجوهزینه + 𝛼)
هزینهمتوسطیکجستجو
Analysis on Chained-Hash-Search
• Load factor =n/m = average keys per slot.• m – number of slots.• n – number of elements stored in the hash table.
• Worst-case complexity: (n) + time to compute h(k).
• Average depends on how h distributes keys among m slots.• Assume• Simple uniform hashing.• Any key is equally likely to hash into any of the m slots, independent of
where any other key hashes to.
• O(1) time to compute h(k).• Time to search for an element with key k is (|T[h(k)]|).• Expected length of a linked list = load factor = = n/m.
Expected Cost of an Unsuccessful Search
Proof:
• Any key not already in the table is equally likely to hash to any of the mslots.
• To search unsuccessfully for any key k, need to search to the end of the list T[h(k)], whose expected length is α.
• Adding the time to compute the hash function, the total time required is Θ(1+α).
Theorem:
An unsuccessful search takes expected time Θ(1+α).
14
استممکنکامپیوتریبرنامهیکنویسندهمثال.میکندعملمتفاوتدرهمسازتابعدادهبهبستهمواقعبعضی
طوربهدرهمسازتابعاگرحتی.میکنداستفادهخودمتغیرهاینامگذاریبرایخاصیحروفازعادتبرحسب
.باشدنمناسبکامپایلریکازخاصکاربریکاستفادهبرایاستممکن.باشدمتوازنحروفهمهیرویکلی
Universal Hash
𝐻 = {ℎ1, ℎ2, … ℎ𝑙}
استفادهیطوالنمدتبراینباشدنیازسیستمکهاستمفیدزمانیبرایسراسریدرهمسازتابعازاستفاده
سیستمهاییچنیندر.شوندmapاولازوگیرندقراردرهمسازتابعدردوبارهدادههاهمهیبایدوگرنه.شود
.باشدصحیحانتخاببایدابنداهمان
.کامپایلریانرمافزاراستفادهکنندههرباربهصورتتصادفیازیکیازاینتوابعاستفادهمیکند
15
استممکنکامپیوتریبرنامهیکنویسندهمثال.میکندعملمتفاوتدرهمسازتابعدادهبهبستهمواقعبعضی
طوربهدرهمسازتابعاگرحتی.میکنداستفادهخودمتغیرهاینامگذاریبرایخاصیحروفازعادتبرحسب
.باشدنمناسبکامپایلریکازخاصکاربریکاستفادهبرایاستممکن.باشدمتوازنحروفهمهیرویکلی
Universal Hash
𝐻 = {ℎ1, ℎ2, … ℎ𝑙}
عنصرکهدرهمسازیتوابعتعداد:سراسریدرهمسازتابعیکمجموعهدرxوyخانهیکبهراmap
حداکثرباید,میکنند𝐻
𝑚مختلفدرهمسازیتابعهایدرهاyوxیعنی).استآرایهاندازهmکه.باشد
mapمختلفخانههایبهشوند)
.کامپایلریانرمافزاراستفادهکنندههرباربهصورتتصادفیازیکیازاینتوابعاستفادهمیکند
16
Universal Hash
𝐻 = {ℎ1, ℎ2, … ℎ𝑙}
عنصرکهدرهمسازیتوابعتعداد:سراسریدرهمسازتابعیکمجموعهدرxوyخانهیکبهراmap
حداکثرباید,میکنند𝐻
𝑚مختلفدرهمسازیتابعهایدرهاyوxیعنی).استآرایهاندازهmکه.باشد
mapمختلفخانههایبهشوند)
.کامپایلریانرمافزاراستفادهکنندههرباربهصورتتصادفیازیکیازاینتوابعاستفادهمیکند
:برایتابعدرهمسازسراسریکهخصوصیتفوقراداشتهباشدمثال
ℎ𝑎,𝑏 𝑘 = 𝑎𝑘 + 𝑏 𝑚𝑜𝑑 𝑝 𝑚𝑜𝑑 𝑚 𝑝یکعدداولکهازهمهیاعداددامنهبزرگترباشد.
تابعمجموعهیدردرهمسازیتوابعازکدامهرمیخواهیم
pاندازه.برگردانندmاندازهیدرعددی,درهمسازیسراسری
.استبزرگخیلی
𝑎𝜖{1, … , 𝑝 − 1}
𝑏𝜖{0, … , 𝑝 − 1}
(O (𝛼متوسطهزینهجستجو
Division Method
• Map a key k into one of the m slots by taking the remainder of k divided by m. That is,
h(k) = k mod m
• Example: m = 31 and k = 78 h(k) = 16.• Advantage: Fast, since requires just one division
operation.
• Disadvantage: Have to avoid certain values of m.• Don’t pick certain values, such as m=2p• Or hash won’t depend on all bits of k.
• Good choice for m:• Primes, not too close to power of 2 (or 10) are good.
18
Examples
ℎ 𝑘 = 𝑎𝑘 + 𝑏 𝑚𝑜𝑑 𝑚 (𝑚 ≠ 2𝑖)
ℎ 𝑘 = ⌊𝑚(𝐴𝑘 𝑚𝑜𝑑 1)⌋ (𝑚 = 2𝑖)
𝑎 = 1 , 𝑏 = 0 ⇒ ℎ 𝑘 = 𝑘 𝑚𝑜𝑑 𝑚 𝑚 ≠ 2𝑖
0 < 𝐴 < 1
.راانتخابمیکنندbوaبستهبهمسئله
𝑚 = 2𝑖بگیریمازبیتiبهراستدرنظرگرفتهنمیشوند.
𝐴 =5 − 1
2
Multiplication Method
• If 0 < A < 1, h(k) = m (kA mod 1) = m (kA – kA) where kA mod 1 means the fractional part of kA, i.e., kA – kA.
• Disadvantage: Slower than the division method.• Advantage: Value of m is not critical.• Typically chosen as a power of 2, i.e., m = 2p, which makes implementation
easy.
• Example: m = 1000, k = 123, A 0.6180339887…h(k) = 1000(123 · 0.6180339887 mod 1)
= 1000 · 0.018169... = 18.
Methods of Resolution
• Chaining:• Store all elements that hash to the same slot in a
linked list.
• Store a pointer to the head of the linked list in the hash table slot.
• Open Addressing (open hashing):• All elements stored in hash table itself.• When collisions occur, use a systematic
(consistent) procedure to store elements in free
slots of the table.
k2
0
m–1
k1 k4
k5 k6
k7 k3
k8
Methods of Resolution
• Open Addressing (open hashing):• All elements stored in hash table itself.• When collisions occur, use a systematic
(consistent) procedure to store elements in free
slots of the table.
.کنیمدرجخالیجایاولیندرکنیدفرض
از!کردسرچراآرایهکلدرجهاوحذفازبعدباید
.منکنیسرچراآرایهکلکهمیکنیماستفادهدرهمسازی
Linear Probing
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
12
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
12
14
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
12
14
50
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
12
14
50
.وجودنداردواگرپربودبرمیگردانیم
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
30
12
14
50
بودبهجستجوادامهبدهکهاگرپربودflag=1وجودنداردواگر
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0
ℎ 𝑘, 1
ℎ 𝑘, 2
… .
ℎ 𝑘,𝑚 − 1ℎ 𝑘, 𝑖 = ℎ(𝑘) + 𝑐1𝑖 + 𝑐2𝑖
2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 𝑖 = ℎ1(𝑘) + 𝑖ℎ2(𝑘) 𝑚𝑜𝑑 𝑚تاعددمتفاوتبدهدmباید
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
ℎ 𝑘, 0 = 𝑘 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 1 = 𝑘 + 1 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 2 = 𝑘 + 2 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 3 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
ℎ 𝑘, 4 = 𝑘 + 3 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50}
40
30
12
1450
!اینجا,درروشزنجیرهاییکعددبهلینکلیستاضافهمیشدm:درجعنصراضافهبر
17
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
مثال
{40, 30, 12,14,50}
40
30
12
14
50
جدولاولیهازبینمیرودوهمهیعناصرازاولدرتابعدرهمسازجدیدباطولدوبرابرm:درجعنصراضافهبر
.وهردفعهپرشداینکارتکرارمیشود.درجمیشوند
17
Open Hashing
ℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50, 17}
40
30
12
14
50جدولاولیهازبینمیرودوهمهیعناصرازاولدرتابعدرهمسازجدیدباطولدوبرابرm:درجعنصراضافهبر
(2m)هزینهسرشکناز
Open Hashingℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50, 17}
جدولاولیهازبینمیرودوهمهیعناصرازاولدرتابعدرهمسازجدیدباطولدوبرابرm:درجعنصراضافهبر
(2m)هزینهسرشکناز
Open Hashingℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
{40, 30, 12,14,50, 17}
جدولاولیهازبینمیرودوهمهیعناصرازاولدرتابعدرهمسازجدیدباطولدوبرابرm:درجعنصراضافهبر
(2m)هزینهسرشکناز
Open Hashingℎ 𝑘, 𝑖 = 𝑘 + 𝑖 𝑚𝑜𝑑 𝑚
وحذفچقدراست؟هزینهسرشکنیکدرج:سوال
𝑂 1 ?
Open Hashing
ℎ: 𝑈 ⤫ 0, 1, … ,𝑚 − 1 → {0, 1, … ,𝑚 − 1}
ℎ 𝑘, 0
ℎ 𝑘, 1
ℎ 𝑘, 2
… .
ℎ 𝑘,𝑚 − 1
تاعددمتفاوتبدهدmباید
.تاپخششوندmورویهر
هزینهمتوسطجستجویناموفق؟
دنبالهوارسیبهkبهازاییککلید:فرض
.جایگشتاست!mاحتمالمساوییکیاز
Open Hashing
ℎ 𝑘, 0 ℎ 𝑘, 1 ℎ 𝑘, 2 … .
𝑖 + 1
اولینخانهخالی
.کنیماستفادهمیبرایبدستآوردنمتوسطهزینهجستجوازیکمتغیرتصادفی
X=هزینهجستجو
ℎ 𝑘, 𝑖
هزینهجستجو=
هزینهمتوسطجستجو؟
𝐸 𝑋 =𝑖𝑃𝑟 ( باشدامiخانهی,اولینخانهخالی(
Open Hashing
ℎ 𝑘, 0 ℎ 𝑘, 1 ℎ 𝑘, 2 … .
𝑖 + 1 اولینخانهخالی
.کنیماستفادهمیبرایبدستآوردنمتوسطهزینهجستجوازیکمتغیرتصادفی
X=هزینهجستجو
ℎ 𝑘, 𝑖هزینهجستجو=
هزینهمتوسطجستجو؟
𝐸 𝑋 =𝑖𝑃𝑟 ( باشدامiخانهی,اولینخانهخالی(
A(i)=رویدادیکهخانهiامپرباشد.
Pr X ≥ i = Pr(𝐴 0 ∩ 𝐴 1 ∩ ⋯∩ 𝐴 𝑖 − 1 )
Pr X = i = Pr 𝑋 ≥ 𝑖 − Pr(𝑋 ≥ 𝑖 + 1)
Open Hashing
ℎ 𝑘, 0 ℎ 𝑘, 1 ℎ 𝑘, 2 … .
𝑖 + 1 اولینخانهخالی
.کنیماستفادهمیبرایبدستآوردنمتوسطهزینهجستجوازیکمتغیرتصادفی
X=هزینهجستجو
ℎ 𝑘, 𝑖هزینهجستجو=
هزینهمتوسطجستجو؟
𝐸 𝑋 =𝑖𝑃𝑟 ( باشدامiخانهی,اولینخانهخالی(A(i)=رویدادیکهخانهiامپرباشد.
Pr X ≥ i = Pr(𝐴 0 ∩ 𝐴 1 ∩⋯∩ 𝐴 𝑖 − 1 )
Pr X = i = Pr 𝑋 ≥ 𝑖 − Pr(𝑋 ≥ 𝑖 + 1)
𝐸 𝑋 = σ 𝑖𝑃𝑟 ( )= σ 𝑖(𝑃𝑟 𝑥 ≥ 𝑖 − Pr(𝑥 ≥ 𝑖 + باشدامiخانهی,اولینخانهخالی((1
𝑖 𝑃𝑟 𝑥 ≥ 𝑖 − Pr 𝑥 ≥ 𝑖 + 1 =𝑃𝑟 𝑥 ≥ 𝑖 − iPr 𝑥 ≥ 𝑖 + 1 + 𝑖𝑃𝑟 𝑥 ≥ 𝑖 + 1 =Pr(𝑥 ≥ 𝑖)
Open Hashing
ℎ 𝑘, 0 ℎ 𝑘, 1 ℎ 𝑘, 2 … .
𝑖 + 1 اولینخانهخالی
.کنیماستفادهمیبرایبدستآوردنمتوسطهزینهجستجوازیکمتغیرتصادفی
X=هزینهجستجو
ℎ 𝑘, 𝑖هزینهجستجو=
هزینهمتوسطجستجو؟
𝐸 𝑋 =𝑖𝑃𝑟 ( باشدامiخانهی,اولینخانهخالی(A(i)=رویدادیکهخانهiامپرباشد.
Pr X ≥ i = Pr(𝐴 0 ∩ 𝐴 1 ∩⋯∩ 𝐴 𝑖 − 1 )
Pr X = i = Pr 𝑋 ≥ 𝑖 − Pr(𝑋 ≥ 𝑖 + 1)
𝐸 𝑋 = σ 𝑖𝑃𝑟 ( )=σPr(𝑥 ≥ 𝑖)خانهی,اولینخانهخالیiباشدام
Pr X ≥ i =n
m∗n − 1
m− 1∗ … .∗
n − i + 1
𝑚− 𝑖 + 1≤
𝑛
𝑚
𝑖
=∝𝑖
Open Hashing
ℎ 𝑘, 0 ℎ 𝑘, 1 ℎ 𝑘, 2 … .
𝑖 + 1 اولینخانهخالی
.کنیماستفادهمیبرایبدستآوردنمتوسطهزینهجستجوازیکمتغیرتصادفی
X=هزینهجستجو
ℎ 𝑘, 𝑖هزینهجستجو=
هزینهمتوسطجستجو؟
𝐸 𝑋 =𝑖𝑃𝑟 ( باشدامiخانهی,اولینخانهخالی(A(i)=رویدادیکهخانهiامپرباشد.
Pr X ≥ i = Pr(𝐴 0 ∩ 𝐴 1 ∩⋯∩ 𝐴 𝑖 − 1 )
Pr X = i = Pr 𝑋 ≥ 𝑖 − Pr(𝑋 ≥ 𝑖 + 1)
𝐸 𝑋 = σ 𝑖𝑃𝑟 ( )=σPr 𝑥 ≥ 𝑖 = σ ∝𝑖≅1
1−∝= 𝑂(
1
1−∝باشدامiخانهی,اولینخانهخالی(
Pr X ≥ i =n
m∗n − 1
m− 1∗ … .∗
n − i + 1
𝑚− 𝑖 + 1≤
𝑛
𝑚
𝑖
=∝𝑖
Open Hashingهزینهمتوسطجستجوموفق؟
𝑂(1
∝
𝑙𝑛𝑛
1 −∝)
43
Discussion
؟
Arash Vaezi
Recommended