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