close

Mr.Muzi

一只很安静的monkey

Java Map 02 - AbstractMap

字数统计: 3.1k 阅读时长: 14 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 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! -------------
 


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