JAVA基础知识之Map集合

时间:2021-10-12 23:54:02
  • Map的内部结构Entry
  1. Set与Map的关系
  2. Map的内部类Entry
  3. Map的通用方法及Map的简单用法
  • HashMap和HashTable的区别
  1. HashMap和HashTable判断元素相等的标准
  2. 可变对象对HashMap的影响
  • LinkedHashMap的特征
  • Properties 的特征
  • SortedMap接口和TreeMap类的特征
  • WeekHashMap
  • IdentifyHashMap与HashMap的区别
  • EnumMap的特征
  • 各种Map实现类的性能分析

Map的内部结构

Set和Map的关系

Map由key-value对组成,key不可以重复(因为无序),Map接口定义了一个Set keySet();方法用来返回所有key.即所有key组成了一个Set集合。

Map中key集合与集合容器Set非常相似,因此Map和Set的子集也非常相似,从名字上看,Set集合有HashSet, LinkeHashSet, SortedSet, TreeSet, EnumSet;而Map有HashMap, LinkedHashMap, SortedMap, TreeMap, EnumMap等子接口和实现类。Set和Map中的key集合的存储方式完全相同,从JDK源码来看,JAVA是先实现了Map, 然后包装一个value集为null的Map就实现了Set.

Map的内部类Entry

Map的内部有一个内部类Entry,用来封装key-value对。Entry中的部分方法,Object getKey(); Object getValue(); Object setValue(V value);下面是Map接口JDK源代码中的定义,

 public interface Map
{
public static interface Entry
{ public abstract Object getKey(); public abstract Object getValue(); public abstract Object setValue(Object obj); public abstract boolean equals(Object obj); public abstract int hashCode();
} ....

下面是Map接口的一个实现类HashMap, 可以看到HashMap的源码中,在内部类Entry中增加了几个私有成员,

 public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable
{
static class Entry
implements Map.Entry
{ ...... final Object key;
Object value;
Entry next;
int hash; //初始化内部类
Entry(int i, Object obj, Object obj1, Entry entry)
{
value = obj1;
next = entry;
key = obj;
hash = i;
}
} ......

当HashMap要put进新元素时,会初始化一个Entry类来保存key-value对。如下面的JDK源代码,

     public Object put(Object obj, Object obj1)
{
if(table == EMPTY_TABLE)
inflateTable(threshold);
if(obj == null)
return putForNullKey(obj1);
int i = hash(obj);
int j = indexFor(i, table.length);
for(Entry entry = table[j]; entry != null; entry = entry.next)
{
Object obj2;
if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2)))
{
Object obj3 = entry.value;
entry.value = obj1;
entry.recordAccess(this);
return obj3;
}
} modCount++;
addEntry(i, obj, obj1, j);
return null;
}

第22行会初始化一个Entry对象,

 ......
void addEntry(int i, Object obj, Object obj1, int j)
{
if(size >= threshold && null != table[j])
{
resize(2 * table.length);
i = null == obj ? 0 : hash(obj);
j = indexFor(i, table.length);
}
createEntry(i, obj, obj1, j);
}
......
void createEntry(int i, Object obj, Object obj1, int j)
{
Entry entry = table[j];
table[j] = new Entry(i, obj, obj1, entry);
size++;
}
......

Map接口中定义的方法及Map的简单用法

基本方法有get(Object obj), put(V value), remove(Object obj), putAll(Map map)...

其他方法,故名思议,

containsKey(Object obj);containsValue(Object obj);clear();equals(Object obj);

另外一些方法,解释如下,

public abstract Set keySet(); 返回该Map中所有key组成的Set集合
public abstract Collection values();返回该Map中所有value组成的collection集合
public abstract Set entrySet();返回Map中的所有Entry对象组成的Set集合,一个Entry对象是由key-value对组成。

下面是Map的一个简单用法,

 package collection.map;

 import java.util.HashMap;
import java.util.Map; public class Maps {
public static void main(String[] args) {
Map map = new HashMap();
map.put("a",1);
map.put("b",2);
map.put("c",3);
//key不同时,value可以重复
map.put("d",4);
System.out.println(map);
//key重复时,新的value会覆盖旧的value,同时返回旧的value
System.out.println(map.put("d", 5));
System.out.println(map);
System.out.println(map.containsKey("b"));
System.out.println(map.containsValue(3)); for(Object key : map.keySet()) {
//map.get(key)方法获取value
System.out.print(map.get(key)+",");
}
System.out.print("\n");
map.remove("c");
System.out.println(map);
}
}

