Java容器全面分析（续）

一、Set与Map

Set集合的继承体系：

Map集合的继承体系：

从上面的继承关系我们可以看出来，实现Map接口和Set接口的接口名、类名完全相似。

从上一篇博文的分析我们可以知道，Map集合的key具有一个特征：所有的key不能重复，且key之间没有顺序（TreeMap是有顺序的），如果将Map集合的所有key集中起来，那这些key就组成了一个set集合，则map集合提供了keySet()方法返回所有key组成的集合。这样就实现了Map到Set之间的转换。其实也可以实现Set到Map之间的转换。

下面简单实现一下将Set扩展成Map，自定义个一个SimpleEntry类，

代码如下：

package com.crazyit;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;

class SimpleEntry<K, V> implements Map.Entry<K, V>, java.io.Serializable {
	private final K key;
	private V value;

	public SimpleEntry(K key, V value) {
		this.key = key;
		this.value = value;
	}

	public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
		this.key = entry.getKey();
		this.value = entry.getValue();
	}

	public K getKey() {
		return key;
	}

	public V getValue() {
		return value;
	}

	public V setValue(V value) {
		V oldValue = this.value;
		this.value = value;
		return oldValue;
	}

	public boolean equals(Object o) {
		if (o == this) {
			return true;
		}
		if (o.getClass() == SimpleEntry.class) {
			SimpleEntry se = (SimpleEntry) o;
			return se.getKey().equals(getKey());
		}
		return false;
	}

	public int hashCode() {
		return key == null ? 0 : key.hashCode();
	}

	public String toString() {
		return key + "=" + value;
	}
}

public class Set2Map<K, V> extends HashSet<SimpleEntry<K, V>> {
	public void clear() {
		super.clear();
	}

	public boolean containsKey(K key) {
		return super.contains(new SimpleEntry<K, V>(key, null));
	}

	boolean containsValue(Object value) {
		for (SimpleEntry<K, V> se : this) {
			if (se.getValue().equals(value)) {
				return true;
			}
		}
		return false;
	}

	public V get(Object key) {
		for (SimpleEntry<K, V> se : this) {
			if (se.getKey().equals(key)) {
				return se.getValue();
			}
		}
		return null;
	}

	public V put(K key, V value) {
		add(new SimpleEntry<K, V>(key, value));
		return value;
	}

	public void putAll(Map<? extends K, ? extends V> m) {
		for (K key : m.keySet()) {
			add(new SimpleEntry<K, V>(key, m.get(key)));
		}
	}

	public V removeEntry(Object key) {
		for (Iterator<SimpleEntry<K, V>> it = this.iterator(); it.hasNext();) {
			SimpleEntry<K, V> en = (SimpleEntry<K, V>) it.next();
			if (en.getKey().equals(key)) {
				V v = en.getValue();
				it.remove();
				return v;
			}
		}
		return null;
	}

	public int size() {
		return super.size();
	}
}

总结：可以通过对Set加以改造，将Set变为Map，这个改造的Map集合在功能上几乎可以和系统提供的Map一样。

二、HashMap与HashSet分析比较：

1、HashMap与HashSet都是采用传统的Hash算法决定集合的存储位置，这样可以保证快速存、取集合元素。

注意：集合虽然说存储Java对象，但实际上不会真正将Java对象放入Set集合中，而只是在Set集合中保留这些对象的引用罢了。

对于HashMap、HashSet及其子类而言，它们采用了Hash算法来决定集合中元素的存储位置

当在创建HashMap的时候，有一个默认的负载因子，其默认值为0.75,，这是时间和空间成本上的一种折衷，增大负载因子就可以减少Hash表所占用的内存空间，但会增加查询数据的时间开销，而查询又是最频繁的操作。减小负载因子会提高数据查询的性能，但是增加Hash表所占用的内存空间。

2、对于HashSet，它是基于HashMap实现的，HashSet底层采用HashMap来保存所有的元素，因此HashSet的实现相对容易一些。

注意：HashSet的绝大部分方法都是通过调用HashMap来实现的，因此HashSet和HashMap两个集合在实现本质上是相同的。

如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖已有的集合元素。

下面我们看一个精彩的程序：

package com.crazyit;

import java.util.HashSet;
import java.util.Set;

