каква е мотивацията зад процедурата за метод на умножение за хеширане?

Започнах да научавам за хеширането от CLRS (Cormen et al.). Успях да разбера математическата процедура и как следва компютърната реализация. Книгата просто посочва математическата процедура като-

-> multiply the key k with a constant A (0<A<1), results into kA;

-> extract the fractional part of kA by doing (kA mod 1);

-> multiply the result with m (usually taken to be a power of 2 for easy 
implementation on computers);

-> take the floor of this result and that is the hashed value;

-> therefore, this is the hashing function, h(k) = floor[m*(kA mod 1)]

книгата по-нататък посочва как ще бъде приложен на повечето компютри, предимствата му пред метода на разделяне и предложението на Кнут за стойността на „А“.

Това, което не мога да разбера, е ЗАЩО следваме тази процедура на конкретно умножаване на ключа с число (A) в диапазона от 0 до 1 и след това вземане на дробната част, последвано от умножение по m и след това вземане на думата?

Това създава ли хеширани стойности, които „наподобяват много“ SUHA (предположение за просто равномерно хеширане), т.е. в идеалния случай всеки ключ трябва независимо да хешира към всеки от m слота, така че този метод дава ли резултати, „по-близки“ до този идеал?


methods hash multiplication hashtable
person Jai Jain    schedule 08.04.2019    source източник

Отговори (2)


arrow_upward
0
arrow_downward

В идеалния случай хеширането трябва да отговаря на предположението за просто равномерно хеширане.

Например в хешираща функция h(k): U--> {0...m-1}, където U е наборът от възможни ключове, а m е размерът на таблицата

Което означава, че всеки ключ във Вселената от ключове трябва да има еднаква вероятност да се окаже на едно и също място всеки път, когато го хеширате и разпределението на ключовете е равномерно разпределено във всички местоположения, нали?

Е, не е толкова лесно на практика, ние не знаем вероятността за разпределението на ключовете предварително и дори и да знаем, пак не знаем кои ще бъдат изтеглени от тази вселена.

Така че трябва да станем практични въз основа на това, което знаем за ключовете, за да създадем някакво изчисление на k, което да се представя добре и да разпределя ключовете добре в таблицата.

Това е мястото, където навлизаме в търговията между методите,

Вземете метода на разделяне: Просто h(k) = k mod m Ключ по модула на размера на вашата маса. Просто, бързо и произвежда само законни стойности, но трябва да изберете своя m много внимателно! Например, ако таблицата е степен на 2, вие по същество вземате най-малко значимите битове от k и тези ключове вероятно ще покажат определена структура. Така че изберете просто число за m вероятно близо до точната степен на 2.

Нека да преминем към метода на умножение за известен контраст: h(k) = floor[m*(kA mod 1)] където (0<A<1)

Ние умножаваме нашия ключ с дробно число, така че mod 1 е там, за да премахне дробния компонент. По същество вие ще умножите m с число между 0 до, но не включително 1 и накрая, ние вземаме думата на резултата от това, за да получим цяло число. Това е по-бавно от метода на разделяне, но няма значение какво избирате за m Стойността на m не е критична!

Обратно към въпроса ви, зависи изцяло от това какъв вид реализация имате и следователно как трябва да използвате съответно хеш-таблици. Има много там.

person Ulug Toprak    schedule 08.04.2019

arrow_upward
0
arrow_downward

Когато умножим дробната част на kA (която е някъде в интервал [0,1]) по m, ние генерираме стойност в диапазона от 0 до m-1, която след това може да се използва като индекс на хеш-таблицата. Нека означим дробната част на kA с {kA}.

Тази процедура също, както всяка друга хеш функция, може или не може да разпредели входните ключове (които не са известни предварително) равномерно.

Да предположим, че има няколко последователни целочислени ключа и искаме да осигурим тяхното равномерно разпределение. За това ще трябва да направим стойностите {kA} възможно най-еднакви в интервал [0,1]. Ако това може да се направи, крайният хеш (след умножаване с m) също ще бъде разпределен добре в диапазона от 0 до m-1. В този смисъл стойността на A тогава става важна и CLRS препоръчва (което само по себе си препраща към Knuth) 1/golden-ratio за A. С това генерираните стойности на {kA} ще бъдат добре разпределени в [0,1].

person Nitin Verma    schedule 15.01.2021