执行结果,

 {d=4, b=2, c=3, a=1}
4
{d=5, b=2, c=3, a=1}
true
true
5,2,3,1,
{d=5, b=2, a=1}

HashMap和Hashtable

HashMap和Hashtable是Map的两个典型的实现类,它们之间的关系与HashSet和Vector完全类似。Hashtable是一个古老的Map实现类,虽然支持安全线程,但现在已经可以通过Collections工具类来同步容器的线程了,所以Hashtable用得非常少。

HashMap和HashTable判断元素相等的标准

与HashSet一样,HashMap和Hashtable判断元素是否相等的标准,也是需要同时满足两个key通过equals方法对比返回true,两个key的hashCode值要相等。在Map接口中已经定义了equals和hashCode方法,所以在HashMap和Hashtable中,必须重写这两个方法,且必须满足上面的规则。下面是一个例子,

 package collection.map;

 import java.util.HashMap;
import java.util.Hashtable; class A {
int count;
public A(int count) {
this.count = count;
}
//根据count的值来判断两个对象是否相等
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj != null && obj.getClass() == A.class) {
A a = (A)obj;
return this.count == a.count;
}
return false;
} //根据count值来计算hashCode
public int hashCode() {
return this.count;
}
} class B {
//重写equals, B与任何对象比较都返回true
public boolean equals(Object obj) {
return true;
}
} public class HashTables {
public static void main(String[] args) {
Hashtable ht = new Hashtable();
ht.put(new A(100), "a");
ht.put(new A(200), "b");
ht.put(new A(300), new B());
System.out.println(ht);
//只要两个对象通过equal比较返回true,Hashtable就认为它们的value相等
//由于此处Hashtable会调用value为B对象的equals做比较,所以总返回true,在HashMap中则返回false
//这也是Hashtable和HashMap底层containsValue方法的区别
System.out.println(ht.containsValue("test"));
//比较key则需要equal相等且hashCode相等
System.out.println(ht.containsKey(new A(300)));
System.out.println(ht.containsKey(new A(305)));
ht.remove(new A(200));
System.out.println(ht);
} }

执行结果,

 {collection.map.A@12c=collection.map.B@1b5998f, collection.map.A@c8=b, collection.map.A@64=a}
true
true
false
{collection.map.A@12c=collection.map.B@1b5998f, collection.map.A@64=a}

上面这个例子中可见,Hashtable判断两个元素是否相等(即判断Key是否相等)的标准是,即要equals返回true,又要hashCode相等,而Hashtable判断两个元素的value是否相等,只需要通过equals比较两个value是否返回true,并且这个equals是可以重载的。

可变对象对HashMap的影响

与HashSet类似的是,如果使用可变对象作为HashMap,Hashtable的key,如果程序修改了组成key的可变变量,则也可能会破坏HashMap和Hashtable,导致无法正常访问。

比如下面的例子,

 package collection.map;

 import java.util.HashMap;
import java.util.Iterator; class C {
int count;
public C(int count) {
this.count = count;
}
//根据count的值来判断两个对象是否相等
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj != null && obj.getClass() == C.class) {
C a = (C)obj;
return this.count == a.count;
}
return false;
} //根据count值来计算hashCode
public int hashCode() {
return this.count;
}
} public class HashMapErr {
public static void main(String[] args) {
HashMap hm = new HashMap();
hm.put(new C(100),1);
hm.put(new C(200), 2);
hm.put(new C(300), 3);
Iterator it = hm.keySet().iterator();
C first = (C)it.next();
System.out.println(first.count);
first.count = 500;
System.out.println(hm);
//key被修改后,对应的元素无法删除,元素也无法取出
hm.remove(new C(100));
System.out.println(hm);
System.out.println(hm.get(new C(1))); //未被修改的key对应的元素可以被删除
hm.remove(new C(200));
System.out.println(hm); }
}

执行结果,

 100
{collection.map.C@1f4=1, collection.map.C@c8=2, collection.map.C@12c=3}
{collection.map.C@1f4=1, collection.map.C@c8=2, collection.map.C@12c=3}
null
{collection.map.C@1f4=1, collection.map.C@12c=3}

