Ҳадиса чӣ гуна аст?

Ҳеш таблица — бу маълумотлар тузилмаси бўлиб, у асоциатив массив (луғат)ни амалга оширади. У "калит-ҳақиқий" жупларини сақлайди, бу ерда калитлар уникал.

Асосий принциплар:

• Ҳеш функцияси: Калитни рақамга (ҳеш-код ёки индекс) айлантиради. Бу индекс сақлаш жойини кўрсатади (қутуча).
• Масив (қутучалар): Ҳақиқий "калит-ҳақиқий" жупларининг сақланиши.
• Коллизиялар: Турли калитлар бир хил ҳеш-кодини ишлаб чиқарадиган ҳолат.

Коллизияларни ҳал қилиш:

• Ланцинг усули (Separate chaining): Ҳар бир қутучада, бир хил ҳеш-кодга эга элементлар рўйхати (ёки бошқа маълумот тузилмаси) сақланади.
• Очиқ манзиллаш (Open addressing): Коллизия бўлса, бўш қутучани қидириш учун турли стратегиялар (линейли сондириш, квадратик сондириш, иккилик ҳешлаш) қўлланилади.

Хусусиятлар:

• Тез кириш: Идеал ҳолда O(1) қўшиш, қидириш ва ўчириш амалиётлари учун.
• Ҳеш функциясига боғлиқлик: Ҳеш функциясининг сифатини ва коллизияларни ҳал қилиш стратегиясини яхши танлаш ишлаш самарадорлигига катта таъсир кўрсатади.
• Мемори ёки ҳажмдан фойдаланиш: Қўшимча ёдгорига эҳтиёж бор.

QAда қўлланиши:

• Тест маълумотларини сақлаш (калит - параметр номи, қиймат - кутилган ёки ҳақиқий қиймат).
• Элементларнинг бирдеклигини текшириш (масалан, фойдаланувчи IDлари).
• Кэшларни амалга ошириш.