Хэш функц
Хэш функц гэж юу вэ? Энгийн тайлбар өгнө үү.
Хэш функц нь аль ч оролтыг (жишээ нь: тэмдэгт мөр эсвэл тоо) тогтмол хэмжээтэй тоон утга болгон хувиргадаг функц юм. Энэ нь өгөгдлийг хурдан индексжүүлэхэд ашиглагддаг.
Хэш хүснэгт гэж юу вэ? Python-д ямар өгөгдлийн бүтэц нь хэш хүснэгт дээр суурилдаг вэ?
Хэш хүснэгт нь түлхүүр-утга (key-value) хосуудыг хэш функц ашиглан массивт хадгалдаг өгөгдлийн бүтэц. Python-д dict болон set нь хэш хүснэгт дээр суурилдаг.
Hash collision (хэш зөрчил) гэж юу вэ? Жишээ тайлбарла.
Хариultыг харах
Хоёр өөр оролт (жишээ: 'ab' ба 'ba') ижил хэш утга үүсгэхийг hash collision гэнэ. Жишээ: хэрэв hash('abc') == hash('xyz') бол зөрчил гарсан гэнэ.
Хэш функцийн 'deterministic' шинж чанар гэж юуг хэлэх вэ?
Deterministic гэдэг нь ижил оролт өгвөл үргэлж ижил хэш утгыг буцаадаг гэсэн үг. Жишээ нь: hash('hello') нь үргэлж нэг утгыг буцаана.
Хэш хүснэгтэд элемент хайх, оруулах, устгах гурван үйлдлийн дундаж цаг O(1) байдгийн шалтгаан юу вэ?
Хэш функц нь түлхүүрийг шууд индекс болгодог тул массивт нэг алхмаар хандах боломжтой. Иймд хайлт, оруулалт, устгалт нь дундажаар O(1) байдаг (зөрчилгүй тохиолдолд).
Python-д хэш хүснэгтийн worst-case хайлтын цаг яагаад O(n) болдог вэ?
Бүх элемент нэг индекст зөрчил гарвал, хайлт тухайн бүлгийн бүх элементийг дайрах шаардлагатай болдог. Ийм тохиолдолд хайлт O(n) болно. Энэ нь ихэвчлэн маш муу хэш функц ашиглах эсвэл хортой оролт (DoS халдлага) үед тохиолддог.
Python-д `hash()` функцийг ямар төрлийн объектод хэрэглэж болохгүй вэ? Жишээ хэлнэ үү.
Python-д өөрчлөгдөх (mutable) объектод hash() хэрэглэж болохгүй. Жишээ нь: list ([1,2,3]), dict, set зэрэг. Эдгээр нь unhashable гэж нэрлэгддэг.
Load factor гэж юу вэ? Python-ийн dict-д load factor ямар утгад хүрэхэд дахин хуваарилалт (rehashing) хийгддэг вэ?
Load factor = оруулсан элементийн тоо / хүснэгтийн нийт хэмжээ. Python-ийн dict нь load factor 2/3 (~0.67)-д хүрэхэд хүснэгтийн хэмжээг хоёр дахин нэмэгдүүлж rehash хийдэг.
Python-д `__hash__` ба `__eq__` аргуудын хоорондын хамаарлыг тайлбарла. Яагаад хоёулангийнхийг нэгэн зэрэг тодорхойлох ёстой вэ?
Хоёр объект тэнцүү бол (__eq__ True буцаана) тэдгээр нь ижил hash утгатай байх ёстой (__hash__). Хэрэв __eq__-г тодорхойлвол __hash__-г ч тодорхойлох ёстой, эс бол Python автоматаар __hash__-г None болгоно. Энэ нь dict/set-д зөв ажиллахад зайлшгүй.
Avalanche effect гэж юу вэ? Хэш функцтэй ямар холбоотой вэ?
Avalanche effect нь оролт дахь нэг битийн өөрчлөлт нь хэш утгын ихэнх хэсгийг өөрчлөхөд хүргэдэг шинж чанар. Энэ нь хэш функцийн аюулгүй байдал, тараалтын чанарыг нэмэгдүүлдэг.
Open addressing ба separate chaining зөрчил шийдвэрлэх аргуудын ялгааг дэлгэрэнгүй тайлбарла.
Separate chaining: зөрчил гарсан индекст холбогдсон жагсаалт үүсгэдэг. Open addressing: зөрчил гарвал массив дотроос дараагийн чөлөөт байрыг хайдаг (linear, quadratic, double hashing). Python-ийн dict нь open addressing ашиглана.
Double hashing гэж юу вэ? Томьёог бичиж тайлбарла. Linear probing-тай харьцуулна уу.
Double hashing: probe(i) = (h1(k) + i * h2(k)) % m. Хоёр дахь хэш функц алхамын хэмжээг тодорхойлдог тул кластер бага үүсдэг.
Double hashing нь тараалтыг сайжруулдаг ч хоёр хэш тооцоолол хийдэг тул арай удаан.
Cryptographic hash function ба non-cryptographic hash function-ийн ялгааг тайлбарла. SHA-256 болон MurmurHash жишээ болгон хэрэглэ.
Cryptographic (SHA-256): нэг чиглэлт, зөрчил олоход маш хэцүү, аюулгүй байдлын зорилгоор хэрэглэнэ. Non-cryptographic (MurmurHash): хурдан боловч буцааж тооцоолох боломжтой, хэш хүснэгтэд хэрэглэнэ. SHA-256 удаан ч найдвартай, MurmurHash хурдан ч аюулгүй байдал дутмаг.
$500
Python-ийн dict дэх hash table-ийн дотоод бүтцийг тайлбарла: compact dict, split dict гэж юу вэ? CPython-д хэрхэн хэрэгжсэн бэ?
CPython 3.6+ дээр dict нь compact representation ашигладаг: жижиг индекс массив + entries массив. Индекс массив нь хэш → слотын байрлалыг агуулна. Split dict нь ижил бүтцийн олон объектод (жишээ: class instance-д) хуваалцан ашиглагддаг хуваагдмал бүтэц. Энэ нь санах ойн хэрэглээг бууруулдаг.
Python-д хэш randomization (hash seed) гэж юу вэ? PYTHONHASHSEED гэж юу вэ? Яагаад энэ механизм нэвтрүүлсэн бэ?
Python 3.3+ дээр str, bytes, datetime-ийн hash утга програм эхлэх бүрт санамсаргүй seed ашиглан өөрчлөгддөг. PYTHONHASHSEED=0 гэвэл randomization унтардаг. Шалтгаан: Буруу оролтоор dict-д O(n) зөрчил үүсгэж DoS халдлага хийхэд (Hash DoS) хамгаалах зорилготой.