Динамикалық мінсіз хэштеу - Dynamic perfect hashing - Wikipedia

Жылы Информатика, динамикалық мінсіз хэштеу шешуге арналған бағдарламалау әдісі болып табылады қақтығыстар ішінде хэш-кесте мәліметтер құрылымы.[1][2][3]Хэш-кестедегіден гөрі көп жадты қажет етеді,[дәйексөз қажет ] бұл әдіс элементтердің үлкен жиынтығында жылдам сұраулар, кірістіру және жою қажет болған жағдайда пайдалы.

Егжей

Статикалық жағдай

FKS схемасы

Оңтайлы проблема статикалық хэштеу тұңғыш рет Фредман, Комлос және Семереди шешті.[4] 1984 жылғы мақаласында,[1] олар хэш-кестенің әр шелегі екінші деңгейлі хэш-кестеге сәйкес келетін екі деңгейлі хэш кестесінің схемасын егжей-тегжейлі сипаттайды. Кілттер екі рет хэштелген - бірінші хэш мәні бірінші деңгейдегі хэш кестесінде белгілі бір шелекке сәйкес келеді; екінші хэш мәні сол жазбаның екінші деңгейдегі хэш кестесіндегі орнын береді. Екінші деңгей кестесі қақтығыссыз болуға кепілдік береді (яғни.) тамаша хэштеу ) құрылыс кезінде. Демек, іздеу құны кепілдендірілген O (1) ең нашар жағдайда.[2]

Статикалық жағдайда, бізге әрқайсысы бірегей кілті бар x жазбалары бар жиынтықты мерзімінен бұрын береді.Фредман, Комлос және Семереди өлшемі бар бірінші деңгейдегі хэш кестені таңдайды. s = 2 (x-1) шелектер.[2]

Салу үшін, х жазбалар бөлінеді с жоғары деңгейдегі хэштеу функциясы бойынша шелектер, қайда s = 2 (x-1). Содан кейін әрбір шелек үшін к жазбалар, екінші деңгей кестесі бөлінеді к2 слоттар және оның хэш функциясы а-дан кездейсоқ таңдалады әмбебап хэш функциясы соқтығыспайтын етіп орнатыңыз (яғни а тамаша хэш функциясы ) және хэш-кестемен қатар сақталады. Егер кездейсоқ таңдалған хэш функциясы соқтығысуымен кесте құрса, жаңа хэш функциясы кездейсоқ түрде соқтығыспайтын кестеге кепілдік берілгенге дейін таңдалады. Соңында, соқтығысусыз хэшпен к жазбалар екінші деңгей кестесіне қосылды.

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

Бірінші деңгейдегі хэш функциясы арнайы таңдалған, сондықтан x бірегей кілт мәндерінің нақты жиынтығы үшін барлық екінші деңгейдегі хэш кестелерінде пайдаланылатын T кеңістігі O (n) кеңістік, және нақтырақ T әмбебап хэштеу хэш-функциялардың отбасы, олардың кемінде жартысы осындай қасиетке ие.[2]

Динамикалық корпус

Dietzfelbinger және басқалар. динамикалық сөздік алгоритмін ұсыныңыз, егер сөздікке біртіндеп n элемент жиынтығын қосқанда, мүшелік сұраулары әрдайым тұрақты уақытта жұмыс істейді, сондықтан O (1) ең нашар уақытта, жалпы сақтау орны O (n) (сызықтық) және O (1) амортизацияланған кірісті енгізу және жою уақыты (амортизацияланған тұрақты уақыт ).

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

Сонымен қатар, динамикалық жағдайда жоғарғы деңгей кестесінің немесе кез-келген ішкі кестенің максималды өлшемдерін білу мүмкін емес. Күтілетін O-ны сақтаудың бір әдісі (n) кестенің кеңістігі - кірістіру мен жоюдың жеткілікті саны болған кезде толық қайта құруды сұрайды. Dietzfelbinger және басқалардың нәтижелері бойынша,[2] егер кірістірудің немесе жоюдың жалпы саны соңғы құрылыс кезіндегі элементтердің санынан асып кетсе, кірістіру мен жоюдың амортизацияланған құны O (1) болып қалады, қайта қалпына келтіруді ескере отырып.

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

Псевдокодты енгізу

Орналастыру

функциясы Орналастыру (х) болып табылады    j : = сағ (х)    егер (h позициясыj(х) subtable Тj қамтиды х (жойылмаған)) қайту (х ішінде S)    егер аяқталса    басқа         қайту (х жоқ S)    соңы басқаСоңы

Кірістіру

Жаңа жазба енгізу кезінде х кезінде j, ғаламдық операциялар есептегіші, санау, ұлғайтылады.

Егер х бар j, бірақ жойылған деп белгіленеді, содан кейін белгі жойылады.

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

