در این مطلب، ویدئو مدیریت برخورد در جدول هش – آموزش ساختارهای داده و الگوریتم ها در پایتون شماره 6 با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:18:21
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,120 –> 00:00:02,370
در این آموزش ساختار داده، ما
2
00:00:02,370 –> 00:00:04,440
قصد داریم
3
00:00:04,440 –> 00:00:08,580
در ویدیوی قسمت 1 نحوه مدیریت برخوردها در جدول هش را بررسی کنیم
4
00:00:08,580 –> 00:00:11,040
که اگر قبلاً
5
00:00:11,040 –> 00:00:12,990
آن را ندیدهاید، به شدت توصیه میکنم آن را تماشا کنید،
6
00:00:12,990 –> 00:00:16,650
جدول هش را در پایتون پیادهسازی کردهایم،
7
00:00:16,650 –> 00:00:18,420
آن کلاس را میگیریم و ما
8
00:00:18,420 –> 00:00:21,090
قصد داریم آن را برای رسیدگی به برخورد
9
00:00:21,090 –> 00:00:23,130
با استفاده از روش زنجیرهای جداگانه تقویت کنیم،
10
00:00:23,130 –> 00:00:25,560
همچنین به کاوش خطی میپردازیم و در
11
00:00:25,560 –> 00:00:27,840
پایان چند
12
00:00:27,840 –> 00:00:31,080
تمرین جالب برای شما داریم که میتوانید در اینجا در این تصویر حل کنید.
13
00:00:31,080 –> 00:00:33,090
من یک نقشه هش دارم که کلید
14
00:00:33,090 –> 00:00:35,700
آن به عنوان مثال علامت 6 و مقدار
15
00:00:35,700 –> 00:00:39,149
310 با استفاده از تابع هش است، ما در حال یافتن
16
00:00:39,149 –> 00:00:41,969
شاخص مناسب در آرایه خود هستیم، به
17
00:00:41,969 –> 00:00:44,340
عنوان مثال در اینجا برای 6 مارس
18
00:00:44,340 –> 00:00:48,570
و آن مقدار در اینجا ذخیره می شود، اما زمانی که
19
00:00:48,570 –> 00:00:52,110
من یک برخورد دریافت می کنم که به این معنی است که برای یک
20
00:00:52,110 –> 00:00:56,280
کلید دیگر کمتر amar 17 است.
21
00:00:56,280 –> 00:00:58,980
آیا من در اینجا انجام می دهم من باید چند کار
22
00:00:58,980 –> 00:01:01,710
خاص انجام دهم زیرا اکنون دو
23
00:01:01,710 –> 00:01:04,379
کلید سعی می کنند مقادیر خود را در یک مکان ذخیره کنند، در
24
00:01:04,379 –> 00:01:06,720
اینجا می توانیم از
25
00:01:06,720 –> 00:01:08,850
رویکردی به نام زنجیره جداگانه یا
26
00:01:08,850 –> 00:01:11,250
زنجیره ای استفاده کنیم که در آن به جای ذخیره
27
00:01:11,250 –> 00:01:14,159
مستقیم g مقداری که ما یک لیست پیوندی
28
00:01:14,159 –> 00:01:17,460
یا یک لیست را در هر مکان ذخیره می کنیم، بنابراین ابتدا
29
00:01:17,460 –> 00:01:20,369
وقتی ریاضی 6 وارد شد،
30
00:01:20,369 –> 00:01:23,060
دفعه بعد که برخورد داشتیم این عنصر را به لیست پیوندی اضافه می
31
00:01:23,060 –> 00:01:26,159
کنیم و
32
00:01:26,159 –> 00:01:28,080
عنصر دوم وارد می شود، فقط آن را به
33
00:01:28,080 –> 00:01:30,600
لیست پیوندی خاص اضافه می کنیم. به این ترتیب
34
00:01:30,600 –> 00:01:33,290
این لیست پیوندی میتواند به رشد خود ادامه دهد و
35
00:01:33,290 –> 00:01:36,630
چندین کلید میتوانند مقدار هش یکسانی را به اشتراک بگذارند.
36
00:01:36,630 –> 00:01:40,979
تجزیه و تحلیل Big O در اینجا به این صورت است
37
00:01:40,979 –> 00:01:45,210
که معمولاً برای متوسط
38
00:01:45,210 –> 00:01:49,680
یدگی جستجوی نقشه هش موردی مرتبه 1 است که زم
39
00:01:49,680 –> 00:01:52,259
ن ثابتی است، اما در این مورد مم
40
00:01:52,259 –> 00:01:55,380
ن است ادامه یابد. تا مرتبه n زیرا
41
00:01:55,380 –> 00:01:58,350
تصور کنید اگر عملکرد هش بدی دارید
42
00:01:58,350 –> 00:02:01,740
و همه عناصر همه
43
00:02:01,740 –> 00:02:04,710
کلیدها شاخص یکسانی تولید می
44
00:02:04,710 –> 00:02:07,049
کنند، همه مقادیر سهام خود را در یک
45
00:02:07,049 –> 00:02:08,910
سطل خواهید داشت و این یک لیست پیوندی طولانی خواهد بود،
46
00:02:08,910 –> 00:02:10,649
بنابراین در آن صورت جستجو
47
00:02:10,649 –> 00:02:13,230
پیچیدگی همان پیچیدگی
48
00:02:13,230 –> 00:02:13,860
یک لیست پیوندی است
49
00:02:13,860 –> 00:02:16,770
که به ترتیب است و وقتی اکنون
50
00:02:16,770 –> 00:02:19,860
میخواهم مقدار 17 مارس را
51
00:02:19,860 –> 00:02:21,960
برگردانم تابع هش است تا شاخصی به دست بیاورم که 9 است،
52
00:02:21,960 –> 00:02:22,410
53
00:02:22,410 –> 00:02:25,190
به فهرست شماره نه میروم سپس به
54
00:02:25,190 –> 00:02:28,710
صورت خطی این l را جستجو میکنم. فهرست جوهر شده و به
55
00:02:28,710 –> 00:02:31,440
همین دلیل مهم است که کلید خود را
56
00:02:31,440 –> 00:02:34,200
در هر یک از این عناصر ذخیره کنید تا
57
00:02:34,200 –> 00:02:37,050
بدانید که کدام مقدار
58
00:02:37,050 –> 00:02:40,380
با کدام کلید مرتبط است. روش دوم برای
59
00:02:40,380 –> 00:02:42,630
حل تصادم، کاوش خطی نامیده می شود
60
00:02:42,630 –> 00:02:46,380
در اینجا کاری که ما انجام می دهیم، سپس 17 خود را تشکیل می دهیم.
61
00:02:46,380 –> 00:02:50,310
در نه و متوجه می شویم که
62
00:02:50,310 –> 00:02:53,670
قبلاً یک ذخیره ارزش در این مکان وجود دارد،
63
00:02:53,670 –> 00:02:56,910
به مکان موجود بعدی می رویم در
64
00:02:56,910 –> 00:02:59,370
اینجا آرایه من در اینجا به پایان می رسد، اما بیایید
65
00:02:59,370 –> 00:03:00,810
بگوییم اگر یک مکان دهم
66
00:03:00,810 –> 00:03:04,880
خالی بود، من 17 مارس را ذخیره
67
00:03:04,880 –> 00:03:07,380
می کردم. آن مکان را نداشته
68
00:03:07,380 –> 00:03:10,170
باشم به مکان 0-2 معکوس نگاه خواهم کرد
69
00:03:10,170 –> 00:03:12,660
که آن مکان نیز پر شده است،
70
00:03:12,660 –> 00:03:15,660
بنابراین به مکان شماره یک می روم و در اینجا
71
00:03:15,660 –> 00:03:18,930
مقدار 17 مارس خود را ذخیره می کنم که به آن
72
00:03:18,930 –> 00:03:21,500
کاوش خطی می گویند زیرا کاوش خطی
73
00:03:21,500 –> 00:03:24,900
به معنای جستجو است. برای یک
74
00:03:24,900 –> 00:03:28,260
شکاف خالی برای ذخیره ارزیابی من
75
00:03:28,260 –> 00:03:31,500
مثال دیگری که در آن 18 مارس به ایندکس
76
00:03:31,500 –> 00:03:34,410
0 تصمیم گرفت، قبلاً مقادیر شاخص un – چاه
77
00:03:34,410 –> 00:03:37,140
شماره 1 وجود داشت که آن نیز پر شده است، بنابراین
78
00:03:37,140 –> 00:03:39,420
اکنون مقدار خود را در شاخص
79
00:03:39,420 –> 00:03:42,030
شماره 2 ذخیره کرده اید، اکنون بیایید پیاده سازی کنیم. زنجیر زدن در
80
00:03:42,030 –> 00:03:44,310
پایتون در اینجا من یک کلاس پایتون
81
00:03:44,310 –> 00:03:46,650
دارم که در قسمت 1 این آموزش پیاده سازی کردیم
82
00:03:46,650 –> 00:03:47,310
83
00:03:47,310 –> 00:03:49,440
و این کلاس تمام برخوردها را مدیریت نمی
84
00:03:49,440 –> 00:03:51,510
کند بلکه این کار را انجام می دهد و یک تابع هش دریافت می
85
00:03:51,510 –> 00:03:54,120
کند و هنگامی که آیتم یا آیتم را دریافت
86
00:03:54,120 –> 00:03:56,340
کردید به شاخص خاصی می رود.
87
00:03:56,340 –> 00:03:58,680
آرایه خود را ذخیره کنید و مقدار را ذخیره کنید، من به شما نشان خواهم داد
88
00:03:58,680 –> 00:04:01,290
که این کلاس چه مشکلی خواهد داشت، بنابراین
89
00:04:01,290 –> 00:04:05,310
در اینجا من تابع هش را دارم
90
00:04:05,310 –> 00:04:08,130
که فرم r6 و 17 مارس نامیده می شود و شما می دانید
91
00:04:08,130 –> 00:04:11,730
که هر دو دارای شاخص یکسانی هستند، بنابراین
92
00:04:11,730 –> 00:04:15,299
وقتی مقداری مانند این را ذخیره می کنم 6 مارس
93
00:04:15,299 –> 00:04:19,380
من مقدار 1 20 mr 17 دارم 459 است، اما
94
00:04:19,380 –> 00:04:22,048
از آنجایی که جرم 17 همان شاخص را
95
00:04:22,048 –> 00:04:24,240
دارد، مقدار جرم 6 را بیش از حد برمی گرداند،
96
00:04:24,240 –> 00:04:27,599
بنابراین وقتی می گویم
97
00:04:27,599 –> 00:04:31,289
مقدار 6 مارس را برای من دریافت کنید، دارم 459 می گیرم، ببینید 120 را ذخیره کردم
98
00:04:31,289 –> 00:04:34,650
اما من 459 را دریافت می کنم و این به
99
00:04:34,650 –> 00:04:37,440
دلیل برخورد است زیرا در 17 مارس این
100
00:04:37,440 –> 00:04:40,530
مقدار 459 بیشتر است یا آن، بنابراین اکنون می
101
00:04:40,530 –> 00:04:42,570
خواهیم آن برخورد را در همین
102
00:04:42,570 –> 00:04:44,460
کلاس در اینجا برطرف کنیم اولین کاری که می خواهم
103
00:04:44,460 –> 00:04:48,530
انجام دهم این است که به جای مقداردهی اولیه هیچ به عنوان
104
00:04:48,530 –> 00:04:51,560
عنصر منفرد. من آرایه خالی را مقداردهی اولیه می کنم
105
00:04:51,560 –> 00:04:56,250
زیرا n هر
106
00:04:56,250 –> 00:04:58,770
عنصر فقط مقداری نیست که ما جفت مقادیر کلیدی را ذخیره می کنیم،
107
00:04:58,770 –> 00:05:01,110
بنابراین اگر از اولین ارائه ما به یاد داشته باشید،
108
00:05:01,110 –> 00:05:04,979
109
00:05:04,979 –> 00:05:07,470
هر زمان که برخورد داشته باشیم، جفت ارزش کلید را ذخیره می کنیم تا
110
00:05:07,470 –> 00:05:09,360
بتوانیم به عنصر مناسب نگاه کنیم، به
111
00:05:09,360 –> 00:05:12,479
همین دلیل است که من آرایه هایی در هر یک از آنها دارم.
112
00:05:12,479 –> 00:05:14,820
عنصر منفرد تابع هش GAT
113
00:05:14,820 –> 00:05:17,130
یکسان باقی می ماند، ما نیازی به زنجیره
114
00:05:17,130 –> 00:05:19,860
ای نداریم که اکنون می خواهیم
115
00:05:19,860 –> 00:05:21,539
تابع set item را در پیاده سازی اصلی خود
116
00:05:21,539 –> 00:05:24,539
پیاده سازی کنیم، ما قبلاً
117
00:05:24,539 –> 00:05:28,470
مقدار را در شاخص H نادیده می گرفتیم اما در شاخص H اکنون
118
00:05:28,470 –> 00:05:30,210
یک لیست پیوندی داریم. ما باید
119
00:05:30,210 –> 00:05:32,340
از طریق لیست پیوند داده شده را تکرار کنیم و برای
120
00:05:32,340 –> 00:05:34,830
یافتن مکان مناسب یا به روز رسانی
121
00:05:34,830 –> 00:05:38,099
ارزش خود بجنگیم، بنابراین اولین کاری که انجام می دهیم این است که در
122
00:05:38,099 –> 00:05:41,310
لیست پیوندی ما این است که این عنصر
123
00:05:41,310 –> 00:05:44,190
از قبل وجود داشته باشد، بنابراین
124
00:05:44,190 –> 00:05:47,400
ممکن است شما قبلاً 6 مارس داشته باشید. در
125
00:05:47,400 –> 00:05:50,340
موقعیت مکانی خود و شما مانند ok خواهید بود،
126
00:05:50,340 –> 00:05:52,440
بیایید مقدار را با چیز دیگری به روز کنیم،
127
00:05:52,440 –> 00:05:55,729
به عنوان مثال در اینجا اگر
128
00:05:55,729 –> 00:05:58,770
چیزی شبیه به این دارید که در ابتدا
129
00:05:58,770 –> 00:06:01,680
جرم شش را وارد کرده اید، اما دفعه بعد می
130
00:06:01,680 –> 00:06:04,560
خواهید همان va را به روز کنید. خوب است برای
131
00:06:04,560 –> 00:06:06,840
آن کلید، بنابراین ما ابتدا به این مورد خاص رسیدگی می کنیم،
132
00:06:06,840 –> 00:06:12,270
بنابراین اجازه دهید
133
00:06:12,270 –> 00:06:13,890
قبل از اینکه آن
134
00:06:13,890 –> 00:06:15,960
را به زبان بیاوریم، آن را مشخص کنیم، اجازه دهید حالت ساده ای را به شما نشان دهم،
135
00:06:15,960 –> 00:06:21,229
بنابراین فرض کنید در این شاخص یا
136
00:06:21,229 –> 00:06:25,280
این کلید خاص در آن کلید وجود ندارد.
137
00:06:25,280 –> 00:06:30,360
در صورتی که کاری که انجام خواهید داد به سادگی در
138
00:06:30,360 –> 00:06:32,700
آن لیست پیوندی است، بنابراین این مورد خاص،
139
00:06:32,700 –> 00:06:35,849
این یک لیست پیوندی است یا در
140
00:06:35,849 –> 00:06:39,190
پایتون ما فقط از لیستی در اینجا استفاده
141
00:06:39,190 –> 00:06:43,480
می کنیم که می خواهید جفت ارزش کلید را به روز کنید
142
00:06:43,480 –> 00:06:45,850
، این سناریوی ساده ما خواهد بود، اما شما
143
00:06:45,850 –> 00:06:49,090
این کار را انجام خواهید داد. فقط در صورتی که کلید
144
00:06:49,090 –> 00:06:52,240
در آن لیست پیوندی وجود نداشته باشد، از این رو می
145
00:06:52,240 –> 00:06:55,030
خواهید ابتدا بفهمید که آیا کلید وجود دارد یا نه،
146
00:06:55,030 –> 00:06:59,470
بنابراین برای عنصر شاخص می گویید
147
00:06:59,470 –> 00:07:03,700
بنابراین enumerate تابعی است که از آن
148
00:07:03,700 –> 00:07:07,600
برای تبادل عناصر در
149
00:07:07,600 –> 00:07:13,420
آرایه خود استفاده می کنید. اگر طول عنصر
150
00:07:13,420 –> 00:07:20,620
برابر با 2 و عنصر 0 برابر با کلید باشد،
151
00:07:20,620 –> 00:07:23,680
یعنی برای این کلید من قبلاً
152
00:07:23,680 –> 00:07:26,380
یک عنصر دارم، بنابراین شما فقط
153
00:07:26,380 –> 00:07:29,890
یک مقدار را تغییر می دهید، بنابراین در همان
154
00:07:29,890 –> 00:07:32,380
عنصر یک مقدار را تغییر می دهید، اما از آنجایی که ما یک مقدار را
155
00:07:32,380 –> 00:07:35,440
وارد می کنیم. تاپل یا تاپل الف
156
00:07:35,440 –> 00:07:40,600
تغییرناپذیر است بنابراین نمی توانم فقط بگویم عنصر
157
00:07:40,600 –> 00:07:43,720
1 برابر است با مقدار شما می دانید به جای
158
00:07:43,720 –> 00:07:45,820
سرنگونی اگر از آرایه دیگری استفاده می
159
00:07:45,820 –> 00:07:48,630
کردید ممکن بود کار کند بنابراین من فقط می خواهم
160
00:07:48,630 –> 00:07:51,070
یک جدول جدید را اساساً در
161
00:07:51,070 –> 00:07:54,100
همان مکان وارد کنم تا مکان من اول باشد. از
162
00:07:54,100 –> 00:07:58,330
همه اینها و در آن
163
00:07:58,330 –> 00:08:03,850
ایندکس خاص، این مکان مقدار کلیدی را ذخیره
164
00:08:03,850 –> 00:08:06,850
خواهم کرد، امیدوارم منطقی باشد اگر
165
00:08:06,850 –> 00:08:09,010
این کمی پیچیده باشد، به شما پیشنهاد می کنم
166
00:08:09,010 –> 00:08:12,760
این را در پایتون اشکال زدایی کنید و وقتی
167
00:08:12,760 –> 00:08:14,440
از هسته عبور کردید، ایده خروجی
168
00:08:14,440 –> 00:08:17,250
از آنچه را که من در اینجا سعی می کنم این کار را انجام دهم و
169
00:08:17,250 –> 00:08:20,470
این برابر با true است تا
170
00:08:20,470 –> 00:08:26,530
اتفاق بیفتد چیز پیدا شده درست می شود و
171
00:08:26,530 –> 00:08:33,099
شما از حلقه خارج می شوید بنابراین عنصر پیدا شده
172
00:08:33,099 –> 00:08:40,659
ابتدا اشتباه است و سپس
173
00:08:40,659 –> 00:08:45,130
اگر عنصر شما تشکیل نشده باشد این کار را انجام می دهید
174
00:08:45,130 –> 00:08:47,710
که به این معنی است که من
175
00:08:47,710 –> 00:08:49,260
این کلید را
176
00:08:49,260 –> 00:08:51,840
در جدول هش خود نداشتم، به همین د