Ipinapakilala ang koleksyon ng TreeMap

Isang araw sa unibersidad, kailangan kong magsulat ng code para pagbukud-bukurin ang mga apelyido ng aking mga kaklase, na nagsilbing susi sa kanilang personal na data, sa pataas na pagkakasunud-sunod. Gumugol ako ng maraming oras dito. Ngunit kung alam ko ang tungkol sa klase ng TreeMap noon, mas mabilis kong natapos ang gawain.

Ano ang TreeMap ? Ito ay isang istraktura ng data na parang diksyunaryo na nag-iimbak ng mga elemento bilang mga pares ng key-value, na pinagbubukod-bukod ang mga ito ayon sa key.

Saan at paano ito magagamit? Well, ito ay magiging perpekto para sa parehong assignment na may mga apelyido ng aking mga kaklase. Kung kailangan kong mag-imbak ng mga halaga sa pataas na pagkakasunud-sunod, sa halip na magsulat ng sarili kong algorithm sa pag-uuri, ang kailangan ko lang gawin ay lumikha ng TreeMap at ilagay ang mga halaga dito.

Nag-uuri ito ng mga uri tulad ng Integer at String sa pataas na pagkakasunud-sunod. Ngunit kung gusto mong ilagay ang iyong sariling custom na uri sa isang TreeMap , kailangan ng iyong klase na ipatupad ang Comparable interface, upang maipatupad nito ang compareTo() method, na nagpapahiwatig kung paano pag-uri-uriin ang mga pagkakataon ng iyong klase.

public class Person implements Comparable<Person> {

    private String firstName;
    private String lastName;

    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

  …

    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }

    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

I-override natin ang compareTo() na paraan upang pag-uri-uriin nito ang mga halaga ayon sa unang pangalan sa reverse alphabetical order:

TreeMap map = new TreeMap<Person, String>();

map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Ang mga halaga ay maiimbak sa sumusunod na pagkakasunud-sunod:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

Ipinapatupad ng klase ng TreeMap ang interface ng NavigableMap , na nagpapalawak naman ng interface ng SortedMap . Nagbibigay-daan ito sa klase ng TreeMap na gumamit ng mga puno upang mag-imbak ng mga halaga sa pinagsunod-sunod na pagkakasunud-sunod.

Upang ilagay iyon sa mga simpleng termino, ang pulang-itim na puno ay isang istraktura ng data na nag-iimbak ng mga halaga sa kanang subtree kung mas malaki ang mga ito kaysa sa ugat, at sa kaliwang subtree kung mas mababa ang mga ito. Ang pagpapatupad na ito ay maaaring maghanap ng mga halaga sa istraktura nang napakabilis.

Ang isang pulang-itim na puno ay nagbabalanse sa sarili, kaya binabago nito ang istraktura nito habang ipinapasok ang bawat bagong halaga. Ang unang idinagdag na halaga ay itinuturing na ugat, ngunit ang isa pang halaga ay maaaring maging ugat sa panahon ng proseso ng pagbabalanse.

Well, ngayon alam mo na kung ano ang TreeMap at kung paano ito gumagana.

Tandaan na ang TreeMap ay maaari lamang mag-imbak ng mga bagay na ang klase ay nagpapatupad ng Comparable interface at na-override ang compareTo() na paraan.

Ngunit paano kung gumagamit tayo ng mga third-party na klase na na-load mula sa iba't ibang mga aklatan at hindi maipapatupad ang Comparable sa kanila? May solusyon para dito: sumulat ng sarili mong Comparator .

Ang Comparator ay isang interface na mayroong compare() na paraan. Magagamit natin ito upang ihambing ang mga bagay at iimbak ang mga ito sa isang TreeMap .

Comparator<Person> comparator = new Comparator<Person>() {

    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};


TreeMap map = new TreeMap<Person, String>(comparator);

Sa halimbawang ito, gumawa kami ng custom na Comparator at nagpasa ng TreeMap sa klase.

Simula sa Java 8, maisusulat natin ito gamit ang lambda expression:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

Sa madaling salita, upang mag-imbak ng mga halaga sa isang TreeMap , kailangan mong tukuyin kung paano ayusin ang mga ito. Mayroong dalawang paraan para gawin ito: ipatupad ang Comparable o ipatupad ang sarili mong Comparator .

Ngunit paano kung kailangan nating ilagay ang null sa isang TreeMap bilang isang susi? Hinahayaan ka ng HashMap na gawin ito. Oo, ngunit paano ito pinangangasiwaan ng TreeMap ?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Ang pagpapatakbo ng code na ito ay nagbibigay sa amin ng isang error:

Ang problema ay ang panloob na klase ng TreeMap ay naghahambing ng mga halaga gamit ang compareTo() na paraan. Maaari mong tiyak na pumasa sa isang null na halaga sa at ang code ay mag-compile. Ngunit sa runtime makakakuha ka ng isang error, dahil ang pamamaraan ay tatawagin sa isang null na halaga, na nagiging sanhi ng isang NullPointerException na ihagis.

Paghahambing ng HashMap at TreeMap

Hindi tulad ng TreeMap , hinahayaan ka ng HashMap na mag-imbak ng null bilang isang susi. Ang istraktura ay may isang tiyak na lugar para sa lahat ng mga null key. Nagagawa ng HashMap na mag-imbak ng mga null key dahil tinutukoy nito kung saan sila pupunta batay sa kanilang hash value, at ang pagkalkula ng hash value ay hindi nangangailangan ng mga paghahambing. Kaya lahat ng mga null key ay may kanilang lugar.

Nandiyan ka na — ngayon alam mo na kung ano ang gagamitin kapag kailangan mong mag-imbak ng mga halaga sa pinagsunod-sunod na pagkakasunud-sunod, at kung paano itakda ang mga panuntunan para sa pag-uuri.