Implementarea „IndexedSet”, „MapSet” sau „SetMap” în Java (Programare, Java, Colecții, Guava)

Piotr Findeisen a intrebat.

Sunt în căutarea unei Set implementare în Java care să ofere o căutare bazată pe proprietățile elementelor. Gândindu-mă în termeni Guava, aceasta ar putea fi construită folosind un Function<Element, SearchKey> (care se așteaptă să fie unic pentru toate elementele setului) și furnizarea unei metode find(SearchKey key) care returnează un Element pentru care funcția ar returna key.

Evident presupuneri evidente care ar trebui să fie îndeplinite:

  • Rezultatul lui function(element) este constant pe toată durata de viață a element în set.
  • funcția dă rezultate unice pentru toate elementele setului

Motivul:
Uneori este nevoie de Set<Element> iar tipul de câmp nu poate fi schimbat în Map<SearchKey, Element> (cum ar fi în cazul entităților JPA sau în cazul unui cod de la o a patra parte). Cu toate acestea, la construirea unui astfel de obiect se poate folosi în siguranță propriul obiect Set cu Map-capacități similare.

Alternative:

Am găsit deja câteva alternative, dar niciuna dintre ele nu pare perfectă

  • să nu aibă Map-capacități similare – utilizarea căutării liniare pentru find(SearchKey) implementare (funcționează cu orice Set implementare:)
  • utilizarea TreeSet cu Comparator compararea SearchKeys – un pic ca un hack, mai ales că aceasta nu mai respectă egalitatea elementelor
    metoda „find” se numește ceiling și necesită să construiți artificial Element în scopul căutării (uogh…)
  • „set de echivalență” (http://code.google.com/p/guava-libraries/issues/detail?id=576) – dar acest lucru nu este implementat și nu pare să fie implementat și nici nu pare că va fi

(Dacă doriți să răspundeți că nu mai cunoașteți alte alternative – economisiți-vă timpul și nu o faceți. Este un lucru pe care îl știu deja, nu voi putea accepta răspunsul dumneavoastră).

Comentarii

  • Aveți neapărat nevoie să aveți un singur obiect care să servească ambele roluri, sau ați putea avea setul și apoi să-l indexați separat, de exemplu, cu ajutorul unui obiect de tip „set”. Maps.uniqueIndex? Ați putea oricând să vă creați propriul tip care utilizează această idee combinată cu compoziția și delegarea pentru a expune ambele seturi de interfețe dintr-un singur obiect. –  > Por Jon Skeet.
  • Ei bine, partea de motivare spune de ce aveți nevoie în continuare de un Set – dar nu explică de ce nu poți avea ambele. –  > Por Jon Skeet.
  • Vrei să spui că, de exemplu, pentru a subclasa un HashSet și să am un câmp „index” suplimentar care să fie o hartă și să-l gestionez eu însumi? S-ar face, dar tot un pic predispus la erori. –  > Por Piotr Findeisen.
  • Dacă aș putea adăuga un nou tip, aș adăuga doar Map<SearchKey, Element> și aș fi mulțumit de această abordare elegantă. În cazuri cum ar fi fasolea JPA sau un magazin de date de la o terță parte, nu doriți / nu puteți adăuga un nou câmp pe lângă cel existent. Set<Element>, astfel încât această soluție este aplicabilă doar în unele dintre cazuri. –  > Por Piotr Findeisen.
  • De fapt, eu sugeram să se folosească compoziția mai degrabă decât moștenirea. Un nou tip cu două câmpuri (o hartă și un set) în care metodele să fie delegate unuia sau ambelor câmpuri. –  > Por Jon Skeet.
3 răspunsuri
maaartinus

Cred că îmi scapă ceva, altfel este destul de ușor prin ForwardingSet la HashBiMap.keySet(). My implementare trivială se interesează doar de add și addAlltoate celelalte lucruri ar trebui să funcționeze fără niciun efort. Nu există un test unic, aș recomanda să folosiți Guava testlib pentru acest lucru.

Comentarii

  • drăguț. deși nu este o bibliotecă 🙂 –  > Por Piotr Findeisen.
  • Dar aproape…. BiMap face aproape toată treaba. Ați putea încerca să-i convingeți pe cei de la Guava să adauge această funcție, dar sunt destul de sceptic, deoarece nu am auzit niciodată de cineva care să aibă nevoie de ea. Deși sunt sigur, mi-am dorit acest lucru cu ceva timp în urmă. –  > Por maaartinus.
Peter Lawrey

Caut o implementare Set în Java care să ofere o căutare bazată pe proprietățile elementelor.

Pentru asta există o hartă și, da, trebuie să construiți un obiect cheie pentru a reprezenta ceea ce se caută.

Aceasta este cea mai simplă și mai eficientă soluție în Java, așa că, deși este ușor neplăcută, nu mi-aș face griji.

BTW: Seturile sunt de obicei implementate ca un strat peste o hartă în JRE, ceea ce nu este ideal, IMHO.

Comentarii

  • Din păcate, Map nu are un add(Element) metodă care să calculeze cheia pentru apelant. În plus, cred că am spus că sunt limitat la Set<Element> ca tip de date care Map nu implementează AFAIK. În cazurile în care pot schimba tipul de date – sunt de acord cu tine, cu sănătatea mintală și cu Map. –  > Por Piotr Findeisen.
  • Cât de complicat este să scrieți o astfel de metodă sau să subclasați Map pentru a face acest lucru? Dacă derivarea unei chei de unul singur este atât de dificilă, vă sugerez să vă schimbați modelul astfel încât să nu fie așa. De ce vă limitați la Set având în vedere că Collection are exact aceleași metode. –  > Por Peter Lawrey.
  • Aveți dreptate! IndexedCollection ar face la fel de bine. Există vreo implementare existentă? Dacă nu, aș rămâne cu soluția mea de lucru. TreeSet. –  > Por Piotr Findeisen.
  • Nu aș sugera subclasarea claselor de bibliotecă. Se caută probleme la următoarea actualizare majoră a JVM. –  > Por Veronica Cornejo.
  • @VeronicaCornejo Bună observație, deși subclasarea este o opțiune, este puțin probabil să fie cea mai bună opțiune. Este mult mai bine să adăugați acest cod la ceva care înfășoară colecția. –  > Por Peter Lawrey.
Veronica Cornejo

Dacă înțeleg corect întrebarea dumneavoastră, îmi vin în minte 2 alternative:

  1. O variantă a hack-ului tău: o TreeSet cu un comparator care compară YourSearchKey cu YourElement. Puteți fie să păcăliți sistemul de tipuri, fie să creați o interfață comună YourAbstractSearchKey. Singurele dezavantaje sunt că:
    • YourSearchKey obiectele ar putea fi inserate în Set. Collections.checkedSet() ar putea fi de ajutor în acest punct.
    • Rezultatul căutărilor ar trebui, cel mai probabil, să fie transformat în YourElement. Soluție: definiți toate proprietățile în interfața comună. YourAbstractSearchKey și să aibă o implementare YourSearchKey throw UnsupportedOperationException pentru cele suplimentare.
  2. Similar, dar cu o hartă. Nu este nevoie să adăugați proprietăți suplimentare la YourAbstractSearchKey pentru că harta ar fi Map<YourAbstractSearchKey,YourElement>. Pentru a adăuga elemente ar trebui să scrieți myMap.put(newElement,newElement).

Comentarii

  • Woow. Nu m-am gândit la acest lucru. Acest lucru este foarte mult în conformitate cu abordarea mea generală hackish 🙂 –  > Por Piotr Findeisen.
  • (Harta nu va face – dacă ar face-o, aș face doar Map<SearchKey, Element>) –  > Por Piotr Findeisen.
  • @PiotrFindeisen Da, cam asta am spus și eu RE Maps. –  > Por Veronica Cornejo.