Біріктірілген хэш кестесінде қақтығыстарды шешу стратегиясы
Coalesced hashing
Хеш-кестедегі түйісуді шешу стратегиясы: біріктірілген хештеу. Жеке тізбектеу мен ашық адрестеудің қосымшасы, жадты үнемдейді. Хеш-функцияны шектеу өте маңызды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Хэш кестесіндегі коллизияны шешу стратегиясы
Hash table collision resolution strategy
Біріктірілген хэштеу, сондай-ақ біріктірілген тізбектеу деп аталатын стратегия, хэш кестесіндегі коллизияны шешу үшін қолданылатын және бөлек тізбектеу мен ашық адрестеудің аралас түрін құрайтын әдіс.
Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing.
Жеке тізбектелген хэш-кесте
Жеке тізбектелген хэш-кестеде бірдей мекен-жайға хэштелген элементтер сол мекен-жайдағы тізімге (немесе "тізбекке") орналастырылады. Бұл техника көп жадты босқа жұмсауға алып келуі мүмкін, себебі кесте жақсы өнімділік көрсететін жүктеме коэффициентін сақтау үшін (әдетте күтілетін элементтер санынан екі есе көп) жеткілікті үлкен болуы керек, сондай-ақ тізбектегі алғашқы элементтен басқа барлық элементтер үшін қосымша жад қолданылуы тиіс (егер тізімнің басшылары қолданылмаса, онда қосымша жад тізбектегі барлық элементтер үшін қолданылуы тиіс).
In a separate chaining hash table, items that hash to the same address are placed on a list (or "chain") at that address. This technique can result in a great deal of wasted memory because the table itself must be large enough to maintain a load factor that performs well (typically twice the expected number of items), and extra memory must be used for all but the first item in a chain (unless list headers are used, in which case extra memory must be used for all items in a chain).
Төменгі бөлме
Коалесценцияның әсерін азайту үшін маңызды оңтайландыру – хэш-функцияның адрестік кеңістігін кестедегі тек бір бөлігімен шектеу. Мысалы, егер кесте M өлшемімен, 0-ден M-1 дейін нөмірленген ұяларымен болса, хэш-функция адрестерді кестедегі алғашқы N ұясына ғана тағайындайтындай етіп, адрестік кеңістікті шектеуге болады. Қалған M-N ұялары, "жер төлесі" деп аталатын бөлік, енгізу кезінде қақтылысқа түсетін элементтерді сақтау үшін ғана пайдаланылады. Жер төлесі толып біткенше, бірігу (коалесценция) жүрмейді. N-нің M-ге қатысты оптималды таңдауы кестедегі жүктеме коэффициентіне (немесе толу деңгейіне) байланысты. Мұқият талдау көрсеткендей, N = 0,86 × M мәні көптеген жүктеме коэффициенттері үшін оңтайлы нәтижеге жақын.
An important optimization, to reduce the effect of coalescing, is to restrict the address space of the hash function to only a subset of the table. For example, if the table has size M with buckets numbered from 0 to M − 1, we can restrict the address space so that the hash function only assigns addresses to the first N locations in the table. The remaining M − N buckets, called the cellar, are used exclusively for storing items that collide during insertion. No coalescing can occur until the cellar is exhausted. The optimal choice of N relative to M depends upon the load factor (or fullness) of the table. A careful analysis shows that the value N = 0.86 × M yields near optimum performance for most load factors.
Нұсқалар
Іске қосу үшін іздеу уақытын жақсартатын басқа да нұсқалар бар. Жою алгоритмдері кездейсоқтықты сақтайды, сондықтан орташа іздеу уақытын талдау жоюдан кейін де қолданылады. Біріктірілген тізбектеу бастапқы және екіншілік кластерлеудің әсерінен қашады, нәтижесінде жеке тізбектеуге арналған тиімді іздеу алгоритмін пайдалана алады. Тізбектер қысқа болса, бұл стратегия өте тиімді және жад тұрғысынан ықшам болуы мүмкін. Ашық адрестеу сияқты, біріктірілген хэш-кестеден деректерді жою қиын және қымбат болуы мүмкін, ал кестенің көлемін өзгерту өте қымбат және оны мүмкіндігінше сирек жасау керек.
Other variants for insertion are also possible that have improved search time. Deletion algorithms have been developed that preserve randomness, and thus the average search time analysis still holds after deletions. Coalesced chaining avoids the effects of primary and secondary clustering, and as a result can take advantage of the efficient search algorithm for separate chaining. If the chains are short, this strategy is very efficient and can be highly condensed, memory wise. As in open addressing, deletion from a coalesced hash table is awkward and potentially expensive, and resizing the table is terribly expensive and should be done rarely, if ever.