Sokongan kontena untuk objek di Java 1.0.2

Herbert Spencer menulis, "Sains adalah pengetahuan yang teratur." Akibatnya adalah aplikasi adalah objek yang tersusun. Mari luangkan sedikit masa untuk beralih ke beberapa aspek Java yang penting untuk mengembangkan aplikasi daripada applet.

Dari mereka yang pernah mendengar tentang Java, majoriti telah belajar tentang bahasa melalui akhbar popular. Pernyataan yang banyak muncul adalah bahawa Java adalah untuk "memprogram aplikasi kecil, atau applet, yang dapat disisipkan di halaman Web." Walaupun betul, definisi ini hanya menyampaikan satu aspek bahasa baru; ia tidak menggambarkan keseluruhan gambarannya. Mungkin Java dapat digambarkan dengan lebih baik sebagai bahasa yang dirancang untuk membina sistem - sistem besar - kepingan mudah alih yang dapat difahami yang dapat digabungkan yang dapat digabungkan, secara keseluruhan atau sebahagian, untuk menghasilkan keseluruhan yang diinginkan.

Di ruangan ini saya akan mula melihat pelbagai alat yang boleh anda gunakan untuk membina di Java. Saya akan menunjukkan bagaimana alat-alat ini dapat digabungkan untuk membuat aplikasi yang lebih besar, dan bagaimana, setelah anda memiliki aplikasi, anda dapat menggabungkan aplikasi ke dalam sistem yang lebih besar lagi - semuanya mungkin kerana di Jawa tidak ada perbezaan antara aplikasi lengkap dan subrutin yang ringkas.

Untuk menyediakan sumber kod sumber untuk ruangan ini dan lajur yang lalu, saya memilih untuk membina jurubahasa ASAS. "Mengapa ASAS?" anda mungkin bertanya, memikirkan tidak ada yang menggunakan ASAS lagi. Ini tidak benar sepenuhnya. BASIC hidup dalam Visual Basic dan dalam bahasa skrip lain. Tetapi yang lebih penting, banyak orang telah terdedah kepadanya dan dapat membuat lompatan konseptual berikut: Jika "aplikasi" diprogramkan dalam BASIC, dan BASIC dapat ditulis di Jawa, maka aplikasi dapat ditulis di Jawa. ASAS hanyalah bahasa yang ditafsirkan; alat yang akan kita bina dapat diubah suai untuk menggunakan sebarang sintaks bahasa, oleh itu konsep inti menjadi fokus artikel ini. Oleh itu, apa yang dimulakan sebagai aplikasi menjadi komponen aplikasi lain - mungkin juga applet.

Kelas dan bekas generik

Membangun kelas generik sangat relevan ketika membuat aplikasi kerana kelas menggunakan kembali memberikan pengaruh yang luar biasa dalam mengurangkan kerumitan dan waktu untuk memasarkan. Dalam applet, nilai kelas generik dikurangkan oleh keperluan memuatkannya melalui rangkaian. Kesan negatif memuat kelas generik melalui rangkaian ditunjukkan oleh Sun's Java Workshop (JWS). JWS menambah versi standard toolkit abstrak (AWT) dengan menggunakan beberapa kelas "bayangan" yang sangat elegan. Kelebihannya ialah applet mudah dikembangkan dan kaya dengan ciri; Kelemahannya ialah memuatkan kelas ini memerlukan banyak masa pada pautan rangkaian yang perlahan. Walaupun keburukan ini akan hilang akhirnya, apa yang kita dapati adalah bahawa perspektif sistem mengenai pengembangan kelas sering diperlukan untuk mencapai penyelesaian terbaik.

Oleh kerana kita mula melihat dengan lebih serius dalam pembangunan aplikasi, kita akan menganggap bahawa kita telah menentukan bahawa kelas generik adalah penyelesaian yang sah.

Java, seperti banyak bahasa umum, menyediakan beberapa alat untuk membuat kelas generik. Keperluan yang berbeza memerlukan penggunaan

alat yang berbeza. Di ruangan ini saya akan menggunakan pengembangan containerkelas sebagai contoh kerana dapat memuat hampir semua alat yang mungkin ingin digunakan pengguna.

Bekas: Definisi

Bagi anda yang belum mengetahui perkara yang berorientasikan objek, wadah adalah kelas yang mengatur objek lain. Bekas biasa adalah pokok binari, barisan, senarai, dan timbunan. Java membekalkan tiga kelas kontena dengan keluaran JDK 1.0.2: java.util.Hashtable, java.util.Stack, dan java.util.Vector.

