Patlisiso ea binary e bapisoa joang le mekhoa e meng ea ho batla?
Context:Li-array tse hlophisitsoeng tse nang le patlo ea binary ke tharollo e sa sebetseng hantle ha ho kenngoa le ho hlakola ts'ebetso ho kenngoa le ho khutlisoa, ho nka  (n) nako bakeng sa ketso e 'ngoe le e 'ngoe e joalo. Ho phaella moo, lihlopha tse hlophisitsoeng li ka thatafatsa tšebeliso ea mohopolo haholo-holo ha likarolo li atisa ho kenngoa ka har'a lihlopha. Ho na le mehaho e meng ea boitsebiso e tšehetsang ho kenngoa le ho tlosoa ka tsela e atlehang haholoanyane. Ho batlisisa ka binary ho ka sebelisoa ho etsa ho bapisa hantle le ho beha setho (ho khetholla hore na boleng ba sepheo bo ka har'a pokello ea litekanyetso). Ho na le mehaho ea boitsebiso e tšehetsang ho bapisa ka potlako le ho ba setho sa sehlopha. Leha ho le joalo, ho fapana le mekhoa e meng e mengata ea ho batla, ho batla ka binary ho ka sebelisoa bakeng sa ho bapisa hantle, hangata ho etsa lipapali tse joalo ka O ((log n) nako ho sa tsotelehe mofuta kapa sebopeho sa boleng ka bobona. Ho phaella moo, ho na le mesebetsi e meng, e kang ho fumana karolo e nyenyane le e khōlō ka ho fetisisa, e ka etsoang ka katleho lethathamong le hlophisitsoeng.  Ho batla ka tsela e otlolohileng:  Ho batla ka tsela e otlolohileng ke mokhoa o bonolo oa ho batla o hlahlobang rekoto e 'ngoe le e 'ngoe ho fihlela e fumana boleng boo e bo batlang. Ho batla ka tsela e otlolohileng ho ka etsoa lethathamong le hokahaneng, le lumellang ho kenya le ho hlakola ka potlako ho feta lethathamo. Ho batla ka binary ho potlakile ho feta ho batla ka linear bakeng sa lihlopha tse hlophisitsoeng ntle le haeba lihlopha li le khutšoanyane, le hoja lihlopha li hloka ho hlophisoa pele. Li-algorithms tsohle tsa ho hlophisa tse thehiloeng ho bapisa likarolo, tse kang ho hlophisa kapele le ho kopanya, li hloka bonyane O ((nlog n) ho bapisoa maemong a mabe ka ho fetisisa. Ho fapana le ho batla ka tsela e otlolohileng, ho batla ka tsela ea binary ho ka sebelisoa bakeng sa ho bapisa ka tsela e atlehang. Ho na le mesebetsi e kang ho fumana karolo e nyenyane le e khōlō ka ho fetisisa e ka etsoang ka katleho lethathamong le hlophisitsoeng empa eseng lethathamong le sa hlophisitsoeng.  Lifate:  Lifate tsa patlo ea binary li batloa ho sebelisoa algorithm e ts'oanang le patlo ea binary. Sefate sa ho batla ka binary ke sebopeho sa data sa sefate sa binary se sebetsang ho latela molao-motheo oa ho batla ka binary. Lirekoto tsa sefate li hlophisitsoe ka tatellano e hlophisitsoeng,'me rekoto e' ngoe le e 'ngoe sefateng e ka batloa ho sebelisoa algorithm e ts'oanang le patlo ea binary, ho nka nako e tloaelehileng ea logarithmic. Ho kenya le ho hlakola ho boetse ho hloka nako ea karolelano ea logarithmic lifateng tsa ho batla tsa binary. Sena se ka ba ka potlako ho feta linear nako kenyelletswa le ho hlakola la lihlooho tse hlophisitsoeng,'me lifate binary lula le matla a ho phetha mesebetsi eohle khoneha ka la lihlooho tse hlophisitsoeng, ho akarelletsa le mefuta e fapaneng le e batlang e le lipotso.  Leha ho le joalo, patlo ea binary hangata e sebetsa hantle bakeng sa ho batla ha lifate tsa patlo ea binary li kanna tsa se leka-lekane hantle, ho fella ka ts'ebetso e mpe hanyane ho feta patlo ea binary. Sena se sebetsa esita le ho lifate tse leka-lekaneng tsa ho batla tsa binary, lifate tsa ho batla tsa binary tse leka-lekanang li-node tsa tsona, hobane ke ka seoelo li hlahisang sefate se nang le maemo a fokolang ka ho fetisisa. Ntle le bakeng sa ho leka-lekana binary batla lifate, sefate ka 'na ba ka ho teba unbalanced le tse seng kae ka hare nodes le bana ba babeli, e leng se fellang ka karolelano le mpe ka ho fetisisa-boemo ba batla nako atamela n papiso.[e] Lifate tsa patlo ea binary li nka sebaka se seholo ho feta li-array tse hlophisitsoeng.  Lifate tsa ho batla tsa binary li ikemiselitse ho batla ka potlako mohopolong o kantle o bolokiloeng ka har'a li-disk tse thata, kaha lifate tsa ho batla tsa binary li ka hlophisoa hantle lits'ebetsong tsa faele. Sefate sa B se akaretsa mokhoa ona oa ho hlophisa lifate. Hangata lifate tsa B li sebelisoa ho hlophisa polokelo ea nako e telele joalo ka marang-rang le litsamaiso tsa lifaele.  Hashing: Bakeng sa ho kenya ts'ebetsong mekhahlelo e kopanetsoeng, litafole tsa hash, sebopeho sa data se bapisang linotlolo le lirekoto se sebelisa ts'ebetso ea hash, hangata se potlakile ho feta patlo ea binary ho lethathamo le hlophisitsoeng la lirekoto. Boholo ba ts'ebetsong ea tafole ea hash bo hloka feela nako e sa fetoheng e sa fetoheng ka karolelano. Leha ho le joalo, hashing ha e na thuso bakeng sa lipapali tse batlang li lekana, joalo ka ho bala senotlolo se latelang se senyenyane ka ho fetesisa, se latelang se seholo ka ho fetesisa, le se haufi, kaha tlhaiso-leseling e fanoeng patlisisong e sa atleheng ke hore sepheo ha se teng rekotong efe kapa efe. Ho batlisisa ka binary ho molemo bakeng sa ho bapisa lintho tse joalo, ho li etsa ka nako ea logarithm. Patlisiso ea li-binary e boetse e tšehetsa ho bapisa hoo e batlang e le ntho e le 'ngoe. Mesebetsi e meng, e kang ho fumana ntho e nyenyane le e khōlō ka ho fetisisa, e ka etsoa ka katleho mekolokong e hlophisitsoeng empa eseng litafoleng tsa hash.  Ho beha li-algorithms tsa ho ba setho: Bothata bo amanang le ho batla ke ho ba setho sa sehlopha. Algorithm leha e le efe e etsang ho batla, joaloka ho batla ha binary, e ka boela ea sebelisoa bakeng sa ho ba setho sa sehlopha. Ho na le li-algorithm tse ling tse loketseng ho ba litho tsa sehlopha. Letoto la li-bit ke lona le bonolo ka ho fetisisa, le leng molemo ha lenane la linotlolo le lekanyelitsoe. E boloka pokello ea li-bit ka mokhoa o kopanetsoeng,'me e' ngoe le e 'ngoe e emela senotlolo se le seng ka har'a lenane la linotlolo. Li-array tsa li-bit li potlakile haholo, li hloka feela O(1) nako. Mofuta oa Judy1 oa Judy o sebetsana le linotlolo tsa 64-bit ka katleho.  Bakeng sa liphetho tse batlang li le haufi, Bloom filters, e leng sebopeho se seng sa data se nang le monyetla se thehiloeng ho hashing, boloka sete ea linotlolo ka ho kenya linotlolo ka ho sebelisa li-bit array le mesebetsi e mengata ea hash. Li-filter tsa Bloom li sebelisa sebaka se seholo ho feta li-array tsa bit maemong a mangata ebile ha li liehe haholo: ka k mesebetsi ea hash, lipotso tsa litho li hloka feela Ke nako. Leha ho le joalo, li-filter tsa Bloom li na le liphello tse fosahetseng.  Mehaho e meng ea data: Ho na le mehaho ya data e ka ntlafatsa ka ho batla binary maemong a mang ka bobeli batla le tshebetso tse ling tse fumanehang bakeng sa mekgahlelo hlophisitsoeng. Ka mohlala, ho batla, ho bapisa hoo e ka bang, le mesebetsi e fumanehang bakeng sa lihlopha tse hlophisitsoeng li ka etsoa ka mokhoa o atlehileng ho feta ho batla ha binary mehahong e khethehileng ea data e kang lifate tsa van Emde Boas, lifate tsa fusion, liteko le lihlopha tsa bit. Mehaho ena e khethehileng ea data hangata e potlakile feela hobane e sebelisa monyetla oa thepa ea linotlolo tse nang le tšobotsi e itseng (hangata linotlolo tse nang le linomoro tse nyane tse felletseng), ka hona e tla nka nako kapa sebaka bakeng sa linotlolo tse se nang tšobotsi eo. Hafeela linotlolo li ka hlophisoa, mesebetsi ena e ka etsoa ka tsela e atlehang ka mehla lenaneng le hlophisitsoeng ho sa tsotelehe linotlolo. Mehaho e meng, e kang Judy arrays, e sebelisa mekhoa e'maloa ho fokotsa sena ha e ntse e boloka katleho le bokhoni ba ho etsa papali e batlang e tšoana.
Li-array tse hlophisitsoeng tse nang le patlo ea binary ke tharollo e sa sebetseng hantle ha ho kenngoa le ho hlakola ts'ebetso ho kenella le ho khutlisoa. Ho phaella moo, lihlopha tse hlophisitsoeng li ka thatafatsa tšebeliso ea mohopolo haholo-holo ha likarolo li atisa ho kenngoa ka har'a lihlopha. Ho batla ka binary ho potlakile ho feta ho batla ka linear bakeng sa lihlopha tse hlophisitsoeng ntle le haeba lihlopha li le khutšoanyane, le hoja lihlopha li hloka ho hlophisoa pele. Ho batla ka binary hangata ho sebetsa hantle haholo ha ho batloa hobane lifate tsa ho batla ka binary li kanna tsa ba le botsitso bo sa phethahalang, ho fella ka ts'ebetso e mpe hanyane ho feta ho batla ka binary. mokhoa oa boitsebiso o kopanyang linotlolo le litlaleho o sebelisa mosebetsi oa hash, ka kakaretso o potlakile ho feta ho batla ka binary lethathamong le hlophisitsoeng la litlaleho.