Master/Reference Architectures and Patterns/hjp5/html/k100101.html


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259

<html>
<head>
<title>
Handbuch der Java-Programmierung, 5. Auflage
</title>
</head>
<body>
<a name="startofbody"></a>
<script language="JavaScript" src="hjp4lib.js">
</script>
<script language="JavaScript">
installKbdHandler("97,#startofbody;101,#endofbody;116,cover.html;122,k100003.html;115,search.html;105,index.html;100,JDKDOCS;112,APIDOCS;104,k100097.html;106,k100100.html;107,k100102.html;108,k100107.html");
</script>
<table border=0 cellpadding=0 cellspacing=1 width="100%">
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="cover.html">&nbsp;Titel&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100003.html">&nbsp;Inhalt&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="search.html">&nbsp;Suchen&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="index.html">&nbsp;Index&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/index.html" onClick="this.href=getDocIndex()">&nbsp;DOC&nbsp;</a>
<td align="right">Handbuch der Java-Programmierung, 5. Auflage
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100097.html">&nbsp;&lt;&lt;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100100.html">&nbsp;&nbsp;&lt;&nbsp;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100102.html">&nbsp;&nbsp;&gt;&nbsp;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100107.html">&nbsp;&gt;&gt;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/api/index.html" onClick="this.href=getApiIndex()">&nbsp;API&nbsp;</a>
<td align="right">Kapitel 15 - Collections II
</table>
<hr>


<!-- Section -->
<a name="sectlevel2id015004"></a>
<h2>15.4 Die Collection des Typs Set </h2>
<hr>
<ul>
<li><a href="k100101.html#sectlevel2id015004">15.4 Die Collection des Typs Set</a>
<ul>
<li><a href="k100101.html#sectlevel3id015004001">15.4.1 Abstrakte Eigenschaften</a>
<li><a href="k100101.html#sectlevel3id015004002">15.4.2 Implementierungen</a>
</ul>
</ul>
<hr>


<!-- Section -->
<a name="sectlevel3id015004001"></a>
<h3>15.4.1 Abstrakte Eigenschaften </h3>

<p>
Ein <a name="ixa100962"><a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a></a>
&auml;hnelt der <a href="index_l.html#ixb100717"><font color=#000080><tt>List</tt></font></a>,
erlaubt aber im Gegensatz zu dieser keine doppelten Elemente. Genauer
gesagt, in einem <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
darf es zu keinem Zeitpunkt zwei Elemente <font color="#000077"><tt>x</tt></font>
und <font color="#000077"><tt>y</tt></font> geben, f&uuml;r die <font color="#000077"><tt>x.equals(y)</tt></font>
wahr ist. Ein <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
entspricht damit im mathematischen Sinn einer <i>Menge</i>, in der
ja ebenfalls jedes Element nur einmal vorkommen kann. Ein <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
hat allerdings keine spezielle Schnittstelle, sondern erbt seine Methoden
von der Basisklasse <a href="index_c.html#ixb100721"><font color=#000080><tt>Collection</tt></font></a>.

<p>
Die Unterschiede zu <a href="index_l.html#ixb100717"><font color=#000080><tt>List</tt></font></a>
treten zutage, wenn man versucht, mit <a href="index_a.html#ixb100727"><font color=#000080><tt>add</tt></font></a>
ein Element einzuf&uuml;gen, das bereits vorhanden ist (bei dem also
die <a href="index_e.html#ixb100223"><font color=#000080><tt>equals</tt></font></a>-Methode
wie zuvor beschrieben <a href="index_t.html#ixb100233"><font color=#000080><tt>true</tt></font></a>
ergibt). In diesem Fall wird es nicht erneut eingef&uuml;gt, sondern
<a href="index_a.html#ixb100727"><font color=#000080><tt>add</tt></font></a>
gibt <a href="index_f.html#ixb100234"><font color=#000080><tt>false</tt></font></a>
zur&uuml;ck. Auch f&uuml;r die Methoden <a href="index_a.html#ixb100728"><font color=#000080><tt>addAll</tt></font></a>
und den Konstruktor <font color="#000077"><tt>Set(Collection c)</tt></font>
gilt, dass sie kein Element doppelt einf&uuml;gen und damit insgesamt
die Integrit&auml;tsbedingung einer Menge erhalten. 

<p>
Ein weiterer Unterschied zu <a href="index_l.html#ixb100717"><font color=#000080><tt>List</tt></font></a>
ist, dass ein <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
keinen <a href="index_l.html#ixb100735"><font color=#000080><tt>ListIterator</tt></font></a>,
sondern lediglich einen einfachen <a href="index_i.html#ixb100125"><font color=#000080><tt>Iterator</tt></font></a>
erzeugen kann. Dessen Elemente haben keine definierte Reihenfolge.
Sie kann sich durch wiederholtes Einf&uuml;gen von Elementen im Laufe
der Zeit sogar &auml;ndern. 
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100%>
<tr>
<td width=1 align=left valign=top bgcolor="#CC0000"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=1></td>
<td width=1 align=left valign=top bgcolor="#CC0000"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top width=1000>