Kontena mempunyai prinsip penyusun dan antara muka. Tumpukan, misalnya, dapat disusun sebagai "first in, last out" (FILO), dan antara muka mereka boleh didefinisikan mempunyai dua kaedah - push () dan pop () . Bekas sederhana boleh dianggap sebagai kaedah standard menambah dan membuang . Selanjutnya, mereka akan memiliki cara untuk menghitung keseluruhan wadah, untuk memeriksa untuk melihat apakah objek calon sudah ada di dalam wadah dan untuk menguji jumlah elemen yang dipegang oleh kontena.

Kelas kontena Java menunjukkan beberapa masalah dengan kontena, terutama wadah yang dikunci (bekas yang menggunakan kunci untuk mencari objek). Bekas tanpa kunci seperti Stack dan Vector hanya memasukkan objek ke dalam dan menarik objek keluar. Hashtable bekas berkunci menggunakan objek kunci untuk mencari objek data. Agar fungsi kunci berfungsi, objek utama mesti menyokong kaedah HashCode yang mengembalikan kod hash yang unik untuk setiap objek. Keupayaan mengunci ini berfungsi keranaObjectkelas menentukan kaedah HashCode dan oleh itu diwarisi oleh semua objek, tetapi tidak selalu seperti yang anda mahukan. Sebagai contoh, jika anda memasukkan objek ke dalam bekas jadual hash anda dan anda mengindeksnya dengan objek String, kaedah HashCode lalai hanya mengembalikan bilangan bulat unik berdasarkan nilai rujukan objek. Untuk rentetan, anda benar-benar mahu kod hash menjadi fungsi dari nilai rentetan, jadi String mengatasi HashCode dan membekalkan versi sendiri. Ini bermaksud bahawa untuk objek apa pun yang anda kembangkan, dan ingin menyimpan di dalam tabel hash menggunakan contoh objek sebagai kunci, anda mesti mengganti kaedah HashCode. Ini memastikan bahawa objek yang dibina secara identik mempunyai kod yang sama.

Tetapi bagaimana dengan bekas yang disusun? Satu-satunya antara muka penyortiran yang disediakan di Objectkelas adalah sama dengan () , dan ia terpaksa menyamakan dua objek yang mempunyai rujukan yang sama, tidak mempunyai nilai yang sama. Inilah sebabnya mengapa, di Java, anda tidak dapat menulis kod berikut:

 jika (someStringObject == "ini") maka {... buat sesuatu ...} 

Kod di atas membandingkan rujukan objek, menyatakan bahawa terdapat dua objek yang berbeza di sini, dan mengembalikan palsu. Anda mesti menulis kodnya seperti berikut:

 jika (someStringObject.compareTo ("this") == 0) maka {... buat sesuatu ...} 

Ujian terakhir ini menggunakan pengetahuan yang dikemas dalam kaedah String σύγκanding untuk membandingkan dua objek rentetan dan mengembalikan petunjuk persamaan.

Menggunakan alat di dalam kotak

Seperti yang saya nyatakan sebelumnya, pembangun program generik memiliki dua alat utama yang tersedia untuk mereka: warisan pelaksanaan (pemanjangan) dan warisan tingkah laku (pelaksanaan).

Untuk menggunakan warisan pelaksanaan, anda memperluas (subkelas) kelas yang ada. Secara lanjutan, semua subkelas kelas asas mempunyai keupayaan yang sama dengan kelas root. Ini adalah asas untuk HashCodekaedah di Objectkelas. Oleh kerana semua objek diwarisi dari java.lang.Objectkelas, semua objek mempunyai kaedah HashCodeyang mengembalikan hash unik untuk objek tersebut. Sekiranya anda ingin menggunakan objek anda sebagai kunci, ingatlah peringatan yang disebutkan sebelumnya mengenai penolakan HashCode.

Selain warisan implementasi, ada perilaku warisan (implementasi), yang dicapai dengan menentukan bahwa objek menerapkan antarmuka Java tertentu. Objek yang melaksanakan antara muka boleh dilemparkan ke rujukan objek dari jenis antara muka itu. Maka rujukan itu dapat digunakan untuk menggunakan kaedah yang ditentukan oleh antara muka tersebut. Biasanya, antara muka digunakan apabila kelas mungkin perlu memproses beberapa objek dari pelbagai jenis dengan cara yang sama. Sebagai contoh, Java menentukan antara muka Runnable yang digunakan oleh kelas utas untuk bekerja dengan kelas dalam utas mereka sendiri.

Membina bekas

Untuk menunjukkan pertukaran dalam menulis kod generik, saya akan memandu anda melalui reka bentuk dan pelaksanaan kelas kontena yang disusun.

Seperti yang saya sebutkan sebelumnya, dalam pengembangan aplikasi tujuan umum, dalam banyak keadaan wadah yang baik akan berguna. Dalam aplikasi contoh saya, saya memerlukan bekas yang keduanya dikunci , yang bermaksud bahawa saya ingin mengambil objek terkandung dengan menggunakan kunci sederhana, dan disusun supaya saya dapat mengambil objek yang terkandung dalam urutan tertentu berdasarkan nilai-nilai utama.

