Java Map 02 - AbstractMap

  关于 java.util.AbstractMap<K, V> 的部分笔记,提供了对Map接口的最小实现。本文演示代码段的执行环境基于JDK版本1.7

概述

  AbstractMap提供了关于Map接口的一个最小规模实现。

  如果需要实现一个不可修改的map集合,开发人员只需要继承AbstractMap类并提供一个entrySet方法的实现。该方法以set集合形式返回了当前map集合的键值对映射,返回的set集合不支持add和remove方法,对应的迭代器也不支持remove操作。

  如果需要实现一个可修改的map集合,需要额外实现put方法,且返回的迭代器类需要实现remove方法。

  AbstractMap类的方法可以在需要提升性能的情况下被子类覆盖重新实现。

继承关系

1
2
3
// AbstractSet<E>
--java.lang.Object
--java.util.AbstractMap<K,V>

实现接口

类名 实现接口
AbstractMap<E> Map<K,V>

AbstractMap

Constructor Summary

protected AbstractMap()

1
2
protected AbstractMap() {
}

  默认构造函数。采用protected修饰的原因是因为AbstractMap不直接用于集合的初始化操作,而是在使用真正可用的Set集合处理类时提供一些基础准备工作。所以这个方法不应该暴露到外界去,所以不能用public修饰。同样的原因,因为AbstractMap不涉及到单例模式的设计,所以也不会是private,这样其子类也没办法继承到父类的无参构造方法。所以综上考虑,protected是最理想的选择。

部分方法

public int size()

1
2
3
public int size() {
return entrySet().size();
}

  返回当前map集合中存储的键值对数量,如果超过了Integer的最大值(MAX_VALUE)那么就返回MAX_VALUE。

public boolean isEmpty()

1
2
3
public boolean isEmpty() {
return size() == 0;
}

  如果当前map集合不包含任何键值对,那么返回true。

public boolean containsValue(Object value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}

  判断当前集合是否存储val为value的键值对映射。如果当前集合中存储了一个及以上val为value的键值对,那么就返回true,否则返回false。整个过程需要O(n)time,n为当前集合中存储的元素数量。方法采用equals()方法完成元素相等检查。

public boolean containsKey(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean containsKey(Object key) {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}

  判断当前集合是否存储key为入参key的键值对映射。如果当前集合中存储了一个及以上key为入参key的键值对,那么就返回true,否则返回false。整个过程需要O(n)time,n为当前集合中存储的元素数量。方法采用equals()方法完成元素相等检查。

public V get(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}

  从当前集合中查找并返回key为入参key的键值对映射中含有的value。如果集合中未存储key为入参key的键值对映射,那么返回null。整个过程需要O(n)time,n为当前集合中存储的元素数量。方法采用equals()方法完成元素相等检查。

public V put(K key, V value)

1
2
3
public V put(K key, V value) {
throw new UnsupportedOperationException();
}

  向当前map集合中插入一个key-value键值对。当前类不支持该操作,抛出异常。

public V remove(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}

V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}

  从当前map集合中删除入参key的键值对映射,并返回映射对应的value值。第2 ~ 16行代码用来查找集合中对应于入参key的键值对映射,如果找到一个,那么就退出循环执行删除操作。第19 ~ 22行代码得到要删除的键值对映射的value值,并利用迭代器删除该键值对映射,最后返回value值。

public void putAll(Map<? extends K, ? extends V> m)

1
2
3
4
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}

  当前集合m中的键值对映射逐个保存到当前map集合中。底层调用的是put(K key, V value)方法,在AbstractMap中不支持插入操作,所以会抛出异常。

public void clear()

1
2
3
public void clear() {
entrySet().clear();
}

  清空当前map集合中存储的所有键值对映射。

public Set<K> keySet()

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
public Set<K> keySet() {
if (keySet == null) {
keySet = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();

public boolean hasNext() {
return i.hasNext();
}

public K next() {
return i.next().getKey();
}

public void remove() {
i.remove();
}
};
}

public int size() {
return AbstractMap.this.size();
}

public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}

public void clear() {
AbstractMap.this.clear();
}

public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
}
return keySet;
}

  返回当前map集合中存储的键值对映射的key值集合。该内容会在方法第一次被调用时创建,如果在方法调用时该内容已经存在,那么不做任何处理。

  对该集合做的操作会同步出现在map集合上,反之亦然。该返回集合支持remove操作,操作后的执行效果是将map集合中对应的键值对删除。

public Collection<V> values()

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
public Collection<V> values() {
if (values == null) {
values = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();

public boolean hasNext() {
return i.hasNext();
}

public V next() {
return i.next().getValue();
}

public void remove() {
i.remove();
}
};
}