<p>
Besondere Vorsicht ist geboten, wenn ein <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
dazu benutzt wird, <a name="ixa100963"><i>ver&auml;nderliche Objekte</i></a>
zu speichern (sie werden auch als <a name="ixa100964"><i>mutable</i></a>
bezeichnet). Wird ein Objekt, das in einem <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
gespeichert ist, so ver&auml;ndert, dass der <a href="index_e.html#ixb100223"><font color=#000080><tt>equals</tt></font></a>-Vergleich
mit einem anderen Element danach einen anderen Wert ergeben k&ouml;nnte,
so gilt der komplette <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
als undefiniert und darf nicht mehr benutzt werden. 

<p>
Zentrale Ursache f&uuml;r dieses Problem ist die Tatsache, dass Objektvariablen
intern als <i>Zeiger</i> auf die zugeh&ouml;rigen Objekte dargestellt
werden. Auf ein Objekt, das in einem <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
enthalten ist, kann somit auch von au&szlig;en zugegriffen werden,
wenn nach dem Einf&uuml;gen des Objekts noch ein Verweis darauf zur
Verf&uuml;gung steht. Bei den in Java vordefinierten &#187;kleinen&#171;
Klassen wie <a href="index_s.html#ixb100117"><font color=#000080><tt>String</tt></font></a>,
<a href="index_i.html#ixb100170"><font color=#000080><tt>Integer</tt></font></a>
usw. ist das kein Problem, denn Objekte dieses Typs k&ouml;nnen nach
ihrer Konstruktion nicht mehr ver&auml;ndert werden (sie sind <a name="ixa100965"><i>immutable</i></a>).
Bei ver&auml;nderlichen Objekten k&ouml;nnten dagegen im <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
enthaltene Elemente unbemerkt ver&auml;ndert und dessen Integrit&auml;t
verletzt werden.</td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top>
<table border=0 cellspacing=0 cellpadding=1 width=100% bgcolor="#CC0000">
<tr>
<td><font color="#FFFFFF">&nbsp;Warnung&nbsp;</font></td>
</tr>
</table>
</td>
<td width=1 align=left valign=top bgcolor="#CC0000"><img src="trp1_1.gif"></td>
</tr>
</table>


<!-- Section -->
<a name="sectlevel3id015004002"></a>
<h3>15.4.2 Implementierungen </h3>

<p>
Das <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>-Interface
wird im JDK nur von den Klassen <a name="ixa100966"><a href="index_h.html#ixb100742"><font color=#000080><tt>HashSet</tt></font></a></a>
und <a name="ixa100967"><a href="index_a.html#ixb100743"><font color=#000080><tt>AbstractSet</tt></font></a></a>
implementiert. Die abstrakte Implementierung dient lediglich als Basisklasse
f&uuml;r eigene Ableitungen. In der voll funktionsf&auml;higen <a href="index_h.html#ixb100742"><font color=#000080><tt>HashSet</tt></font></a>-Implementierung
werden die Elemente intern in einer <a name="ixa100968"><a href="index_h.html#ixb100121"><font color=#000080><tt>HashMap</tt></font></a></a>
gespeichert. Vor jedem Einf&uuml;gen wird gepr&uuml;ft, ob das einzuf&uuml;gende
Element bereits in der <a href="index_h.html#ixb100121"><font color=#000080><tt>HashMap</tt></font></a>
enthalten ist. Die Performance der Einf&uuml;ge-, L&ouml;sch- und
Zugriffsfunktionen ist im Mittel <i>konstant</i>. Neben den oben erw&auml;hnten
Standardkonstruktoren besitzt die Klasse <a href="index_h.html#ixb100742"><font color=#000080><tt>HashSet</tt></font></a>
zwei weitere Konstruktoren, deren Argumente direkt an den Konstruktor
der <a href="index_h.html#ixb100121"><font color=#000080><tt>HashMap</tt></font></a>
weitergereicht werden: 
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#EEFFCC">
<tr>
<td valign=top width=100%>
<font color="#660066">
<pre>
HashSet(int initialCapacity)
HashSet(int initialCapacity, float loadFactor)
</pre>
</font>
</td>
<td valign=top>
<a href="../jdkdocs/api/java/util/HashSet.html" onClick="this.href=getApiDoc('java.util.HashSet')"><font color="#660066" size=-1>java.util.HashSet</font></a></td>
</tr>
</table>

<p>
Wir wollen uns die Anwendung eines <a href="index_h.html#ixb100742"><font color=#000080><tt>HashSet</tt></font></a>
am Beispiel der Generierung eines Lottotipps ansehen. Ein &auml;hnliches
Beispiel gibt es in <a href="k100108.html#lottolisting1">Listing 16.1</a>.
Dort wird ein <a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a>
verwendet, um doppelte Zahlen zu verhindern. 
<a name="lottolisting2"></a>