Semasa merancang sistem, penting untuk diingat bahagian sistem mana yang menggunakan antara muka tertentu. Bagi bekas, terdapat dua antara muka kritikal - bekas itu sendiri dan kunci yang mengindeks bekas. Program pengguna menggunakan bekas untuk menyimpan dan menyusun objek; kontena itu sendiri menggunakan antara muka kunci untuk membantu mereka mengatur diri mereka sendiri. Semasa merancang bekas, kami berusaha menjadikannya mudah digunakan dan menyimpan pelbagai jenis objek (sehingga meningkatkan kegunaannya). Kami merancang kunci agar fleksibel sehingga pelbagai pelaksanaan kontena dapat menggunakan struktur kunci yang sama.

To solve my behavioral requirements, keying and sorting, I turn to a useful tree data structure called a binary search tree (BST). Binary trees have the useful property of being sorted, so they can be efficiently searched and can be dumped out in sorted order. The actual BST code is an implementation of the algorithms published in the book Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, and Ron Rivest.

java.util.Dictionary

The Java standard classes have taken a first step toward generic keyed containers with the definition of an abstract class named java.util.Dictionary. If you look at the source code that comes with the JDK, you will see that Hashtable is a subclass of Dictionary.

The Dictionary class attempts to define the methods common to all keyed containers. Technically, what is being described could more properly be called a store as there is no required binding between the key and the object it indexes. However, the name is appropriate as nearly everyone understands the basic operation of a dictionary. An alternative name might be KeyedContainer, but that title gets tedious pretty quickly. The point is that the common superclass of a set of generic classes should express the core behavior being factored out by that class. The Dictionary methods are as follows:

size( )

This method returns the number of objects currently being held by the container.
isEmpty( ) This method returns true if the container has no elements.
keys( ) Return the list of keys in the table as an Enumeration.
elements( ) Return the list of contained objects as an Enumeration.
get(Objectk) Get an object, given a particular key k.
put(Objectk,Objecto) Store an object o using key k.
remove(Objectk) Remove an object that is indexed by key k.

By subclassing Dictionary, we use the tool of implementation inheritance to create an object that can be used by a wide variety of clients. These clients need know only how to use a Dictionary, and we can then substitute our new BST or a Hashtable without the client noticing. It is this property of abstracting out the core interface into the superclass that is crucial to reusability, general-purpose function, expressed cleanly.

Basically, Dictionary gives us two groups of behavior, accounting and administration -- accounting in the form of how many objects we've stored and bulk reading of the store, and administration in the form of get, put, and remove.

If you look at the Hashtable class source (it is included with all versions of the JDK in a file named src.zip), you will see that this class extends Dictionary and has two private internal classes, one named HashtableEntry and one named HashtableEnumerator. The implementation is straightforward. When put is called, objects are placed into a HashtableEntry object and stored into a hash table. When get is called, the key passed is hashed and the hashcode is used to locate the desired object in the hash table. These methods keep track of how many objects have been added or removed, and this information is returned in response to a size request. The HashtableEnumerator class is used to return results of the elements method or keys method.

First cut at a generic keyed container

The BinarySearchTree class is an example of a generic container that subclasses Dictionary but uses a different organizing principle. As in the Hashtable class, I've added a couple of classes to support holding the stored objects and keys and for enumerating the table.

The first is BSTNode, which is equivalent to a HashtableEntry. It is defined as shown in the code outline below. You can also look at the source.

class BSTNode { protected BSTNode parent; protected BSTNode left; protected BSTNode right; protected String key; protected Object payload; public BSTNode(String k, Object p) { key = k; payload = p; } protected BSTNode() { super(); } BSTNode successor() { return successor(this); } BSTNode precessor() { return predecessor(this); } BSTNode min() { return min(this); } BSTNode max() { return max(this); } void print(PrintStream p) { print(this, p); } private static BSTNode successor(BSTNode n) { ... } private static BSTNode predecessor(BSTNode n) { ... } private static BSTNode min(BSTNode n) { ... } private static BSTNode max(BSTNode n) { ... } private static void print(BSTNode n, PrintStream p) { ... } } 

Mari kita perhatikan kod ini untuk menjelaskan dua perkara. Pertama, terdapat konstruktor yang dilindungi nol, yang ada sehingga subkelas kelas ini tidak perlu menyatakan konstruktor yang mengatasi salah satu pembina kelas ini. Kedua, kaedah pengganti , pendahulu , min , maks , dan cetak sangat pendek dan hanya memanggil setara peribadi yang sama untuk menjimatkan ruang memori.