LinkedHashMap的特征

HashSet有一个子类LinkedHashSet,与此类似的是HashMap有一个子类LinkedHashMap。 LinkedHashMap也是一个有序集合,其内部由一个双向链表来维护元素顺序(只需要维护key的顺序),默认顺序为插入元素的顺序,Map的迭代顺序也是根据此双向链表决定的。

LinkedHashMap因为要维护元素顺序,因此插入和删除的性能比起HashMap略低,但是迭代遍历的性能会更高。 下面是一个用LinkedHashMap迭代遍历的例子,

 package collection.map;

 import java.util.LinkedHashMap;
import java.util.Map; public class LinkedHashMaps {
public static void main(String[] args) {
Map lhm= new LinkedHashMap();
lhm.put("a", 1);
lhm.put("b", 2);
lhm.put("c", 3);
System.out.println(lhm);
lhm.remove("b");
lhm.put("b", 2);
System.out.println(lhm);
}
}

执行结果,

 {a=1, b=2, c=3}
{a=1, c=3, b=2}

Properties 的特征

Properties是Hashtable的一个子类,它的key和value都必须是String类型,它可以将一个Map对象和文件IO (inputStream, outputStream)关联起来,通过store(...)方法将Map对象的数据写入文件或者通过load(...)方法从文件读取数据写入Map. Properties还提供了以下方法,getProperty(...), setProperty(...)。下面是它的典型用法,

 package collection.map;

 import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Properties; public class Propertieses {
public static void main(String[] args) throws FileNotFoundException, IOException {
Properties pos = new Properties();
pos.setProperty("a", "1");
pos.setProperty("b", "2");
//write pos to output.txt
pos.store(new FileOutputStream("output.txt"), "here is a comment line"); Properties pos2 = new Properties();
pos2.setProperty("c", "3");
// read from output.txt and set to pos2
pos2.load(new FileInputStream("output.txt"));
System.out.println(pos2);
}
}

执行结果,

{b=2, a=1, c=3}

同时,output.txt中写入了pos的内容如下,

#here is a comment line
#Tue Nov 01 14:01:09 CST 2016
b=2
a=1

SortedMap接口和TreeMap类的特征

Set接口派生了一个SortedSet子接口,SortedSet 有一个实现类TreeSet, 与此类似的是,Map接口派生了一个SortedMap子接口,SortedMap子接口有一个实现类TreeMap. TreeMap底层是一个红黑树数据结构,每个节点就是一个key-value对,节点按照key进行排序,TreeMap中和TreeSet一样,也有两种排序方式,即自然排序(由元素实现Comparable控制排序逻辑)和定制排序(在TreeMap集合中传入一个排序逻辑Comparator), 由于前面已经多次提到这两种排序方式,下面直接给出例子,

 package collection.map;

 import java.util.TreeMap;

 class T implements Comparable {
int count;
public T(int count) {
this.count = count;
}
public String toString() {
return "T[count:"+count+"]";
}
public boolean equals(Object obj) {
if(this==obj) return true;
if(obj != null && obj.getClass() == T.class) {
T t = (T)obj;
return this.count == t.count;
}
return false;
}
@Override
public int compareTo(Object obj) {
T t = (T)obj;
return this.count - t.count;
}
} public class TreeMaps {
public static void main(String[] args) {
TreeMap tm = new TreeMap();
tm.put(new T(5), "a");
tm.put(new T(-3), "b");
tm.put(new T(9), "c");
System.out.println(tm);
System.out.println(tm.firstEntry());
System.out.println(tm.lastKey());
System.out.println(tm.higherKey(new T(-3)));
System.out.println(tm.lowerKey(new T(9)));
//return sub map
System.out.println(tm.subMap(new T(-3), new T(9)));
}
}

执行结果

 {T[count:-3]=b, T[count:5]=a, T[count:9]=c}
T[count:-3]=b
T[count:9]
T[count:5]
T[count:5]
{T[count:-3]=b, T[count:5]=a}

定制排序和HashSet中的定制排序一样,即在TreeMap初始化的时候,传入一个Comparator对象作为参数, 排序逻辑在Comparator中写。

