Java Collections John Zukowski

Chia sẻ: Tan Giang | Ngày: | Loại File: PDF | Số trang:295

0
88
lượt xem
20
download

Java Collections John Zukowski

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

When learning a new computer programming language, one of the first things you tend to ask is how to work with large groups of data. This topic is often covered in the second course of the standard curriculum for Computer Science as part of a class typically called Data Structures. If you were to look at the class syllabus, you'd likely see topics such as linked lists, queues, stacks, and binary trees, among many other data structures. In Java, these structures are part of the Java Collections Framework....

Chủ đề:
Lưu

Nội dung Text: Java Collections John Zukowski

  1. Java Collections John Zukowski Copyright © 2001 by John Zukowski All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN (pbk): 1-893115-92-5 Trademarked names may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, we use the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. Editorial Directors: Dan Appleman, Gary Cornell, Karen Watterson Technical Editor: Kim Topley Developmental Editor and Copy Editor: Kiersten Burke Production Editor: Kari Brooks Compositor: Impressions Book and Journal Services, Inc. Indexer: Carol Burbo Cover Designer: Karl Miyajima Distributed to the book trade in the United States by Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY, 10010 and outside the United States by Springer-Verlag GmbH & Co. KG, Tiergartenstr. 17, 69112 Heidelberg, Germany The information in this book is distributed on an "as is" basis, without warranty. Although every precaution has been taken in the preparation of this work, neither the author nor Apress shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in this work. Acknowledgments Writing this book has been an interesting experience. So much has changed from when I started until now, it's almost hard to believe. No more "Focus on Java" at About.com, no more employment by jGuru (though I still consult for them), and I'm now off on my own with JZ Ventures, Inc. If you're in need of strategic Java consulting... As always, it's time to thank everyone who helped take my horrible writing and awful drawings into the book you're holding today. At Apress, I'd like to thank Gary Cornell for the book's concept, without which this may have ended
  2. up being just another book on JavaServer Pages, XML, or some other already-covered topic. I would especially like to thank Kiersten Burke for putting up with me, Grace Wong for her roll as mediator, as well as Kari Brooks and Stephanie Rodriguez for their help in shaping up what you are holding today. Special thanks to technical editor Kim Topley who not only straightened me out on some technical lapses, but also helped me to fill in some gaps. Any remaining technical inaccuracies are mine alone. For their continued encouragement along the way, I'd like to personally acknowledge my brother-in- law, Scott Pross, for joining the ranks of geekhood, even if it is with certification from that other software company; my cousin Rachel Goodell, the traveling nurse—it was fun having you in Boston for a change; and Ted Behr, my personal coach, for reminding me that there is more to life than Java. And, of course, all the readers and jGuru Collections FAQ contributors whose ideas, questions, and encouragement should make this edition much better. As always, I am grateful to my wife, Lisa, for her patience and support in jumpstarting JZ Ventures, and our playful three-year old pup, Jaeger, who thinks it's more important for him to be amused than me to be productive. Thanks to Mom and Dad, too, may they enjoy their computer.
  3. Table of Contents Chapter 1: Java Collections Framework: An Overview.................................................................................1 What Is This Book About?......................................................................................................................1 Is This Book for You?................................................................................................................2 How Is This Book Structured? ....................................................................................................2 How Do I Read the Diagrams?...................................................................................................3 Part I: The Historical Collection Classes..........................................................................................................4 Chapter List.............................................................................................................................................4 . Chapter 2: Arrays...............................................................................................................................................5 Overview..................................................................................................................................................5 Array Basics.............................................................................................................................................5 Declaring and Creating Arrays................................................................................................................7 Arrays of Primitives....................................................................................................................8 Arrays of Objects........................................................................................................................9 Multidimensional Arrays............................................................................................................9 Initializing Arrays.....................................................................................................................11 Passing Array Arguments and Return Values..........................................................................12 Copying and Cloning Arrays.................................................................................................................13 Array Immutability................................................................................................................................14 Array Assignments .................................................................................................................................14 Checking for Array Equality ..................................................................................................................15 Array Reflection .....................................................................................................................................16 Character Arrays....................................................................................................................................19 Summary................................................................................................................................................20 Chapter 3: The Vector and Stack Classes......................................................................................................21 Overview................................................................................................................................................21 Vector Basics.........................................................................................................................................21 Creating Vectors.......................................................................................................................23 Adding Elements .......................................................................................................................24 Printing Vectors........................................................................................................................26 Removing Elements..................................................................................................................26 Replacing Elements..................................................................................................................28 Sizing Vectors...........................................................................................................................29 Vector Immutability ..................................................................................................................30 Vector Operations..................................................................................................................................30 Fetching Elements .....................................................................................................................30 Finding Elements......................................................................................................................32 Copying and Cloning Vectors ...................................................................................................34 Checking Vectors for Equality.................................................................................................37 Hashing Vectors ........................................................................................................................37 Serializing Vector.....................................................................................................................37 Maintaining Listener Lists with a Vector.................................................................................38 Vector Variables and Constants.............................................................................................................42 Variables Defined with Vector.................................................................................................42 Variables Defined with AbstractList........................................................................................43 Stack Basics...........................................................................................................................................43 Creating Stacks.........................................................................................................................44 Operating Stacks.......................................................................................................................44 i
  4. Table of Contents Chapter 3: The Vector and Stack Classes Stack Example..........................................................................................................................45 Summary................................................................................................................................................46 Chapter 4: The Enumeration Interface..........................................................................................................47 Enumeration Basics...............................................................................................................................47 The SequenceInputStream Class..............................................................................................48 StringTokenizer........................................................................................................................49 Creating Custom Enumerations.............................................................................................................49 Summary................................................................................................................................................51 Chapter 5: The Dictionary, Hashtable, and Properties Classes...................................................................52 Overview................................................................................................................................................52 Dictionary Basics...................................................................................................................................52 Hashtable Basics....................................................................................................................................53 Understanding Hash Tables......................................................................................................54 Creating Hash Tables................................................................................................................56 Adding Key−Value Pairs..........................................................................................................56 Displaying Hash Table Contents..............................................................................................57 Removing Key−Value Pairs.....................................................................................................57 Sizing Hash Tables...................................................................................................................57 Operating with Hash Tables ...................................................................................................................58 Fetching Keys and Values........................................................................................................58 Finding Elements......................................................................................................................59 Cloning Hash Tables .................................................................................................................60 Checking Hash Tables for Equality..........................................................................................60 Hashing Hash Tables................................................................................................................60 Serializing Hash Tables............................................................................................................60 Hashtable Immutability .............................................................................................................60 Generating Hash Codes............................................................................................................61 Counting Word Occurrences....................................................................................................61 UIDefaults Demonstration........................................................................................................63 Properties Basics....................................................................................................................................64 Using Properties.....................................................................................................................................65 Setting and Getting Elements...................................................................................................65 Getting a List............................................................................................................................66 Loading and Saving..................................................................................................................66 System Properties.....................................................................................................................67 Working with Security Providers ...........................................................................................................69 Understanding Resource Bundles..........................................................................................................72 Summary................................................................................................................................................72 Chapter 6: The BitSet Class.............................................................................................................................73 Overview................................................................................................................................................73 BitSet Basics..........................................................................................................................................73 Creating Bit Sets.......................................................................................................................74 Printing Bit Sets........................................................................................................................74 Bit Set Operations..................................................................................................................................74 Manipulating Individual Bits....................................................................................................74 Manipulating Sets of Bits.........................................................................................................75 ii
  5. Table of Contents Chapter 6: The BitSet Class Determining Set Size................................................................................................................76 Cloning Bit Sets........................................................................................................................76 Checking Bit Sets for Equality.................................................................................................76 Hashing Bit Sets ........................................................................................................................76 Using BitSet: an Example......................................................................................................................77 Summary................................................................................................................................................78 Part II: The Collections Framework...............................................................................................................79 Chapter ..................................................................................................................................................79 List...........................................................................................................................................79 . Chapter 7: Collections Introduction...............................................................................................................80 Overview................................................................................................................................................80 Framework Basics ..................................................................................................................................80 Framework Interfaces...............................................................................................................80 Framework Implementations....................................................................................................81 Framework Algorithms.............................................................................................................82 Collection Interface ................................................................................................................................82 Adding Elements .......................................................................................................................83 Removing Elements..................................................................................................................84 Collection Operations............................................................................................................................85 Fetching Elements .....................................................................................................................85 Finding Elements......................................................................................................................86 Checking Size...........................................................................................................................86 Copying and Cloning Collections.............................................................................................86 Checking for Equality...............................................................................................................87 Hashing Collections..................................................................................................................88 Iterator Interface .....................................................................................................................................88 Using an Iterator.......................................................................................................................88 Filtering Iterator........................................................................................................................89 Collection Exceptions............................................................................................................................91 ConcurrentModificationException...........................................................................................91 UnsupportedOperationException ..............................................................................................92 Summary................................................................................................................................................92 Chapter 8: Sets..................................................................................................................................................93 Overview................................................................................................................................................93 Set Basics...............................................................................................................................................93 HashSet Class........................................................................................................................................94 Creating a HashSet...................................................................................................................95 . Adding Elements .......................................................................................................................95 Removing Elements..................................................................................................................96 Set Operations........................................................................................................................................98 Fetching Elements .....................................................................................................................98 Finding Elements......................................................................................................................99 Checking Size...........................................................................................................................99 Copying and Cloning Sets........................................................................................................99 Checking for Equality.............................................................................................................101 Hashing Collections................................................................................................................101 TreeSet Class.......................................................................................................................................101 iii
  6. Table of Contents Chapter 8: Sets Creating a TreeSet..................................................................................................................102 Adding Elements .....................................................................................................................103 Comparing..............................................................................................................................103 Retrieving the Ends .................................................................................................................104 Fetching Elements ...................................................................................................................104 Working with Subsets.............................................................................................................104 Summary..............................................................................................................................................106 Chapter 9: Lists...............................................................................................................................................107 Overview..............................................................................................................................................107 List Basics............................................................................................................................................107 What's New..........................................................................................................................................108 Usage Issues.........................................................................................................................................109 ArrayList Class....................................................................................................................................110 Creating an ArrayList.............................................................................................................111 Adding Elements .....................................................................................................................111 Getting an Element.................................................................................................................113 Removing Elements................................................................................................................113 List Operations.....................................................................................................................................115 Fetching Elements ...................................................................................................................115 Finding Elements....................................................................................................................115 Replacing Elements................................................................................................................116 Checking Size.........................................................................................................................117 Checking Capacity..................................................................................................................117 Copying and Cloning Lists.....................................................................................................117 Checking for Equality.............................................................................................................118 Hashing Lists..........................................................................................................................118 LinkedList Class..................................................................................................................................119 Creating a LinkedList.............................................................................................................120 Adding Elements .....................................................................................................................120 Retrieving the Ends .................................................................................................................120 Removing Elements................................................................................................................120 LinkedList Example ................................................................................................................121 ListIterator...........................................................................................................................................123 . Summary..............................................................................................................................................125 Chapter 10: Maps...........................................................................................................................................127 Overview..............................................................................................................................................127 Map Basics...........................................................................................................................................127 Map.Entry Interface.............................................................................................................................128 HashMap Class....................................................................................................................................130 Creating a HashMap...............................................................................................................130 Adding Key−Value Pairs........................................................................................................131 Displaying Contents ................................................................................................................131 Removing Key−Value Pairs...................................................................................................132 Sizing Hash Maps...................................................................................................................132 Map Operations ....................................................................................................................................133 Fetching Keys and Values......................................................................................................133 Finding Elements....................................................................................................................133 iv
  7. Table of Contents Chapter 10: Maps Cloning Hash Map..................................................................................................................134 Checking Hash Maps for Equality..........................................................................................134 Hashing Hash Maps................................................................................................................134 Serializing Hash Maps............................................................................................................134 WeakHashMap Class...........................................................................................................................135 Creating a WeakHashMap......................................................................................................135 Understanding Weak References............................................................................................135 Using a WeakHashMap..........................................................................................................136 WeakHashMap Example........................................................................................................137 TreeMap Class.....................................................................................................................................141 Creating a TreeMap................................................................................................................142 Viewing Sub Maps ..................................................................................................................142 Working with End Points ........................................................................................................143 Sharing Comparators..............................................................................................................143 Map Usage...........................................................................................................................................143 Summary..............................................................................................................................................146 Chapter 11: Sorting........................................................................................................................................147 Comparable Basics ...............................................................................................................................147 System−Defined Comparable Classes....................................................................................147 Understanding Comparable....................................................................................................148 Using Comparable..................................................................................................................148 Comparator Basics...............................................................................................................................150 Understanding Comparator.....................................................................................................150 Using Comparator...................................................................................................................151 SortedSet..............................................................................................................................................152 Understanding SortedSet........................................................................................................153 Using TreeSet.........................................................................................................................155 SortedMap............................................................................................................................................155 Understanding SortedMap......................................................................................................156 Using TreeMap.......................................................................................................................157 Summary..............................................................................................................................................157 Chapter 12: Special Collections Support......................................................................................................158 Overview..............................................................................................................................................158 Prebuilt Collections ..............................................................................................................................159 Empty Collections ...................................................................................................................159 Singleton Collections..............................................................................................................159 Wrapped Collections ............................................................................................................................160 Read−Only Collections...........................................................................................................160 Thread−Safe Collections........................................................................................................161 Sorting..................................................................................................................................................162 Sorting Lists............................................................................................................................162 Reversing Order......................................................................................................................163 Searching ..............................................................................................................................................163 Binary Searching .....................................................................................................................163 Finding Extremes....................................................................................................................165 Generic List Operations.......................................................................................................................166 Copying Lists..........................................................................................................................166 v
  8. Table of Contents Chapter 12: Special Collections Support Filling Lists.............................................................................................................................166 Multiple−Copy Collections....................................................................................................167 Reversing Lists.......................................................................................................................167 Shuffling Lists .........................................................................................................................168 Sorting Lists............................................................................................................................168 Summary..............................................................................................................................................169 Chapter 13: Array Algorithm Support.........................................................................................................170 Overview..............................................................................................................................................170 Filling Arrays.......................................................................................................................................170 Checking Equality ................................................................................................................................172 Sorting Arrays......................................................................................................................................173 Primitive Arrays ......................................................................................................................173 Object Arrays..........................................................................................................................174 Searching Arrays ..................................................................................................................................175 Primitive Arrays ......................................................................................................................175 Object Arrays..........................................................................................................................177 Summary..............................................................................................................................................177 Chapter 14: Custom Implementations..........................................................................................................178 Overview..............................................................................................................................................178 AbstractCollection Class ......................................................................................................................178 Subclassing AbstractCollection..............................................................................................179 Implementing Optional Methods............................................................................................179 AbstractSet Class.................................................................................................................................180 Creating a Custom Set............................................................................................................180 AbstractList Class................................................................................................................................182 Subclassing AbstractList........................................................................................................183 . Implementing Optional Methods............................................................................................183 AbstractSequentialList Class...............................................................................................................184 Subclassing AbstractSequentialList .......................................................................................184 . Implementing Optional Methods............................................................................................185 AbstractMap Class...............................................................................................................................185 Subclassing AbstractMap.......................................................................................................186 Implementing Optional Methods............................................................................................186 Creating a Custom Map..........................................................................................................186 Summary..............................................................................................................................................189 Chapter 15: Compatibility Issues..................................................................................................................190 Converting from Historical to New Collections..................................................................................190 Vectors and Hashtables ...........................................................................................................190 Arrays......................................................................................................................................190 Enumerations..........................................................................................................................190 Converting from New to Historical Collections..................................................................................192 Vectors and Hashtables ...........................................................................................................192 Arrays......................................................................................................................................192 Enumerations..........................................................................................................................192 Working with JDK 1.1.........................................................................................................................193 Comparing Objects with JDK 1.1...........................................................................................194 vi
  9. Table of Contents Chapter 15: Compatibility Issues License Requirements.............................................................................................................196 Distinguishing between the 1.2 and 1.3 Releases................................................................................196 Summary..............................................................................................................................................196 Chapter 16: Advanced Usages.......................................................................................................................198 Creating Advanced Collections...........................................................................................................198 Priority Queue.........................................................................................................................198 Multimap .................................................................................................................................203 Soft Hash Map........................................................................................................................207 Finding Additional Collections............................................................................................................212 Choosing the Right Collection.............................................................................................................213 Summary..............................................................................................................................................213 Part III: Alternative Collection Libraries....................................................................................................214 Chapter ................................................................................................................................................214 List.........................................................................................................................................214 . Chapter 17: JGL Libraries............................................................................................................................215 Overview..............................................................................................................................................215 Getting Started.....................................................................................................................................215 Acquisition..............................................................................................................................215 Installation..............................................................................................................................216 Usage......................................................................................................................................219 Licensing and Redistribution Rights .......................................................................................220 Product Support......................................................................................................................220 Key Classes and Interfaces..................................................................................................................220 Collection Classes...................................................................................................................220 Algorithm Support..................................................................................................................224 Functions and Predicates........................................................................................................226 Summary..............................................................................................................................................228 Chapter 18: util.concurrent...........................................................................................................................229 Overview..............................................................................................................................................229 Getting Started.....................................................................................................................................229 Acquisition..............................................................................................................................229 Installation..............................................................................................................................229 Usage......................................................................................................................................230 Licensing and Redistribution Rights .......................................................................................230 Product Support......................................................................................................................230 Key Classes and Interfaces..................................................................................................................231 Sync Interface.........................................................................................................................231 ReadWriteLock Interface ........................................................................................................234 Collection Classes................................................................................................................................235 Copy−on−Write Collections...................................................................................................236 Synchronized Collections.......................................................................................................237 Optimized Hash Maps............................................................................................................238 Summary..............................................................................................................................................238 vii
  10. Table of Contents Chapter 19: Colt..............................................................................................................................................240 Getting Started.....................................................................................................................................240 Acquisition..............................................................................................................................240 Installation..............................................................................................................................240 Usage......................................................................................................................................241 Licensing and Redistribution Rights .......................................................................................241 Product Support......................................................................................................................242 Other Libraries........................................................................................................................242 Key Classes and Interfaces..................................................................................................................243 Package cern.colt....................................................................................................................244 Package cern.colt.bitvector.....................................................................................................245 Package cern.colt.list and cern.colt.list.adapter......................................................................245 Package cern.colt.buffer.........................................................................................................246 Package cern.colt.function......................................................................................................248 Package cern.colt.map............................................................................................................248 Package cern.colt.matrix.*......................................................................................................249 Summary..............................................................................................................................................249 Appendix A: Collections API Reference.......................................................................................................250 Class, Method, and Field Index...........................................................................................................250 Class−Level API Index........................................................................................................................255 AbstractCollection Class .........................................................................................................255 AbstractList Class...................................................................................................................256 AbstractMap Class..................................................................................................................256 AbstractSequentialList Class..................................................................................................257 AbstractSet Class....................................................................................................................257 ArrayList Class.......................................................................................................................257 Arrays Class............................................................................................................................258 BitSet Class.............................................................................................................................258 Collection Interface .................................................................................................................259 Collections Class .....................................................................................................................259 Comparable Interface ..............................................................................................................260 Comparator Interface..............................................................................................................260 ConcurrentModificationException Class ................................................................................261 Dictionary Class ......................................................................................................................261 Enumeration Interface .............................................................................................................261 HashMap Class.......................................................................................................................261 HashSet Class.........................................................................................................................262 Hashtable Class.......................................................................................................................262 Iterator Interface.....................................................................................................................263 LinkedList Class.....................................................................................................................263 List Interface...........................................................................................................................264 ListIterator Interface...............................................................................................................265 Map Interface..........................................................................................................................265 Map.Entry Interface................................................................................................................266 Properties Class .......................................................................................................................266 Set Interface............................................................................................................................266 SortedMap Interface...............................................................................................................267 SortedSet Interface ..................................................................................................................267 Stack Class..............................................................................................................................268 viii
  11. Table of Contents Appendix A: Collections API Reference TreeMap Class........................................................................................................................268 TreeSet Class..........................................................................................................................269 UnsupportedOperationException Class..................................................................................269 Vector Class............................................................................................................................269 WeakHashMap Class..............................................................................................................271 Appendix B: Collections Resources...............................................................................................................272 Collections Implementations...............................................................................................................272 Collections FAQs and Tutorials..........................................................................................................273 Mailing Lists and Newsgroups............................................................................................................273 Collections−Related Web Sites and Information .................................................................................274 Appendix C: Generic Types...........................................................................................................................275 Overview..............................................................................................................................................275 Generic Type Basics............................................................................................................................275 Generic Java.........................................................................................................................................276 Defining Generic Classes and Interfaces................................................................................276 Using Generic Classes............................................................................................................277 PolyJ .....................................................................................................................................................278 Defining Generic Classes and Interfaces................................................................................278 JSR 14..................................................................................................................................................279 ix
  12. Chapter 1: Java Collections Framework: An Overview When learning a new computer programming language, one of the first things you tend to ask is how to work with large groups of data. This topic is often covered in the second course of the standard curriculum for Computer Science as part of a class typically called Data Structures. If you were to look at the class syllabus, you'd likely see topics such as linked lists, queues, stacks, and binary trees, among many other data structures. In Java, these structures are part of the Java Collections Framework. Collections are typically used in a business environment for short−term management of information. This information may have been retrieved from a database, acquired over the network, or just entered by a user. Their primary purpose though is to help the data persist over the lifetime of a program, in a structure that is efficient for the data's purpose. Different collections offer different purposes with quick insertions and deletions but slower fetches, or the reverse, or something in between. Your typical computer science text describes this information in what is called Big O notation and states how fast or slow operations take for each data structure. What Is This Book About? This book is about Java's support for dealing with groups of data. Prior to the Java 2 release, the only standard support for data structures and algorithms was a few fairly basic options available through arrays, hash tables, and vectors. Many people either created their own standard data structure library or reused one of several libraries introduced to deal with collections like the Generic Collection Library for Java (JGL) from ObjectSpace. Aside from rolling their own libraries or reusing those created by others, the Collections Framework (beginning with what came with the early beta release of the Java 2 platform, version 1.2) introduced support into the core Java APIs for manipulating data collections. This book describes how to use this Collections Framework. We'll also look at some of the common alternate frameworks available. A JavaWorld survey back in the summer of 1998 asked readers whether Sun should scrap its Collections API in favor of the more robust JGL (the results are posted at JavaWorld, http://www.javaworld.com/jw−08−1998/jw−08−pollresults.html). At the time, the Java 2 release wasn't final yet, and as Figure 1−1 shows, most people wanted Sun to dump the Collections Framework in favor of licensing JGL. Figure 1−1: The 1998 JavaWorld survey results. While there hasn't been a new survey since, many people find the Collections Framework much easier to use. In addition, since the framework is a core API, not a third−party library, you do not need to redistribute the library with your application. Of course, even Sun doesn't use their own Collections Framework in things like the Swing component set yet, whereas all the internal data models are still using the historical collection classes. And for what its worth, ObjectSpace hasn't released a new version in close to two years. As of this writing in early 2001, they just recently removed a reference from their Web site to the 1.2 release of Java 1
  13. Is This Book for You? being in limited beta testing, months after the release of 1.3. Note Given the name of the JGL library, you might think the acronym was coined when someone spent too much time at the pub. It actually comes from an earlier name for the library that violated Sun's Java trademarks. After a friendly letter from the legal department at Sun, the product name was changed but the acronym remained. Most of the time you only see the acronym with no mention of its illogical expansion. Is This Book for You? This book is not meant to be a textbook for a second course in computer science. It does not cover the material in ACM's Curriculum '78, its revised version in '84, or even in the combined ACM/IEEE Computing Curricula 1991! In fact, I've never read any of those. This book will not teach you how to program in Java. If you need to learn, there are many good books. While I would like everyone to learn from my Mastering Java 2 book (Sybex, 1998), other good learning books are Core Java 2, Volume 1: Fundamentals (Prentice Hall, 2000); Beginning Java 2 (Wrox, 2000); The Java Tutorial (Addison−Wesley, 2000); Thinking in Java (Prentice Hall, 2000); and Learning Java (O'Reilly, 2000). Which one is right for you depends upon your specific back−ground. If you are truly new to programming, consider getting Java Programming: from the Beginning (Norton, 2000). If you can program with Java but you don't understand interfaces yet, you may have some trouble getting through the material in this book. So what does that leave? This book will teach you about the Java Collections Framework. If you'd like to learn more than the single chapter's coverage of the Collections Framework found in most Java books, this book will provide you with a great deal more. In addition, this book describes several of the alternate collection libraries, such as the JGL Libraries from ObjectSpace; Doug Lea's util.concurrent package; and the Colt Distribution for high performance computing. With each of these other libraries, we'll take a quick look at what they offer and I'll introduce you to the collections−related support available from each. While this book isn't meant to be a computer science curriculum text, I do describe concepts like the details of balanced trees and hash tables. An understanding of how each concept works helps you to decide which collection implementation class is appropriate. You will, of course, need a Java development environment. The latest JDK from Sun is sufficient, although you might find yourself more productive with one of the visual development tools like JBuilder or Forté for Java. Of course, since the collections library is not meant to be visually programmed, any old text editor like emacs will do. How Is This Book Structured? This book is broken down into three parts and three appendices. The first part introduces the historical collection classes; the second part describes the Java Collections Framework; and in the third part you'll find descriptions of the alternate collection libraries. In most cases, you don't need to read the book from start to finish; you can just go directly to the particular data structure, class, or interface you wish to learn more about. The exception would be cases such as working with hash tables. Instead of describing them in multiple sections, with both Hashtable and HashMap you'll find the deepest description in the first Hashtable chapter and less in the HashMap chapter. Feel free to flip back and forth as necessary. 2
  14. How Is This Book Structured? The Historical Collection Classes Part One of the book provides you with everything you ever wanted to know about the historical collection classes. While most people know how to do most of the basic array, vector, and hash table operations, we'll also dig into some of the less commonly discussed tasks, such as array reflection and optimization techniques. The Java Collections Framework Part Two deals with the Java Collections Framework. This framework was introduced with the release of the Java 2 Standard Edition, version 1.2. With minor changes, it remains relatively the same in the 1.3 release of the Standard Edition (and is the same in the 1.2 release of the Enterprise Edition). The framework provides enhanced support to manipulate groups of data and allows you to easily separate storage from access. We also explore using the framework with the earlier 1.1 release of the JDK. Alternative Collection Libraries In Part Three, we'll discuss some of the other collection libraries out there. While the JGL Libraries seemed like a de facto collection library years ago, its usage seems to be slipping of late. We'll introduce it here, along with Doug's library and Colt. Note Originating from work by Alexander Stephanov at Hewlett−Packard in 1979, the C++ Standard Template Library, or STL as it is commonly known, is a standard part of the ANSI (American), ISO (International), BSI (British), and DIN (German) adopted C++ standard of November 14, 1997. While this book doesn't cover the STL, if you are interested in learning more about it, you can read "Mumit's STL Newbie's Guide" available at http://www.xraylith.wisc.edu/~khan/software/stl/STL.newbie.html. Keep in mind that the document is for the C++ developer and not the Java developer. The Appendices There are three appendices in this book. Appendix A provides an API reference to the core Java classes of the Collections Framework. You'll find both a class−level API reference as well as an alphabetical class, method, and field reference. In Appendix B you'll find a list of resources to help you become more productive with the book's contents. Appendix C describes support for parameterized types, a prelude to something that could become a Java standard soon, possibly as early as the 1.4 release. The Source Code This book does not include a CD. However, the source code from the book is freely available from the Apress Web site at http://www.apress.com/. With nearly universal Internet access, at least for those programming with Java, I hope that this will not be an issue for anyone. How Do I Read the Diagrams? In all three parts of the book, I've used UML to diagram the design of the classes and processes. If you're already familiar with UML, you should have no problem understanding the diagrams. If you're not yet familiar with the UML, consider reviewing The Unified Modeling Language User Guide (Addison−Wesley, 1998) or UML Distilled (Addison−Wesley, 1999) for a complete tutorial on the subject. In the next chapter, you'll take a long look at array support in Java. Beginning with basic access and creation, you'll quickly move into multi−dimensional array support, initialization, cloning, and immutability. 3
  15. Part I: The Historical Collection Classes Chapter List Chapter 2: Arrays Chapter 3: The Vector and Stack Classes Chapter 4: The Enumeration Interface Chapter 5: The Dictionary, Hashtable, and Properties Classes Chapter 6: The BitSet Class 4
  16. Chapter 2: Arrays Overview Arrays are the only collection support defined within the Java programming language. They are objects that store a set of elements in an order accessible by index, or position. They are a subclass of Object and implement both the Serializable and Cloneable interfaces. However, there is no .java source file for you to see how the internals work. Basically, you create an array with a specific size and type of element, then fill it up. Note Since arrays subclass Object, you can synchronize on an array variable and call its wait() and notify() methods. Let's take a look at what we can do with array objects—beginning with basic usage and declaration and moving through to copying and cloning. We'll also look at array assignment, equality checking, and reflection. Array Basics Before going into the details of declaring, creating, initializing, and copying arrays, let's go over a simple array example. When creating a Java application, the main() method has a single argument that is a String array: public static void main(String args[]). The compiler doesn't care what argument name you use, only that it is an array of String objects. Given that we now have the command−line arguments to our application as an array of String objects, we can look at each element and print it. Within Java, arrays know their size, and they are always indexed from position zero. Therefore, we can ask the array how big it is by looking at the sole instance variable for an array: length. The following code shows how to do this: public class ArrayArgs { public static void main (String args[]) { for (int i=0, n=args.length; i
  17. Chapter 2: Arrays Listing 2−1: Timing loop performance. public class TimeArray { public static void main (String args[]) { int something = 2; long startTime = System.currentTimeMillis(); for (int i=0, n=Integer.MAX_VALUE; i=0; I−) { something = −something; } long endTime = System.currentTimeMillis(); System.out.println("Increasing Delta: " + (midTime − startTime)); System.out.println("Decreasing Delta: " + (endTime − midTime)); } } This test program is really timing the for−loop and not the array access because there is no array access. Note In most cases, the numbers calculated on my 400 MHz Windows NT system were in the low 11,000s for JDK 1.1 and 1.2. However, under JDK 1.3 with the −classic option (no JIT), the timing numbers increased to around 250,000. Even using the HotSpot VM with 1.3, the numbers were between 19,000 and 30,000. If you ever try to access before the beginning or after the end of an array, an ArrayIndexOutOfBoundsException will be thrown. As a subclass of IndexOutOfBoundsException, the ArrayIndexOutOfBoundsException is a runtime exception, as shown in Figure 2−1. Thankfully, this means that you do not have to place array accesses within try−catch blocks. In addition, since looking beyond the bounds of an array is a runtime exception, your program will compile just fine. The program will only throw the exception when the access is attempted. 6
  18. Declaring and Creating Arrays Figure 2−1: The class hierarchy of ArrayIndexOutOfBoundsException. Note You cannot turn off array bounds checking. It is part of the security architecture of the Java runtime to ensure that invalid memory space is never accessed. The following code demonstrates an improper way to read through the command−line array elements: public class ArrayArgs2 { public static void main (String args[]) { try { int i=0; do { System.out.println("Arg " + i + ": " + args[i++]); } while (true); } catch (ArrayIndexOutOfBoundsException ignored) { } } } While functionally equivalent to the earlier ArrayArgs example, it is bad programming practice to use exception handling for control flow. Exception handling should be reserved for exceptional conditions. Declaring and Creating Arrays Remember that arrays are objects that store a set of elements in an index−accessible order. Those elements can either be a primitive datatype, such as an int or float, or any type of Object. To declare an array of a particular type, just add brackets ([ ]) to the declaration: int[] variable; 7
Đồng bộ tài khoản