<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#DDDDDD">
<tr>
<td valign=top>
<font color="#000055">
<pre>
<font color="#555555">001 </font><font color="#00AA00">/* Listing1503.java */</font>
<font color="#555555">002 </font>
<font color="#555555">003 </font><font color="#0000AA">import</font> java.util.*;
<font color="#555555">004 </font>
<font color="#555555">005 </font><font color="#0000AA">public</font> <font color="#0000AA">class</font> Listing1503
<font color="#555555">006 </font>{
<font color="#555555">007 </font>  <font color="#0000AA">public</font> <font color="#0000AA">static</font> <font color="#006699">void</font> main(String[] args)
<font color="#555555">008 </font>  {
<font color="#555555">009 </font>    HashSet set = <font color="#0000AA">new</font> HashSet(10);
<font color="#555555">010 </font>    <font color="#006699">int</font> doubletten = 0;
<font color="#555555">011 </font>    <font color="#00AA00">//Lottozahlen erzeugen</font>
<font color="#555555">012 </font>    <font color="#0000AA">while</font> (set.size() &lt; 6) {
<font color="#555555">013 </font>      <font color="#006699">int</font> num = (<font color="#006699">int</font>)(Math.random() * 49) + 1;
<font color="#555555">014 </font>      <font color="#0000AA">if</font> (!set.add(<font color="#0000AA">new</font> Integer(num))) {
<font color="#555555">015 </font>        ++doubletten;
<font color="#555555">016 </font>      }
<font color="#555555">017 </font>    }
<font color="#555555">018 </font>    <font color="#00AA00">//Lottozahlen ausgeben</font>
<font color="#555555">019 </font>    Iterator it = set.iterator();
<font color="#555555">020 </font>    <font color="#0000AA">while</font> (it.hasNext()) {
<font color="#555555">021 </font>      System.out.println(((Integer)it.next()).toString());
<font color="#555555">022 </font>    }
<font color="#555555">023 </font>    System.out.println(<font color="#0000FF">"Ignorierte Doubletten: "</font> + doubletten);
<font color="#555555">024 </font>  }
<font color="#555555">025 </font>}</pre>
</font>
</td>
<td valign=top align=right>
<a href="../examples/Listing1503.java"><font color="#000055" size=-1>Listing1503.java</font></a></td>
</tr>
</table>
<i>
Listing 15.3: Generierung eines Lottotipps mit HashSet</i></p>

<p>
In diesem Listing wird ein <a href="index_h.html#ixb100742"><font color=#000080><tt>HashSet</tt></font></a>
so lange mit Zufallszahlen zwischen 1 und 49 best&uuml;ckt, bis die
Anzahl der Elemente 6 ist. Da in einen <a href="index_s.html#ixb100716"><font color=#000080><tt>Set</tt></font></a>
keine Elemente eingef&uuml;gt werden k&ouml;nnen, die bereits darin
enthalten sind, ist daf&uuml;r gesorgt, dass jede Zahl nur einmal
im Tipp auftaucht. Der Z&auml;hler <font color="#000077"><tt>doubletten</tt></font>
wird durch den R&uuml;ckgabewert <a href="index_f.html#ixb100234"><font color=#000080><tt>false</tt></font></a>
von <a href="index_a.html#ixb100727"><font color=#000080><tt>add</tt></font></a>
getriggert. Er z&auml;hlt, wie oft eine Zahl eingef&uuml;gt werden
sollte, die bereits enthalten war. Die Ausgabe des Programms k&ouml;nnte
beispielsweise so aussehen: 
<font color="#333300">
<pre>
29
17
16
35
3
30
Ignorierte Doubletten: 2
</pre>
</font>
<hr>
<table border=0 cellpadding=0 cellspacing=1 width="100%">
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="cover.html">&nbsp;Titel&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100003.html">&nbsp;Inhalt&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="search.html">&nbsp;Suchen&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="index.html">&nbsp;Index&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/index.html" onClick="this.href=getDocIndex()">&nbsp;DOC&nbsp;</a>
<td align="right">Handbuch der Java-Programmierung, 5. Auflage, Addison
Wesley, Version 5.0.1
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100097.html">&nbsp;&lt;&lt;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100100.html">&nbsp;&nbsp;&lt;&nbsp;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100102.html">&nbsp;&nbsp;&gt;&nbsp;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100107.html">&nbsp;&gt;&gt;&nbsp;</a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/api/index.html" onClick="this.href=getApiIndex()">&nbsp;API&nbsp;</a>
<td align="right">&copy; 1998, 2007 Guido Kr&uuml;ger &amp; Thomas
Stark, <a href="http://www.javabuch.de">http://www.javabuch.de</a>
</table>
<a name="endofbody"></a>
</body>
</html>