从上面的例子中还可以看到,TreeMap判断两个元素相等的标准是,通过key进行equals比较返回true, 同时通过CompareTo比较key也要返回true。 因此在重写了key中的equals之后,一定要保证CompareTo方法也要返回跟equals一致的结果。

WeakHashMap

WeakHashMap是一种弱引用Map,意思是集合中的key对实际对象只有弱引用, 因此当垃圾回收了该key所对应的实际对象后, WeakHashMap会自动删除该key对应的key-value。 而HashMap是一种强引用,只要HashMap对象没被销毁,key所引用的对象是不会被垃圾回收器回收的,因此HashMap也不会自动删除key-value对。 下面的例子演示了WeakHashMap弱引用,

 package collection.map;

 import java.util.WeakHashMap;

 public class WeekHashMaps {
public static void main(String[] args) {
WeakHashMap wm = new WeakHashMap();
//new String("aa")是匿名对象, WeakHashMap只保留它的弱引用
wm.put(new String("aa"), 1);
wm.put(new String("bb"), 2);
//"cc"是字符串直接量,WeakHashMap保留它的强引用
wm.put("cc", 3);
System.out.println(wm);
//通知系统回收垃圾
System.gc();
System.runFinalization();
//前两个key-value元素将被删除,只能看到最后一个元素
System.out.println(wm);
}
}

执行结果,

 {cc=3, bb=2, aa=1}
{cc=3}

IdentifyHashMap

IdentifyHashMap与HashMap的实现机制基本相同,不同点是IdentifyHashMap判断两个元素(即两个key)相等的标准不同。HashMap要求两个元素的key通过equals对比返回true,通过hashCode返回的值也相等,则认为这两个元素相等; 而IdentifyHashMap判断两个元素相等的标准是, 当且仅当两个元素的key严格相等(key1 == key2)时,才认为两个元素相等。下面演示IdentifyHashMap的用法,

 package collection.map;

 import java.util.IdentityHashMap;

 public class IdentityHashMaps {
public static void main(String[] args) {
IdentityHashMap im = new IdentityHashMap();
im.put(new String("aa"),1);
im.put(new String("aa"),2);
System.out.println(im);
im.put("bb",3);
im.put("bb",4);
System.out.println(im);
}
}

可以看到,对于两个匿名对象new String("aa")的key,key1 != key2 ,因此IdentityHashMap会将它们看作不同的key,都添加进集合中。只有下面的两个常量字符串"bb",由于满足了key1==k2,所以IdentityHashMap只能添加其中一个(第二个覆盖了第一个),执行结果如下,

 {aa=2, aa=1}
{aa=2, aa=1, bb=4}

EnumMap的特征

EnumMap必须与枚举对象一起使用,EnumMap中所有key必须是单个枚举类的枚举值,EnumMap根据key的自然顺序维护集合顺序。EnumMap内部以数组形式保存,所以性能好。下面示范用法,

 package collection.map;

 import java.util.EnumMap;

 enum Season
{
SPRING, SUMMER, FALL, WINTER
} public class EnumMaps {
public static void main(String[] args) {
EnumMap em = new EnumMap(Season.class);
em.put(Season.SPRING, 1);
em.put(Season.SUMMER, 2);
System.out.println(em);
}
}

执行结果,

{SPRING=1, SUMMER=2}

各种Map实现类的性能分析

对于Map的两个常用实现类HashMap和Hashtable, 其实现机制几乎一样,但是Hashtable是一个古老,保证线程安全的集合,所以要比HashMap性能差。

TreeMap通常要比HashMap和Hashtable性能差,因为TreeMap底层要用红黑树来保持元素的顺序。

TreeMap的一个典型用法是,由于TreeMap中的key总是处于排序状态,可以用keySet()方法获取所有key, 接着用toArray()方法生成一个数组,再用Arrays工具类中的binaryArray()方法对已经排序的key数组进行快速查询对象。

对于一般情况,推荐使用HashMap,HashMap的查询速度也比较快(底层由object[]数组保存Entry对象),只是HashMap没有像TreeMap已经排好序的属性。

LinkedHashMap比HashMap要慢,因为它需要链表来保存元素的添加顺序(用来做集合迭代)。

IdentityHashMap与HashMap底层实现方式相似,性能上没有什么特别之处,只是两者判断元素是否相等的标准不同。

EnumMap的性能最好,但它只能使用同一个枚举类的值作为key.