Индексті бейнелеу - Index mapping

Индексті бейнелеу (немесе тікелей мекен-жайнемесе а болмашы хэш функциясы) есептеу техникасы көмегімен сипаттайды массив, онда әр позициядағы батырмаға сәйкес келеді ғалам мүмкін мәндер.[1]Техника кілттер әлемі шамалы болған кезде, ең тиімді болып табылады бөлу барлық мүмкін кілттер үшін бір позициясы бар массив қол жетімді, оның тиімділігі массивтегі ерікті позицияны тексеруге болатындығында тұрақты уақыт.

Қолданылатын массивтер

Жарамды мәндері аз ауқымда шектелген көптеген мәліметтердің практикалық мысалдары бар. Тривиальды хэш функциясы - мұндай деректер іздеу кілті ретінде әрекет етуі керек болған кезде қолайлы таңдау. Кейбір мысалдарға мыналар кіреді:

  • ай жылы (1-12)
  • күн айда (1-31)
  • аптаның күні (1–7)
  • адам жасы (0–130) - мысалы. өмірді қалпына келтіретін актуарлық кестелер, мерзімді ипотека
  • ASCII жалпы математикалық операторлық таңбаларды, цифрларды, тыныс белгілерін және ағылшын тілінің алфавитін қамтитын таңбалар (0–127).

Мысалдар

Тривиальды хэш функциясын қолдану, қайталанбайтын кесте іздеу кезінде шартты тестілеуді және тармақталуды толығымен жоя алады, нұсқаулық жолының ұзындығы компьютерлік бағдарлама.

Тармақтанудан аулақ болыңыз

Роджер Сайл мысал келтіреді[2] жою а көп жол себеп болған ауысу мәлімдемесі:

кезекте bool Тек 30күн(int м){	қосқыш (м) {	іс 4:  // сәуір	іс 6:  // маусым	іс 9:  // қыркүйек	іс 11: // қараша		қайту шын;	әдепкі:		қайту жалған;	}}

Мұны кестені іздеумен ауыстыруға болады:

кезекте bool Тек 30күн(int м){	статикалық const bool Т[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };	қайту Т[м-1];}

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Кормен, Томас Х. (2009). Алгоритмдермен таныстыру (3-ші басылым). Кембридж, Массачусетс: MIT Press. 253–255 бет. ISBN  9780262033848. Алынған 26 қараша 2015.
  2. ^ Сайл, Роджер Энтони (17.06.2008). «Көп салалы кодтар генерациясының супер оптимизаторлық талдауы» (PDF). GCC әзірлеушілер саммитінің материалдары: 103–116. Алынған 26 қараша 2015.