Isang Kuwento ng Dalawang Iterators: Competitive Modification Strategies sa Java

Ang may-akda ng tala ay si Grzegorz Mirek, isang software developer mula sa Krakow (Poland). Nagsimula siyang umunlad sa Java mga 6 na taon na ang nakalilipas, habang nasa unibersidad pa, at mula noon ay walang sawang niyang pinapakintab ang kanyang mga kasanayan sa larangang ito. Siya ay partikular na interesado sa pagganap at pag-optimize ng JVM, na siyang pangunahing isinusulat niya sa kanyang blog . Ang ilan sa mga pinakasikat na tanong sa panayam sa Java ay kinabibilangan ng: Ano ang pagkakaiba sa pagitan ng fail-fast at fail-safe iterator? Ang pinaka-pinasimpleng sagot dito ay: Ang isang fail-fast iterator ay nagtatapon ng isang ConcurrentModificationException kung ang koleksyon ay nagbabago sa panahon ng pag-ulit, ngunit ang isang fail-safe na iterator ay hindi. Bagama't mukhang makabuluhan ito, nananatiling hindi malinaw kung ano ang ibig sabihin ng tagapanayam sa fail-safe? Ang Mga Pagtutukoy ng Wika ng Java ay hindi tumutukoy sa terminong ito kaugnay ng mga iterator. Gayunpaman, mayroong apat na mapagkumpitensyang diskarte sa pagbabago.

Competitive na pagbabago

Una, tukuyin natin kung ano ang mapagkumpitensya (o parallel) na pagbabago. Sabihin nating mayroon tayong koleksyon at kapag aktibo ang iterator, may mga pagbabagong nagaganap na hindi nagmumula sa iterator na ito. Sa kasong ito, nakakakuha kami ng mapagkumpitensyang pagbabago. Bigyan kita ng isang simpleng halimbawa: sabihin nating mayroon tayong ilang mga thread. Ang unang thread ay umuulit, at ang pangalawang thread ay naglalagay o nag-aalis ng mga elemento mula sa parehong koleksyon. Gayunpaman, makakakuha tayo ng ConcurrentModificationException kapag tumatakbo sa isang single-threaded na kapaligiran:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Fail-fast

Ang fragment ng code sa itaas ay isang halimbawa ng isang fail-fast iterator. Tulad ng nakikita mo, ang isang ConcurrentModificationException ay itinapon kapag sinusubukang kunin ang pangalawang elemento mula sa iterator . Paano malalaman ng isang iterator na ang koleksyon ay nabago mula noong ito ay nilikha? Halimbawa, maaaring may tatak ng petsa/oras ang koleksyon, sabihin lastModified . Kapag gumagawa ng iterator, dapat mong kopyahin ang field na ito at iimbak ito sa isang iterator object. Pagkatapos, sa tuwing tatawagin mo ang next() method , ihahambing mo lang ang lastModified value mula sa koleksyon sa kopya mula sa iterator. Ang isang katulad na diskarte ay ginagamit, halimbawa, sa pagpapatupad ng klase ng ArrayList . Mayroon itong instance variable modCount na nag-iimbak ng ilang beses na binago ang listahan:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

Mahalagang tandaan na ang mga fail-fast iterator ay gumagana sa isang best-of-breed na batayan, ibig sabihin ay walang garantiya na ang isang ConcurrentModificationException ay itatapon sa kaganapan ng isang kasabay na pagbabago. Kaya't hindi ka dapat umasa sa kanila - sa halip, dapat itong gamitin upang makakita ng mga error. Karamihan sa mga hindi kasabay na mga koleksyon ay nagbibigay ng mga hindi-mabilis na iterator.

Mahinang Consistency

Karamihan sa mga sabay-sabay na koleksyon sa java.util.concurrent package (tulad ng ConcurrentHashMap at karamihan sa Queue ) ay nagbibigay ng mahinang pare-parehong iterator. Ang kahulugan ng terminong ito ay napakahusay na ipinaliwanag sa dokumentasyon :

• Maaari silang maiproseso nang sabay-sabay sa iba pang mga operasyon
• Hindi sila kailanman magtapon ng ConcurrentModificationException
• Ang mga ito ay ginagarantiyahan na tumawid sa mga umiiral na elemento sa oras na ang iterator ay ginawa nang eksaktong isang beses, at maaari (ngunit hindi kinakailangan na) ipakita ang mga kasunod na pagbabago.

Snapshot

Sa diskarteng ito, ang iterator ay nauugnay sa estado ng koleksyon sa oras ng paglikha nito - ito ay isang snapshot ng koleksyon. Ang anumang mga pagbabagong ginawa sa orihinal na koleksyon ay nagreresulta sa paglikha ng isang bagong bersyon ng pinagbabatayan na istraktura ng data. Ito ay nag-iiwan sa aming snapshot na hindi nagbabago, kaya hindi ito nagpapakita ng mga pagbabago sa koleksyon na naganap pagkatapos magawa ang iterator. Ito ang magandang lumang copy-on-write (COW) technique . Ito ay ganap na malulutas ang problema ng kasabay na mga pagbabago, kaya ang isang ConcurrentModificationException ay hindi nabuo sa diskarteng ito. Bukod pa rito, hindi sinusuportahan ng mga iterator ang mga pagpapatakbo na nagbabago ng mga elemento. Ang mga koleksyon ng copy-on-write ay malamang na masyadong mahal upang gamitin, ngunit makatuwirang gamitin ang mga ito kung ang mga pagbabago ay nangyayari nang hindi gaanong madalas kaysa sa mga pag-ulit ng mga traversal. Ang mga halimbawa ay ang mga klase ng CopyOnWriteArrayList at CopyOnWriteArraySet .

Hindi natukoy na pag-uugali

Maaari kang makatagpo ng hindi natukoy na gawi sa mga legacy na uri ng koleksyon gaya ng Vector at Hashtable . Parehong may mga karaniwang fail-fast iterator, ngunit bilang karagdagan, pinapayagan nila ang paggamit ng mga pagpapatupad ng Enumeration interface , at hindi nila alam kung paano kumilos sa kaso ng kasabay na pagbabago. Maaari kang makatagpo ng ilang elemento na paulit-ulit o nawawala, o kahit ilang kakaibang eksepsiyon. Mas mabuting huwag makipaglaro sa kanila!