Java JDK7源码-java.util.AbstractMap<K,V>

源码

1
package java.util;
2
import java.util.Map.Entry;
3
4
public abstract class AbstractMap<K,V> implements Map<K,V> {
5
6
    protected AbstractMap() {
7
    }
8
9
    // 查询操作
10
11
    /**
12
     * 实现接口:java.util.Map<K,V>
13
     */
14
    public int size() {
15
        return entrySet().size();
16
    }
17
18
    /**
19
     * 实现接口:java.util.Map<K,V>
20
     */
21
    public boolean isEmpty() {
22
        return size() == 0;
23
    }
24
25
    /**
26
     * 实现接口:java.util.Map<K,V>
27
     *
28
     * 本实现迭代entrySet()返回的set,搜寻值为value的entry
29
     * 若找到,则返回true
30
     * 若直到迭代结束也未找到,则返回false
31
     * 
32
     * 需要注意的是,本实现的时间复杂度为线性阶(基于map的大小)
33
     *
34
     * @throws ClassCastException value的类型与map不合
35
     * @throws NullPointerException value==null且map禁止包含null
36
     */
37
    public boolean containsValue(Object value) {
38
        Iterator<Entry<K,V>> i = entrySet().iterator();
39
        if (value==null) {
40
            while (i.hasNext()) {
41
                Entry<K,V> e = i.next();
42
                if (e.getValue()==null)
43
                    return true;
44
            }
45
        } else {
46
            while (i.hasNext()) {
47
                Entry<K,V> e = i.next();
48
                if (value.equals(e.getValue()))
49
                    return true;
50
            }
51
        }
52
        return false;
53
    }
54
55
    /**
56
     * 实现接口:java.util.Map<K,V>
57
     * 
58
     * 本实现迭代entrySet()返回的set,搜寻键为key的entry
59
     * 若找到,则返回true
60
     * 若直到迭代结束也未找到,则返回false
61
     * 
62
     * 需要注意的是,本实现的时间复杂度为线性阶(基于map的大小)
63
     * 许多实现均会重写本方法
64
     *
65
     * @throws ClassCastException key的类型与map不合
66
     * @throws NullPointerException key==null且map禁止包含null
67
     */
68
    public boolean containsKey(Object key) {
69
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
70
        if (key==null) {
71
            while (i.hasNext()) {
72
                Entry<K,V> e = i.next();
73
                if (e.getKey()==null)
74
                    return true;
75
            }
76
        } else {
77
            while (i.hasNext()) {
78
                Entry<K,V> e = i.next();
79
                if (key.equals(e.getKey()))
80
                    return true;
81
            }
82
        }
83
        return false;
84
    }
85
86
    /**
87
     * 实现接口:java.util.Map<K,V>
88
     * 
89
     * 本实现迭代entrySet()返回的set,搜寻键为key的entry
90
     * 若找到,则返回entry的值
91
     * 若直到迭代结束也未找到,则返回null
92
     *
93
     * 需要注意的是,本实现的时间复杂度为线性阶(基于map的大小)
94
     * 许多实现均会重写本方法
95
     *
96
     * @throws ClassCastException key的类型与map不合
97
     * @throws NullPointerException key==null且map禁止包含null
98
     */
99
    public V get(Object key) {
100
        Iterator<Entry<K,V>> i = entrySet().iterator();
101
        if (key==null) {
102
            while (i.hasNext()) {
103
                Entry<K,V> e = i.next();
104
                if (e.getKey()==null)
105
                    return e.getValue();
106
            }
107
        } else {
108
            while (i.hasNext()) {
109
                Entry<K,V> e = i.next();
110
                if (key.equals(e.getKey()))
111
                    return e.getValue();
112
            }
113
        }
114
        return null;
115
    }
116
117
118
    // 修改操作
119
120
    /**
121
     * 实现接口:java.util.Map<K,V>
122
     * 
123
     * 本实现总是会抛出UnsupportedOperationException
124
     *
125
     * @throws UnsupportedOperationException map不支持本方法
126
     * @throws ClassCastException key或value因其类型禁止被插入map
127
     * @throws NullPointerException key为null且map的键不允许为null 或 value为null且map的值不允许为null
128
     * @throws IllegalArgumentException key或value因其某些属性禁止被插入map
129
     */
130
    public V put(K key, V value) {
131
        throw new UnsupportedOperationException();
132
    }
133
134
    /**
135
     * 实现接口:java.util.Map<K,V>
136
     *
137
     * 本实现迭代entrySet()返回的set,搜寻键为key的entry
138
     * 若找到,则先使用entry.getValue方法得到它的值
139
     * 然后使用iterator的remove操作将entry自set中移除(当然,map中对应的键值对也被移除了)
140
     * 最后返回此前保留的值
141
     * 若直到迭代结束也未找到,则返回null
142
     * 
143
     * 需要注意的是,本实现的时间复杂度为线性阶(基于map的大小)
144
     * 许多实现均会重写本方法
145
     * 
146
     * 注意:若map包含key,且entrySet方法返回的set的iterator不支持remove方法
147
     * 则抛出UnsupportedOperationException
148
     *
149
     * @throws UnsupportedOperationException map不支持本方法
150
     * @throws ClassCastException key的类型与map不合
151
     * @throws NullPointerException key为null且map的键不允许为null
152
     */
153
    public V remove(Object key) {
154
        Iterator<Entry<K,V>> i = entrySet().iterator();
155
        Entry<K,V> correctEntry = null;
156
        if (key==null) {
157
            while (correctEntry==null && i.hasNext()) {
158
                Entry<K,V> e = i.next();
159
                if (e.getKey()==null)
160
                    correctEntry = e;
161
            }
162
        } else {
163
            while (correctEntry==null && i.hasNext()) {
164
                Entry<K,V> e = i.next();
165
                if (key.equals(e.getKey()))
166
                    correctEntry = e;
167
            }
168
        }
169
170
        V oldValue = null;
171
        if (correctEntry !=null) {
172
            oldValue = correctEntry.getValue();
173
            i.remove();
174
        }
175
        return oldValue;
176
    }
177
178
179
    // 批量操作
180
181
    /**
182
     * 实现接口:java.util.Map<K,V>
183
     * 
184
     * 本实现迭代m.entrySet()返回的set
185
     * 然后针对每次迭代的结果,均将键值对使用map.put方法存入map中
186
     * 
187
     * 注意:若map不支持put操作,且m!=null
188
     * 则抛出UnsupportedOperationException
189
     *
190
     * @throws UnsupportedOperationException map不支持本方法
191
     * @throws ClassCastException m中的某个key或value因其类型禁止被插入map
192
     * @throws NullPointerException m==null 或m中存在为null的key且map的键不允许为null 或 m中存在为null的value且map的值不允许为null
193
     * @throws IllegalArgumentException m中的某个key或value因其某些属性禁止被插入map
194
     */
195
    public void putAll(Map<? extends K, ? extends V> m) {
196
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
197
            put(e.getKey(), e.getValue());
198
    }
199
200
    /**
201
     * 实现接口:java.util.Map<K,V>
202
     * 
203
     * 注意:若entrySet()返回的set不支持clear操作
204
     * 则抛出UnsupportedOperationException
205
     *
206
     * @throws UnsupportedOperationException map不支持本方法
207
     */
208
    public void clear() {
209
        entrySet().clear();
210
    }
211
212
213
    // 视图
214
215
    /**
216
     * keySet,values会在第一次使用时初始化
217
     * 包含key或value的容器视图均只需要一份
218
     */
219
    transient volatile Set<K>        keySet = null;
220
    transient volatile Collection<V> values = null;
221
222
    /**
223
     * 实现接口:java.util.Map<K,V>
224
     * 
225
     * 本实现返回一个set,它是java.util.AbstractSet的子类
226
     * 该set的iterator是map.entrySet()的iterator的"包装对象"
227
     * 该set的size方法基于map.size()
228
     * 该set的contains(Object o)方法基于map.containsKey方法
229
     * 
230
     * 本方法所返回的set会在方法第一次被调用时创建
231
     * 随后再调用本方法时,均会返回同一个set
232
     * 
233
     * 本方法并未进行并发控制
234
     * 因此在并发环境下,如果复数个请求同时调用本方法
235
     * 并不能确保返回的set是唯一的
236
     */
237
    public Set<K> keySet() {
238
        if (keySet == null) {
239
            keySet = new AbstractSet<K>() {
240
                public Iterator<K> iterator() {
241
                    return new Iterator<K>() {
242
                        private Iterator<Entry<K,V>> i = entrySet().iterator();
243
244
                        public boolean hasNext() {
245
                            return i.hasNext();
246
                        }
247
248
                        public K next() {
249
                            return i.next().getKey();
250
                        }
251
252
                        public void remove() {
253
                            i.remove();
254
                        }
255
                    };
256
                }
257
258
                public int size() {
259
                    return AbstractMap.this.size();
260
                }
261
262
                public boolean isEmpty() {
263
                    return AbstractMap.this.isEmpty();
264
                }
265
266
                public void clear() {
267
                    AbstractMap.this.clear();
268
                }
269
270
                public boolean contains(Object k) {
271
                    return AbstractMap.this.containsKey(k);
272
                }
273
            };
274
        }
275
        return keySet;
276
    }
277
278
    /**
279
     * 实现接口:java.util.Map<K,V>
280
     * 
281
     * 本实现返回一个collection,它是java.util.AbstractCollection的子类
282
     * 该collection的iterator是map.entrySet()的iterator的"包装对象"
283
     * 该collection的size方法基于map.size()
284
     * 该collection的contains(Object o)方法基于map.containsValue方法
285
     * 
286
     * 本方法所返回的collection会在方法第一次被调用时创建
287
     * 随后再调用本方法时,均会返回同一个collection
288
     * 
289
     * 本方法并未进行并发控制
290
     * 因此在并发环境下,如果复数个请求同时调用本方法
291
     * 并不能确保返回的collection是唯一的
292
     */
293
    public Collection<V> values() {
294
        if (values == null) {
295
            values = new AbstractCollection<V>() {
296
                public Iterator<V> iterator() {
297
                    return new Iterator<V>() {
298
                        private Iterator<Entry<K,V>> i = entrySet().iterator();
299
300
                        public boolean hasNext() {
301
                            return i.hasNext();
302
                        }
303
304
                        public V next() {
305
                            return i.next().getValue();
306
                        }
307
308
                        public void remove() {
309
                            i.remove();
310
                        }
311
                    };
312
                }
313
314
                public int size() {
315
                    return AbstractMap.this.size();
316
                }
317
318
                public boolean isEmpty() {
319
                    return AbstractMap.this.isEmpty();
320
                }
321
322
                public void clear() {
323
                    AbstractMap.this.clear();
324
                }
325
326
                public boolean contains(Object v) {
327
                    return AbstractMap.this.containsValue(v);
328
                }
329
            };
330
        }
331
        return values;
332
    }
333
334
    public abstract Set<Entry<K,V>> entrySet();
335
336
337
    // 比较与哈希
338
339
    /**
340
     * 重写祖先类:java.lang.Object
341
     * 实现接口:java.util.Map<K,V>
342
     * 
343
     * 比较o与map的相等性
344
     * 若o同样是一个Map且o与map中存储的键值对均相等,则返回true
345
     * 更正式的说,如果满足如下条件,则可认为两个Map m1 m2相等:
346
     * m1.entrySet().equals(m2.entrySet())
347
     * 以这种方式设计的话,即便m1 m2的实现类不同,也可以正确的判断二者是否相等
348
     * 
349
     * 本实现的判断规则为:
350
     * 1.如果o是map本身,返回true
351
     * 2.如果o的类型不是Map,返回false
352
     * 3.如果o的长度与map不相等,返回false
353
     * 4.迭代map.entrySet方法返回的set,检查o是否包含所有的迭代出的entry,若存在不包含的情况,返回false
354
     * 5.若直至迭代结束也未找到不包含的情况,则返回true
355
     */
356
    public boolean equals(Object o) {
357
        if (o == this)
358
            return true;
359
360
        if (!(o instanceof Map))
361
            return false;
362
        Map<K,V> m = (Map<K,V>) o;
363
        if (m.size() != size())
364
            return false;
365
366
        try {
367
            Iterator<Entry<K,V>> i = entrySet().iterator();
368
            while (i.hasNext()) {
369
                Entry<K,V> e = i.next();
370
                K key = e.getKey();
371
                V value = e.getValue();
372
                if (value == null) {
373
                    if (!(m.get(key)==null && m.containsKey(key)))
374
                        return false;
375
                } else {
376
                    if (!value.equals(m.get(key)))
377
                        return false;
378
                }
379
            }
380
        } catch (ClassCastException unused) {
381
            return false;
382
        } catch (NullPointerException unused) {
383
            return false;
384
        }
385
386
        return true;
387
    }
388
389
    /**
390
     * 重写祖先类:java.lang.Object
391
     * 实现接口:java.util.Map<K,V>
392
     * 
393
     * 返回map的hash code值
394
     * 定义方式为:
395
     * map.entrySet()返回的set中的Entry的hash code之和
396
     * 
397
     * 这样的定义方式确保了对于任意Map而言,只要有
398
     * m1.equals(m2)
399
     * 即有
400
     * m1.hashCode()==m2.hashCode()
401
     * 遵循equals方法与hashCode方法的设计规范
402
     */
403
    public int hashCode() {
404
        int h = 0;
405
        Iterator<Entry<K,V>> i = entrySet().iterator();
406
        while (i.hasNext())
407
            h += i.next().hashCode();
408
        return h;
409
    }
410
411
    /**
412
     * 重写祖先类:java.lang.Object
413
     * 
414
     * 返回描述map的字符串
415
     * 该字符串最外侧是一组大括号{}
416
     * 其内部是由map中的键值对。顺序为map的entrySet的iterator返回的顺序
417
     * 相邻的键值对间以", "(逗号+空格)分割
418
     * 每组键值对的形式为:
419
     * key=value
420
     * key与value均会调用String类的valueOf(Object obj)方法转换为字符串
421
     */
422
    public String toString() {
423
        Iterator<Entry<K,V>> i = entrySet().iterator();
424
        if (! i.hasNext())
425
            return "{}";
426
427
        StringBuilder sb = new StringBuilder();
428
        sb.append('{');
429
        for (;;) {
430
            Entry<K,V> e = i.next();
431
            K key = e.getKey();
432
            V value = e.getValue();
433
            sb.append(key   == this ? "(this Map)" : key);
434
            sb.append('=');
435
            sb.append(value == this ? "(this Map)" : value);
436
            if (! i.hasNext())
437
                return sb.append('}').toString();
438
            sb.append(',').append(' ');
439
        }
440
    }
441
442
    /**
443
     * 重写祖先类:java.lang.Object
444
     * 
445
     * 返回map的浅拷贝
446
     * 即不会复制key与value本身
447
     */
448
    protected Object clone() throws CloneNotSupportedException {
449
        AbstractMap<K,V> result = (AbstractMap<K,V>)super.clone();
450
        result.keySet = null;
451
        result.values = null;
452
        return result;
453
    }
454
455
    /**
456
     * SimpleEntry与SimpleImmutableEntry均会调用的通用方法
457
     * 测试相等性,检查null
458
     */
459
    private static boolean eq(Object o1, Object o2) {
460
        return o1 == null ? o2 == null : o1.equals(o2);
461
    }
462
463
    // 注意:
464
    // 即便共享部分代码
465
    // 但SimpleEntry与SimpleImmutableEntry是明确不同的两个类
466
    // 不过共用的代码不多
467
    // 因此没必要再弄出个抽象类
468
469
    /**
470
     * Entry中存储着Map的键值对
471
     * 调用entry.setValue方法可以改变value
472
     * 本类用于辅助AbstractMap的子类构建map
473
     * (继承AbstractMap,构建map,最重要的一环就是entrySet方法的编写)
474
     */
475
    public static class SimpleEntry<K,V>
476
        implements Entry<K,V>, java.io.Serializable
477
    {
478
        private static final long serialVersionUID = -8499721149061103585L;
479
480
        private final K key;
481
        private V value;
482
483
        /**
484
         * 以key-value为键值对创建entry
485
         */
486
        public SimpleEntry(K key, V value) {
487
            this.key   = key;
488
            this.value = value;
489
        }
490
491
        /**
492
         * 使用传入entry的键值对创建新的entry
493
         */
494
        public SimpleEntry(Entry<? extends K, ? extends V> entry) {
495
            this.key   = entry.getKey();
496
            this.value = entry.getValue();
497
        }
498
499
        /**
500
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
501
         */
502
        public K getKey() {
503
            return key;
504
        }
505
506
        /**
507
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
508
         */
509
        public V getValue() {
510
            return value;
511
        }
512
513
        /**
514
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
515
         */
516
        public V setValue(V value) {
517
            V oldValue = this.value;
518
            this.value = value;
519
            return oldValue;
520
        }
521
522
        /**
523
         * 重写祖先类:java.lang.Object
524
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
525
         * 
526
         * 比较o与entry的相等性
527
         * 若o同样是Map Entry且o与entry代表的键值对相等,则返回true
528
         * 更正式的说,如果满足如下条件,则可认为两个entry e1 e2代表的键值对相等:
529
         * 
530
         * if (
531
         * e1.getKey()==null ? e2.getKey()==null : e1.getKey().equals(e2.getKey())
532
         * ) && (
533
         * e1.getValue()==null ? e2.getValue()==null : e1.getValue().equals(e2.getValue())
534
         * )
535
         * 
536
         * 以这种方式设计的话,即便e1 e2的实现类不同,也可以正确的判断二者是否相等
537
         */
538
        public boolean equals(Object o) {
539
            if (!(o instanceof Map.Entry))
540
                return false;
541
            Map.Entry e = (Map.Entry)o;
542
            return eq(key, e.getKey()) && eq(value, e.getValue());
543
        }
544
545
        /**
546
         * 重写祖先类:java.lang.Object
547
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
548
         * 
549
         * 返回entry的hash code值
550
         * 定义方式如下:
551
         * (
552
         * e.getKey()==null ? 0 : e.getKey().hashCode()
553
         * ) ^ (
554
         * e.getValue()==null ? 0 : e.getValue().hashCode()
555
         * )
556
         * 
557
         * 这样的定义方式确保了对于任意Entry而言,只要有
558
         * e1.equals(e2)
559
         * 即有
560
         * e1.hashCode()==e2.hashCode()
561
         * 遵循equals方法与hashCode方法的设计规范
562
         */
563
        public int hashCode() {
564
            return (key   == null ? 0 :   key.hashCode()) ^
565
                   (value == null ? 0 : value.hashCode());
566
        }
567
568
        /**
569
         * 重写祖先类:java.lang.Object
570
         * 
571
         * 返回描述entry的字符串
572
         * 本实现返回:
573
         * key=value
574
         */
575
        public String toString() {
576
            return key + "=" + value;
577
        }
578
579
    }
580
581
    /**
582
     * Entry中存储着Map的键值对,该键值对不可变
583
     * 本类不支持entry.setValue方法
584
     * 本类用于辅助AbstractMap的子类构建map,可以方便的返回线程安全的键值对快照
585
     * (继承AbstractMap,构建map,最重要的一环就是entrySet方法的编写)
586
     */
587
    public static class SimpleImmutableEntry<K,V>
588
        implements Entry<K,V>, java.io.Serializable
589
    {
590
        private static final long serialVersionUID = 7138329143949025153L;
591
592
        private final K key;
593
        private final V value;
594
595
        /**
596
         * 以key-value为键值对创建entry
597
         */
598
        public SimpleImmutableEntry(K key, V value) {
599
            this.key   = key;
600
            this.value = value;
601
        }
602
603
        /**
604
         * 使用传入entry的键值对创建新的entry
605
         */
606
        public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
607
            this.key   = entry.getKey();
608
            this.value = entry.getValue();
609
        }
610
611
        /**
612
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
613
         */
614
        public K getKey() {
615
            return key;
616
        }
617
618
        /**
619
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
620
         */
621
        public V getValue() {
622
            return value;
623
        }
624
625
        /**
626
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
627
         * 
628
         * 因SimpleImmutableEntry不可变
629
         * 则总是抛出UnsupportedOperationException
630
         *
631
         * @throws UnsupportedOperationException 总是抛出该异常
632
         */
633
        public V setValue(V value) {
634
            throw new UnsupportedOperationException();
635
        }
636
637
        /**
638
         * 重写祖先类:java.lang.Object
639
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
640
         * 
641
         * 比较o与entry的相等性
642
         * 若o同样是Map Entry且o与entry代表的键值对相等,则返回true
643
         * 更正式的说,如果满足如下条件,则可认为两个entry e1 e2代表的键值对相等:
644
         * 
645
         * if (
646
         * e1.getKey()==null ? e2.getKey()==null : e1.getKey().equals(e2.getKey())
647
         * ) && (
648
         * e1.getValue()==null ? e2.getValue()==null : e1.getValue().equals(e2.getValue())
649
         * )
650
         * 
651
         * 以这种方式设计的话,即便e1 e2的实现类不同,也可以正确的判断二者是否相等
652
         */
653
        public boolean equals(Object o) {
654
            if (!(o instanceof Map.Entry))
655
                return false;
656
            Map.Entry e = (Map.Entry)o;
657
            return eq(key, e.getKey()) && eq(value, e.getValue());
658
        }
659
660
        /**
661
         * 重写祖先类:java.lang.Object
662
         * 实现接口:java.util.Map<K,V>.Entry<K,V>
663
         * 
664
         * 返回entry的hash code值
665
         * 定义方式如下:
666
         * (
667
         * e.getKey()==null ? 0 : e.getKey().hashCode()
668
         * ) ^ (
669
         * e.getValue()==null ? 0 : e.getValue().hashCode()
670
         * )
671
         * 
672
         * 这样的定义方式确保了对于任意Entry而言,只要有
673
         * e1.equals(e2)
674
         * 即有
675
         * e1.hashCode()==e2.hashCode()
676
         * 遵循equals方法与hashCode方法的设计规范
677
         */
678
        public int hashCode() {
679
            return (key   == null ? 0 :   key.hashCode()) ^
680
                   (value == null ? 0 : value.hashCode());
681
        }
682
683
        /**
684
         * 重写祖先类:java.lang.Object
685
         * 
686
         * 返回描述entry的字符串
687
         * 本实现返回:
688
         * key=value
689
         */
690
        public String toString() {
691
            return key + "=" + value;
692
        }
693
694
    }
695
696
}

已整理层级关系

直接继承本类的类

本类直接实现的接口

综述

本类是Java集合框架中的一员。其中K,V分别是map中key与value的类型。提供了Map接口最小化,也是最基本的实现。

若需实现一个不可变的map,程序员只需继承本类,然后实现entrySet方法,该方法会返回map键值对的set视图。该set应基于java.util.AbstractSet进行设计,不能支持add或remove方法,它的iterator不能支持remove方法。

如需实现可变的map,在此基础上程序员还需实现本类的put方法(本类会抛出UnsupportedOperationException异常),同时entrySet().iterator()返回的iterator还需实现remove方法。

遵循Map接口的规范,通常来说,程序员需要实现两个构造函数:

  1. 创建一个空的map的无参构造函数
  2. 接收一个Map类型参数的构造函数,它会以入参为基础,创建一个类型为自身实现类的,由相同键值对(key-value)构成的新map

对于本类的非抽象方法,如果实现类认为有必要,均可以重写以达到更高的性能标准。