Екі таңдаулы хештеу: Қолданылуы мен артықшылықтары
2-choice hashing
2 таңдаулы хештеу: екі хеш функциясымен кілттерді салыстырып, қақтығыс аз тізімге орналастыру. Орташа іздеу тиімділігін арттырады, қақтығыстарды азайтады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
2 таңдаулы хэштеу, сондай-ақ 2 таңдаулы тізбектеу деп аталады, – "екі хэш функциясын қолданып хэштеу арқылы кілттер қосылатын хэш кестесінің бір түрі. Кілт, қақтығыс тудыратын кілттер саны аз массивтік позицияға орналастырылады. Кілттерді тізбекте сақтамаса, қақтығыстарды шешу үшін бір схема қажет. Сәтті іздеудің орташа құны , мұндағы – кілттер саны, ал – массивтің көлемі. Ең көп қақтығыстар жоғары ықтималдықпен болады".
2 choice hashing, also known as 2 choice chaining, is "a variant of a hash table in which keys are added by hashing with two hash functions. The key is put in the array position with the fewer (colliding) keys. Some collision resolution scheme is needed, unless keys are kept in buckets. The average case cost of a successful search is , where is the number of keys and is the size of the array. The most collisions is with high probability."
Қалай жұмыс істейді
2 таңдаулы хэштеу екі хэш функциясын – h1(x) және h2(x) – пайдаланады, олар хэш функцияларынан күтілетіндей жұмыс істейді (яғни, бүтін сандарды белгілі бір диапазонға шамалайды). Екі хэш функция да тәуелсіз болуы керек және бір-бірімен байланыссыз болуы тиіс. Екі хэш функцияның болуы кез келген x кілттің h1(x) және h2(x) мәндеріне сәйкес, сақталуы мүмкін екі потенциалды орынға ие болуына мүмкіндік береді. Бір нәрсені еске алу қажет, екі хэш функция болғанымен, тек бір кесте бар; екі хэш функция да сол кестедегі орындарға шамалайды.
2 choice hashing utilizes two hash functions h1(x) and h2(x) which work as hash functions are expected to work (i. e. mapping integers from the universe into a specified range). The two hash functions should be independent and have no correlation to each other. Having two hash functions allows any key x to have up to two potential locations to be stored based on the values of the respective outputs, h1(x) and h2(x). It is important to note that, although there are two hash functions, there is only one table; both hash functions map to locations on that table.
Іске асыру
Бұл жағдайда хэштеуді іске асырудың ең маңызды функциялары – енгізу және іздеу. Енгізу: Енгізілетін объект үшін екі хэш-функцияның мәндері есептелінеді. Содан кейін объект, азырақ объектілер бар бөшке (bucket) орналастырылады. Егер бөшкелердің мөлшері тең болса, h1(x) мәні бойынша орналастырылады. Іздеу: Тиімді іздеу, ізделінетін мәнді табу үшін екі бөшкеде (h1(x) және h2(x) көрсеткен бөшкелерде) іздеу арқылы жүзеге асырылады.
The most important functions of the hashing implementation in this case are insertion and search. Insertion: When inserting the values of both hash functions are computed for the to be inserted object. The object is then placed in the bucket which contains fewer objects. If the buckets are equal in size, the default location is the h1(x) value. Search: Effective searches are done by looking in both buckets (the bucket locations to which h1(x) and h2(x) mapped) for the desired value.
Өнер көрсету
Барлық хэш-кестелердегідей, өнімділік ең үлкен бөшкеге (bucket) байланысты. Мәндер мен қолданылатын хэш-функцияларға байланысты бөшкелердің көлемі үлкен болуы мүмкін болғанымен, мұндай жағдай сирек кездеседі. Екі хэш-функция болғандықтан, кез келген мән үшін екі мүмкін орын бар, бұл үлкен бөшкелердің пайда болу ықтималдығын одан да азайтады. 2 таңдаулы хэштеуді пайдаланған кезде күтілетін бөшке мөлшері: θ(log(log(n))). Бұл жетістік "Екі таңдаудың күші" деп аталатын кездейсоқ ұғымға байланысты. Екі хэш-функцияны қолдану, бір хэш-функциядан айтарлықтай артықшылықтар береді. Екіден астам хэш-функция қолданылса, жақсарту шамалы (және күтілетін рет статистикасына ешқандай өзгеріс енгізілмейді): "Қосымша хэш-функциялар максимумды тек тұрақты фактормен төмендетеді". Кейбір мамандар кейбір процессорлардың кэш-жадында екі жақты қисайған ассоциативтік кэш деп аталатын 2 таңдаулы хэштеудің бір түрін ұсынады. 2 сол жақты хэштеу – бірдей өлшемдегі n/2 екі хэш-кестесін пайдалану және кілтті сол жақ хэш-кестесіне орналастыру арқылы теңдікті асимметриялық түрде шешу – 2 таңдаулы хэштеуге қарағанда азырақ қақтығыстарға (collisions) және тиімдірек өнімділікке ие.
As is true with all hash tables, the performance is based on the largest bucket. Although there are instances where bucket sizes happen to be large based on the values and the hash functions used, this is rare. Having two hash functions and, therefore, two possible locations for any one value, makes the possibility of large buckets even more unlikely to happen. The expected bucket size while using 2 choice hashing is: θ(log(log(n))). This improvement is due to the randomized concept known as The Power of Two Choices. Using two hash functions offers substantial benefits over a single hash function. There is little improvement (and no change to the expected order statistics) if more than two hash functions are used: "Additional hash functions only decrease the maximum by a constant factor." Some people recommend a type of 2 choice hashing called two way skewed associative cache in some CPU caches. 2 left hashing—using two hash tables of equal size n/2, and asymmetrically resolving ties by putting the key in the left hash table—has fewer collisions and therefore better performance than 2 choice hashing with one large hash table of size n.