public int size() {
return AbstractMap.this.size();
}

public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}

public void clear() {
AbstractMap.this.clear();
}

public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
}
return values;
}

  返回当前map集合中存储的键值对映射的value值集合。该内容会在方法第一次被调用时创建,如果在方法调用时该内容已经存在,那么不做任何处理。

  对该集合做的操作会同步出现在map集合上,反之亦然。该集合支持remove操作,删除操作后的执行结果是将当前map集合中对应的键值对删除。

public abstract Set<Entry<K,V>> entrySet()

1
public abstract Set<Entry<K,V>> entrySet();

  需要子类实现的抽象方法,用来返回当前map集合的键值对映射的set集合。

public boolean equals(Object o)

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
public boolean equals(Object o) {
if (o == this)
return true;

if (!(o instanceof Map))
return false;
Map<K,V> m = (Map<K,V>) o;
if (m.size() != size())
return false;

try {
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}

return true;
}

  判断对象o和当前map是否相等。如果o也是一个map且两个map拥有相同的键值对(数量一致,内容一致),那么方法返回true。

  方法会首先检查o是否是当前map自身,如果是,直接返回true。然后检查o是否是一个map,如果不是返回false。如果是,那么检查o存储的键值对数量和当前map集合是否一致,如果不一致返回false。数量校验处理完后检查两个map中的每个键值对的key和value是否存在不一致的结果,如果存在返回false。所有的检查都通过后,认为两个map相等,返回true。

  在整个过程中通过equals()方法完成相等比较。

public int hashCode()

1
2
3
4
5
6
7
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}

  返回当前map集合的hashcode值。map的hashcode值由map中所有键值对实例的hashcode值求和得到。Entry对象的hashcode计算规则是:

(e.getKey() == null ? 0 : e.getKey().hashCode()) ^

(e.getValue() == null ? 0 : e.getValue().hashCode())

对key的hashcode和value的hashcode求异或运算。

public String toString()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";

StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}

  返回当前map集合的String表示形式。所有的键值对内容被“{}”包围,每个键值对之间用“,”分隔,单个键值对以“=”连接键和值。

protected Object clone()

1
2
3
4
5
6
protected Object clone() throws CloneNotSupportedException {
AbstractMap<K,V> result = (AbstractMap<K,V>)super.clone();
result.keySet = null;
result.values = null;
return result;
}

  将当前AbstractMap集合复制一份并返回。执行的是浅度复制,且只复制map集合本身,内部的键值对不会被复制。

private static boolean eq(Object o1, Object o2)

1
2
3
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}

SimpleEntry<K,V>

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
public static class SimpleEntry<K, V> implements Entry<K, V>, java.io.Serializable {
private static final long serialVersionUID = -8499721149061103585L;

private final K key;
private V value;

/**
* 初始化一个map集合中键值对实体
*/
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}

/**
* 初始化一个map集合中键值对实体
*/
public SimpleEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}

/**
* 获取实体的key值
*/
public K getKey() {
return key;
}

/**
* 获取实体的valu值
*/
public V getValue() {
return value;
}

/**
* 设置当前实体的value值并返回被替换的值。
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}

/**
* 判断对象o和当前实体是否相等
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}

/**
* 计算当前实体的hashcode值,根据key的hashcode和value的hashcode做异或运算。
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}

/**
* 返回当前实体的string表示形式。
*/
public String toString() {
return key + "=" + value;
}

}

SimpleImmutableEntry<K, V>

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
public static class SimpleImmutableEntry<K, V>
implements Entry<K, V>, java.io.Serializable {
private static final long serialVersionUID = 7138329143949025153L;

private final K key;
private final V value;

/**
* 初始化一个不可修改value值的键值对实体
*/
public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
}

/**
* 初始化一个不可修改value值的键值对实体
*/
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}

/**
* 获取当前实体的key值
*/
public K getKey() {
return key;
}

/**
* 获取当前实体的value值
*/
public V getValue() {
return value;
}

/**
* 实体valu值不可修改,抛出异常
*/
public V setValue(V value) {
throw new UnsupportedOperationException();
}

/**
* 计算对象o和当前实体是否相等
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}

/**
* 计算当前实体的hashcode值,根据key的hashcode和valu的hashcode求异或运算。
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}

/**
* 返回当前实体的String表示形式。
*/
public String toString() {
return key + "=" + value;
}

}

涉及基础知识点

  1. NIL

参考文献

  1. NIL




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Map 02 - AbstractMap
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-AbstractMap.html