public class HashSetTest {
	public static void main(String[] args) {
		Set<Name> s = new HashSet<Name>();
		s.add(new Name("li", "tianpeng"));
		System.out.println(s.contains(new Name("li", "tianpeng")));
	}
}

class Name {
	private String first;
	private String last;

	public Name(String first, String last) {
		this.first = first;
		this.last = last;
	}
}

打印出来的结果竟然是“false”，我们命名已经添加了一个new Name("abc","123")对象。

这是因为HashSet判断两个对象相等的标准除了要通过equals()方法比较返回true之外，还要两个对象的hashCode()返回值相等，而上面的程序没有没有重写Name类的hashCode()方法，两个Name对象的返回值并不相等，因此HashSet会把它们当成2个对象来处理。

下面重写了hashCode()方法：

package com.crazyit;

import java.util.HashSet;
import java.util.Set;

public class HashSetTest {
	public static void main(String[] args) {
		Set<Name> s = new HashSet<Name>();
		s.add(new Name("li", "tianpeng"));
		System.out.println(s.contains(new Name("li", "tianpeng")));
	}
}

class Name {
	private String first;
	private String last;

	public Name(String first, String last) {
		this.first = first;
		this.last = last;
	}

	public int hashCode() {
		return first.hashCode();
	}

	public boolean equals(Object o) {
		if (this == o)
			return true;
		if (o.getClass() == Name.class) {
			Name n = (Name) o;
			return n.first.equals(first);
		}
		return false;
	}
}

三、TreeMap与TreeSet比较分析：

1、TreeSet底层采用一个NavigableMap来保存TreeSet集合的元素，但是，由于NavigableMap只是一个接口，因此底层仍然使用TreeMap来包含集合中所有元素。

注意：TreeSet里绝大部分方法都是直接调用TreeMap的方法来实现的。

2、TreeMap则采用一种“红黑树”的排序二叉树来保存Map中的每一个元素，每个元素被当成“红黑树”的一个节点对待。

每次添加一个新元素时，此新元素作为“红黑树”的根节点被添加到已有的红黑树中。这样利用红黑树可以快速地插入与删除还有查找。

下面是TreeMap的应用程序：

package com.crazyit;

import java.util.TreeMap;

public class TreeMapTest {
	public static void main(String[] args) {
		TreeMap<String, Double> map = new TreeMap<String, Double>();
		map.put("ccc", 89.0);
		map.put("zzz", 89.0);
		map.put("aaa", 89.0);
		map.put("bbb", 89.0);
		System.out.println(map);
	}
}

关于红黑树的介绍：以后我们会慢慢提到。

总结：Treemap本质上就是一个“红黑树”，而TreeMap上的每一个元素就是该红黑树上的节点。

四、Map和List比较分析：

1、Map的values()方法，Map集合是一个关联数组，Map可以根据key来获取对应的value，所以这些value可以组成一个List集合。但是Map的values()方法并未返回一个List集合。

可以从下面的代码中看出：

package com.crazyit;

import java.util.HashMap;
import java.util.TreeMap;

public class MapValueTest {
	public static void main(String[] args) {
		HashMap<String, Double> scores = new HashMap<String, Double>();
		scores.put("语文", 89.0);
		scores.put("数学", 83.0);
		scores.put("英文", 84.0);
		System.out.println(scores.values());
		System.out.println(scores.values().getClass());
		TreeMap<String, Double> health = new TreeMap<String, Double>();
		health.put("身高", 173.0);
		health.put("体重", 171.0);
		System.out.println(health.values());
		System.out.println(health.values().getClass());
	}
}

可以看出来Map中values()方法返回的值的集合不是List对象。

2、TreeMap：与HashMap优点类似，TreeMap的values()方法返回同样的Values对象，但是此处的Values类是TreeMap的私有内部类，因为TreeMap是用“红黑树”实现的，所以此时Values类当然要考虑红黑树的一些特性。

总结：HashMap和TreeMap中的values()方法并未把Map中的value重新组合成一个包含元素的集合对象，这样可以大大降低系统的开销。

五、Map和List的分析比较：

Map与Set的底层结构很相似，从用法也有一些相似的地方：

（1）Map接口提供了get(K key)方法允许Map对象根据key取得value

（2）List接口提供了get(int index)方法允许List对象根据元素索引取得value

可以把List看成所有key都是int类型的Map，也可以把Map看成key可以是任何类型的List。