функциясы Кірістіру (х) болып табылады    санау = санау + 1;    егер (санау > МFullRehash (х);    егер аяқталса    басқа        j = сағ (х);        егер (Позиция сағj(x) кестенің Тj қамтиды х)            егер (х жойылды деп белгіленді) жою маркерін алып тастаңыз; егер аяқталса        егер аяқталса        басқа            бj = бj + 1;            егер (бj <= мj)                 егер позиция hj(х) of Тj бос дүкен х h жағдайындаj(х) of Тj;                егер аяқталса                басқа                    Барлық белгісіз элементтерін қойыңыз Тj тізімде Lj; Қосыңыз х тізімге қосу Lj;                    бj = ұзындығы Lj;                    қайталау                         сағj = кездейсоқ таңдалған функция Hsj;                    дейін сағj элементтеріне инъекциялық болып табылады Lj;                    үшін барлық ж тізімде Lj                        дүкен ж h жағдайындаj(ж) of Тj;                    үшін аяқтау                соңы басқа            егер аяқталса            басқа                мj = 2 * максимум {1, мj};                сj = 2 * мj * (мj - 1);                егер барлығының жиынтығыj ≤ 32 * М2 / с(М) + 4 * М                     Бөлу сj үшін ұяшықтар Тj; Барлық белгісіз элементтерін қойыңыз Тj тізімде Lj; Қосыңыз х тізімге қосу Lj;                    бj = ұзындығы Lj;                    қайталау                         сағj = кездейсоқ таңдалған функция Hsj;                    дейін сағj элементтеріне инъекциялық болып табылады Lj;                    үшін барлық ж тізімде Lj                        дүкен ж h жағдайындаj(ж) of Тj;                    үшін аяқтау                егер аяқталса                басқа                    FullRehash (х);                соңы басқа            соңы басқа        соңы басқа    соңы басқаСоңы

Жою

Жою х жай жалаушалар х ретінде жойылмайды және өсімсіз санау. Екі кірістіру және жою жағдайында, егер санау табалдырыққа жетеді М бүкіл кесте қайта құрылды, қайда М - бұл жаңа басындағы S мөлшерінің тұрақты еселігі фаза. Мұнда фаза толық қайта құру арасындағы уақытты білдіреді. Назар аударыңыз, мұнда -1 «Жою (х) «бұл барлық мүмкін элементтер жиынтығында жоқ элементтің көрінісі U.

функциясы Жою(х) болып табылады    санау = санау + 1;    j = сағ (х);    егер позиция hj(х) subtable Tj қамтиды х        белгі х жойылған ретінде; егер аяқталса    басқа         қайту (x S мүшесі емес); соңы басқа    егер (санау >= М) FullRehash (-1); егер аяқталсаСоңы

Толық қалпына келтіру

Кестесін толық қалпына келтіру S алдымен жойылған деп белгіленген барлық элементтерді алып тастап, содан кейін келесі шекті мәнді орнатудан басталады М өлшемінің кейбір тұрақты еселігіне дейін S. Бөлінетін хэш функциясы S ішіне с(М) ішкі жиын, мұнда ішкі жиынның мөлшері j болып табылады сj, бірнеше рет кездейсоқ таңдалады:

Ақыр соңында, әр субстата үшін Тj хэш функциясы сағj бірнеше рет кездейсоқ таңдалады Hsj дейін сағj элементтеріне инъекциялық болып табылады Тj. Кестені толығымен қалпына келтіруге күтілетін уақыт S өлшемімен n бұл O (n).[2]

функциясы FullRehash (х) болып табылады    Барлық белгісіз элементтерін қойыңыз Т тізімде L;    егер (х ішінде U) қосыңыз х дейін L;    егер аяқталса    санау = тізім ұзындығы L;    М = (1 + c) * максимум {санау, 4};    қайталау         h = кездейсоқ таңдалған функция Hс (Ұ);        үшін барлық j < с(М) тізімді құрайды Lj сағ үшін (х) = j;            бj = ұзындығы Lj;             мj = 2 * бj;             сj = 2 * мj * (мj - 1);        үшін аяқтау    дейін барлығының жиынтығыj ≤ 32 * М2 / с(М) + 4 * М    үшін барлық j < с(М) Кеңістікті бөлу сj subtable үшін Тj;        қайталау             сағj = кездейсоқ таңдалған функция Hsj;        дейін сағj тізім элементтеріне инъекциялық болып табылады Lj;    үшін аяқтау    үшін барлық х тізімде Lj         дүкен х h жағдайындаj(х) of Тj;    үшін аяқтауСоңы

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

Пайдаланылған әдебиеттер

  1. ^ а б c Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Сирек үстелді 0 (1) ең нашар жағдайға қол жеткізу уақытымен сақтау. J. ACM 31, 3 (маусым. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
  2. ^ а б c г. e f ж сағ Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.«Динамикалық мінсіз хэш: жоғарғы және төменгі шекаралар» Мұрағатталды 2016-03-04 Wayback Machine.SIAM J. Comput. 23, 4 (1994 ж. Тамыз), 738-761.http://portal.acm.org/citation.cfm?id=182370дои:10.1137 / S0097539791194094
  3. ^ Эрик Демейн, Джефф Линд.6.897: Деректердің кеңейтілген құрылымдары.MIT информатика және жасанды интеллект зертханасы. 2003 жылдың көктемі.
  4. ^ Жап, Чи. «FKS схемасына арналған әмбебап құрылыс». Нью-Йорк университеті. Нью-Йорк университеті. Алынған 15 ақпан 2015.[тұрақты өлі сілтеме ]