Java中的STL-Map
Java中的STL01-Map
要点
- Set的实现是基于Map的，HashSet是基于HashMap的，TreeSet是基于TreeMap的。
- Map的继承关系如下图所示
Map接口
public interface Map<K,V> { }
Map接口中的API
abstract void clear()
abstract boolean containsKey(Object key)
abstract boolean containsValue(Object value)
abstract Set<Entry<K, V>> entrySet()
abstract boolean equals(Object object)
abstract V get(Object key)
abstract int hashCode()
abstract boolean isEmpty()
abstract Set<K> keySet()
abstract V put(K key, V value)
abstract void putAll(Map<? extends K, ? extends V> map)
abstract V remove(Object key)
abstract int size()
abstract Collection<V> values()
- entrySet()返回键-值对的Set
- keySet()返回键的Set
- values()返回值的Collection
- Map中不能用重复的键，所以API中返回带有Key的都是用Set返回
Map.Entry接口
interface Entry<K,V> { }
Map.Entry保存Map中的键值对,具有的API如下
bstract boolean equals(Object object)
abstract K getKey()
abstract V getValue()
abstract int hashCode()
abstract V setValue(V object)
entry中提供了两种比较器，分别是按照Key比较、按照Value排序，具体实现如下
// 按照Key比较
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
// 按照Value比较
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
// 按照传入的Key比较器比较
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
// 按照传入的Value比较器比较
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
AbstractMap接口
public abstract class AbstractMap<K,V> implements Map<K,V> {}
常用主要API:
abstract Set<Entry<K, V>> entrySet()
void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
boolean equals(Object object)
V get(Object key)
int hashCode()
boolean isEmpty()
Set<K> keySet()
V put(K key, V value)
void putAll(Map<? extends K, ? extends V> map)
V remove(Object key)
int size()
String toString()
Collection<V> values()
Object clone()
AbstractMap实现了大部分Map的API，具体的Map如HashMap通过继承AcstractMap实现。
虽然说AbstractMap实现了部分的API，但是它的实现都是基于抽象方法的，不涉及具体的数据存储方法，下面列几个函数具体看一下。
- containsValue方法
public abstract Set<Entry<K,V>> entrySet();
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;
}
- AbstractMap中重写了equals方法，equals比较的是两个Map中的键值对是否相等。JDK源码如下。
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) 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;
}
可以看到，它的遍历查找是通过entrySet()函数的返回的Set，至于如何实现entrySet()这个函数，具体的Map实现方式不同。
- 重写了hashCode方法，AbstractMap方法规定，其hashCode的值等于其每个Entry的hashCode的和。
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
SortedMap接口
SortedMap是TreeMap的实现接口，同时也是NavigableMap的继承接口，所有实现此接口的具体Map类型的Key的类型都必须实现Comparator接口。
public interface SortedMap<K,V> extends Map<K,V> { }
主要API
// 继承于Map的API
abstract void clear()
abstract boolean containsKey(Object key)
abstract boolean containsValue(Object value)
abstract Set<Entry<K, V>> entrySet()
abstract boolean equals(Object object)
abstract V get(Object key)
abstract int hashCode()
abstract boolean isEmpty()
abstract Set<K> keySet()
abstract V put(K key, V value)
abstract void putAll(Map<? extends K, ? extends V> map)
abstract V remove(Object key)
abstract int size()
abstract Collection<V> values()
// SortedMap新增的API
abstract Comparator<? super K> comparator()
abstract K firstKey()
abstract SortedMap<K, V> headMap(K endKey)
abstract K lastKey()
abstract SortedMap<K, V> subMap(K startKey, K endKey)
abstract SortedMap<K, V> tailMap(K startKey)
NavigableMap接口
public interface NavigableMap<K,V> extends SortedMap<K,V> { }
主要API
abstract Entry<K, V> ceilingEntry(K key)
abstract Entry<K, V> firstEntry()
abstract Entry<K, V> floorEntry(K key)
abstract Entry<K, V> higherEntry(K key)
abstract Entry<K, V> lastEntry()
abstract Entry<K, V> lowerEntry(K key)
abstract Entry<K, V> pollFirstEntry()
abstract Entry<K, V> pollLastEntry()
abstract K ceilingKey(K key)
abstract K floorKey(K key)
abstract K higherKey(K key)
abstract K lowerKey(K key)
abstract NavigableSet<K> descendingKeySet()
abstract NavigableSet<K> navigableKeySet()
abstract NavigableMap<K, V> descendingMap()
abstract NavigableMap<K, V> headMap(K toKey, boolean inclusive)
abstract SortedMap<K, V> headMap(K toKey)
abstract SortedMap<K, V> subMap(K fromKey, K toKey)
abstract NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
abstract SortedMap<K, V> tailMap(K fromKey)
abstract NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
说明
NavigableMap除了继承SortedMap的特性外，它的提供的功能可以分为4类：
- 第1类，提供操作键-值对的方法。lowerEntry、floorEntry、ceilingEntry 和 higherEntry 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象。
- 第2类，提供操作键的方法。这个和第1类比较类似lowerKey、floorKey、ceilingKey 和 higherKey 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键。
- 第3类，获取键集。navigableKeySet、descendingKeySet分别获取正序/反序的键集。
- 第4类，获取键-值对的子集。
Dictionary
public abstract class Dictionary<K,V> {}
主要API
abstract Enumeration<V> elements()
abstract V get(Object key)
abstract boolean isEmpty()
abstract Enumeration<K> keys()
abstract V put(K key, V value)
abstract V remove(Object key)
abstract int size()