六、ArrayList和LinkedList分析比较：

在List集合的实现类中，主要有3种：ArrayList、Vector和LinkedList。其中Vector还有一个Stack子类，此Stack子类仅在Vector父类的基础上增加了5个方法，这5个方法就将一个Vector扩展成了Stack，实际从本质上来讲，Stack仍然是一个Vector，它只是比Vector多了5个方法罢了。

但实际上，Java不推荐使用Stack类，而使推荐使用Deque实现类，Java提供了一个Deque接口，并为该接口提供了一个ArrayDeque实现类，在无需保证线程安全的情况下，程序完全可以使用ArrayDeque来代替Stack类。

Deque接口代表双端队列这种数据结构，它既有队列FIFO的性质，也有栈FILO的性质。

1、Vector与ArrayList区别：

（1）从序列化机制来看，ArrayList的实现比Vector实现更安全

（2）但Vector是ArrayList的线程安全版本，Vector和ArrayList的绝大部分方法都是相同的，只是Vector的方法增加了synchronized关键字

注意：在多线程条件下使用List集合，而且需要保证List集合的线程安全，仍然可以不使用Vector，考虑将ArrayList包装成线程安全的集合类。Java提供了一个Collections工具类，通过该工具类synchronizedList方法可以将一个普通的ArrayList包装成线程安全的ArrayList。

2、ArrayList和LinkedList区别：

（1）ArrayList是一种顺序存储的线性表

（2）LinkedList是一种链式存储的线性表，其本质就是一个双向链表，因为它不仅实现了List接口，而且实现了Deque接口。

总结：ArrayList取数的性能优越，LinkedList插入、删除的性能优越。

七、Iterator迭代器：

下面看关于迭代器的几个代码：

package com.crazyit;

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListRemove {
	public static void main(String[] args) {
		ArrayList<String> list = new ArrayList<String>();
		list.add("111");
		list.add("222");
		list.add("333");
		Iterator<String> it = list.iterator();
		while (it.hasNext()) {
			String ele = it.next();
			if (ele.equals("222"))
				list.remove(ele);
		}
	}
}

下面再看一个代码：

package com.crazyit;

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListRemove {
	public static void main(String[] args) {
		ArrayList<String> list = new ArrayList<String>();
		list.add("111");
		list.add("222");
		list.add("333");
		Iterator<String> it = list.iterator();
		while (it.hasNext()) {
			String ele = it.next();
			if (ele.equals("333"))
				list.remove(ele);
		}
	}
}

package com.crazyit;

import java.util.Iterator;
import java.util.TreeSet;

public class ArrayListRemove {
	public static void main(String[] args) {
		TreeSet<String> set = new TreeSet<String>();
		set.add("111");
		set.add("222");
		set.add("333");
		Iterator<String> it = set.iterator();
		while (it.hasNext()) {
			String ele = it.next();
			if (ele.equals("333"))
				set.remove(ele);
		}
	}
}

再看下面的代码：

package com.crazyit;

import java.util.Iterator;
import java.util.TreeSet;

public class ArrayListRemove {
	public static void main(String[] args) {
		TreeSet<String> set = new TreeSet<String>();
		set.add("111");
		set.add("222");
		set.add("333");
		Iterator<String> it = set.iterator();
		while (it.hasNext()) {
			String ele = it.next();
			if (ele.equals("222"))
				set.remove(ele);
		}
	}
}

总结：

（1）实际上，对于ArrayList、Vector、LinkedList等List集合而言，如果正在遍历倒数第2个集合元素，使用List集合的remove()方法删除集合的任意一个元素并不会发生异常，当正在遍历其他元素时删除其他元素就会发生相关异常。

（2）对于TreeSet、HashSet等Set集合而言，当使用Iterator遍历它们时，如果正在遍历最后一个集合元素时，使用Set集合的remove()方法删除结婚的元素并不会引发异常，但是如果在遍历其他集合元素时删除其他元素，就会引发相关异常。

因为对于List集合，如果在遍历最后第2个元素时执行删除操作，则List调用Iterator对应的hashNext()方法判断已经没有下一个元素了，则不会取next()了。

而对于Set集合，在遍历最后一个元素时，此时遍历操作已经完成，删除Set中元素不会产生任何影响。

Java容器全面分析（续）,古老的榕树,5-wow.com