Bizda quyidagi matn bor bo’lsin

Muammo : Xesh-jadvalni talabalar haqidagi ma'lumotlarni saqlashi uchun qanday qilib kengaytiramiz? Ularni topish uchun biz hali ham talabaning ismini qidirmoqchimiz, lekin biz darhol ular haqidagi maʼlumotlarga, masalan, harf bahosi, bitirgan yili va hokazolarga ega boʻlamiz.
Biz qilishimiz kerak bo'lgan narsa - barcha ma'lumotlarni o'z ichiga oladigan bog'langan ro'yxat tuzilmasini o'zgartirish:
typedef struct _list_t_ {char *nomi; /* va, albatta, */ int grad_year nomini ishlatish uchun kodimizni o'zgartirishimiz kerak; char letter_grade; struct _list_t_ *keyingi; } list_t;
Muammo: Agar kodingizga biror narsa yuz bergan bo'lsa va siz xash-jadvalda ko'p ma'lumotlarni saqlaganingizdan so'ng tasodifan xesh funktsiyasini yo'qotib qo'ysangiz, qanday qilib ma'lum bir qatorni qidirasiz? Endi qidiruv samaradorligi qanday bo'ladi?
Yuqoridagi hisoblash funksiyasida bo'lgani kabi, siz qidirayotgan narsangizni topmaguningizcha, xesh jadvalini chiziqli qidirishingiz mumkin. Ammo bu O (1) ning oddiy xesh qidirish samaradorligi bilan solishtirganda juda samarasiz . Biz n satr orqali chiziqli qidiruvni amalga oshirayotganimiz sababli, bu strategiyaning samaradorligi O ( n ) dir .
Muammo: To'qnashuvning oldini olishning yana bir usuli - chiziqli zondlash. Chiziqli probing yordamida, agar to'qnashuv ro'y bersa, siz ketma-ket ravishda heshtabledagi joriy joydan keyingi ochiq joyni qidirasiz va satrni u erda saqlang. Ushbu usulning samaradorlik nuqtai nazaridan kiritish uchun qanday kamchiliklari bor?
Chiziqli zondni kiritish O ( n ) bo'lishi mumkin , alohida zanjir esa O (1) bo'lishi mumkin , chunki siz har doim ro'yxatning boshiga kiritasiz.

Rabin-Karp algoritmi

Hashing orqali string qidirish

Ikki satr bir xil yoki yo'qligini tekshirish usuli sifatida xeshlash texnikasidan foydalanishimiz mumkin - agar ikkita satr bir xil qiymatga hash bo'lsa, ular bir xil satr bo'lishi mumkin, lekin agar ular turli qiymatlarga hash bo'lsa . keyin, albatta, bir xil emas . Bu xususiyat 8.2 algoritmida ko'rsatilganidek, qatorni qidirish algoritmida ishlatilishi mumkin .

Biroq, birinchi tahlilda, bu dahshatli g'oyaga o'xshaydi: yaxshi xesh funktsiyalari satrdagi har bir belgiga qarash kerak. Agar naqsh uzunligi M bo'lsa va xesh funksiyasi pastki qatordagi har bir belgiga qarasa, M uzunlikdagi pastki qatorning xeshini hisoblash uchun (hech bo'lmaganda) O ( M ) kerak bo'ladi. Agar xeshlash funksiyasi satrdagi har bir belgini ko‘rib chiqsa, u holda bu algoritm matndagi M - N mumkin bo‘lgan har bir pozitsiyada O ( N ) hisobini bajarishi kerak bo‘ladi va bu algoritm O ( M ( M -) bo‘ladi. N )).
Agar siz 8.1.1- bo'limni eslayotgan bo'lsangiz , O ( M ( M - N )) sodda algoritmning eng yomon holatining vaqt murakkabligi ! Bu, albatta, yomon belgidir - ko'rinishidan, xeshlashdan foydalanib, biz o'zimizni har doim qo'pol kuch algoritmining eng yomon holatida bajariladigan ish hajmini bajarishga mahkum qilamiz.
Siz taxmin qilganingizdek, bu muammoni hal qilishning bir yo'li bor. Bitta xeshni bajarish uchun zarur bo'lgan ish hajmini kamaytirishning umumiy usuli bo'lmasa-da , bir-biri bilan bog'liq bo'lgan qatorlar guruhi uchun juda samarali hisoblanishi mumkin bo'lgan xeshlash funktsiyalari mavjud . Ushbu algoritmda har bir kichik satr keyingi pastki qator bilan chambarchas bog'liq: keyingi pastki satr oddiygina bir uchidan kesilgan bitta belgi va ikkinchi uchiga yangi belgi qo'shiladi.
Ushbu haqiqatdan foydalanadigan yaxshi xeshlash funktsiyasini ishlab chiqa olamizmi? Bir nechtasi bor, lekin tez-tez ishlatiladigan biri 8.1 -rasmda ko'rsatilgan . Ushbu xeshlash funksiyasi qatorni katta raqam sifatida ko'rib chiqadi, bunda massivdagi har bir belgi b bazasidagi sondagi raqamni ifodalaydi . Keyin bu raqamning moduli xesh qiymatini berish uchun p tomonidan olinadi. Yaxshi natijalarga erishish uchun bu p ni shunday tanlash kerakki, u va b nisbatan tub bo'ladi; Bu b yoki p ning asosiy bo'lishi bilan osonlik bilan amalga oshiriladi.