《Java编程思想》之对象的集合（数组、List、Set、Map）二

上接：《Java编程思想》之对象的集合（数组、List、Set、Map）一

22、使用自己创建的类作为HashMap的“键”，需要同时覆盖hashCode()和equals()。原因如下：

1).默认的hashCode()继承自Object，它默认是使用对象的地址计算散列码。

因此即使俩个对象的实例的内容相同，对象的地址是不同的，所以默认的hashCode()得到的散列码是不同的。如下例子：

import java.util.HashMap;
import java.util.Map;
public class TestHashMap{
   private int id;
   public TestHashMap(int id){
      this.id = id;
   }
   public void func(){
      System.out.println(id);
   }
   public String toString(){
      return "TestHashcode#" + id;
   }
   public static void main(String[] args){
      TestHashMap testHashcode = new TestHashMap(2012);
      Map<Object, Object> hashMap = new HashMap<Object, Object>();
      hashMap.put(testHashcode, 2012);

      if(hashMap.containsKey(testHashcode)){
        System.out.println("找到id为：" + testHashcode.id+"的TestHashcode");
      }
      else{
        System.out.println("找不到id为：" + testHashcode.id+"的TestHashcode");
      }
      TestHashMap testHashcode1 = new TestHashMap(2012);
      if(hashMap.containsKey(testHashcode1)){
        System.out.println("找到id为：" + testHashcode1.id+"的TestHashcode");
      }
      else{
        System.out.println("找不到id为：" + testHashcode1.id+"的TestHashcode");
      } 
      System.out.println("--------------------------------");
      System.out.println("testHashcode散列码为:"+testHashcode.hashCode());
      System.out.println("testHashcode1散列码为:"+testHashcode1.hashCode());
   }
}

运行结果：

《Java编程思想》之对象的集合（数组、List、Set、Map）二

出现了“找到”与“找不到”这种尴尬的处境。

2).这时，自己覆盖Oject的hashCode(),在TestHashMap中添加：

public int hashCode(){
   return id;
}

再运行，结果如下：

《Java编程思想》之对象的集合（数组、List、Set、Map）二

3).这是因为HashMap使用equals()判断当前的“键”是否与表中存在的“键”相同，而默认equals()是继承自Object, Object中的Object.equals()只是比较对象的地址。于是再向TestHashMap添加：

public boolean equals(Object o){
   // o instanceofTestHashMap检查o是否是TestHashMap的实例
   return (o instanceof TestHashMap)
     && (id == ((TestHashMap)o).id);
}

运行结果:

《Java编程思想》之对象的集合（数组、List、Set、Map）二

综上：自定义的类，如果不为“键”覆盖hashCode()和equals()，那么在使用散列的数据结构是（HashSet、HashMap、LinkedHashSe，或LinkedHashMap），就无法正确处理你的“键“。

23、散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于“键“的查询速度，散列使用数组（存储一组元素最快的数据结构）来保存散列”键“信息。数组并不保持”键“本身，而是通过”键“对象生成一个数字，将其作为数组的小标。这个数字就是散列码，由定义在Object中的。且可能由你的类覆盖的hashCode()生成。为解决数组容量被固定的问题，不同的”键“可以产生相同的下标，出现冲突。

24、查询一个“值“：计算散列码，使用散列码查询数组。出现冲突，由“外部链接“处理，这时数组并不是直接保存”值“，而是保存”值“的list。然后对list中的”值“使用equals()方法进行线性的查询。

25、ArrayList底层由数组支持，而LinkedList是由双向链表实现的。因此，如果经常要在表中插入和删除元素，LinkedList就比较适合（LinkedList还有建立在AbstractSequentialList基础上的其他功能）；否则，应该使用速度更快的ArrayList。

26、树的行为方式是：它总是处于排序状态。TreeSet、HashMap都是排序好的。

27、只有在执行binarySearch()之前，才确实需要对List或数组进行排序。

28、总结：

1). 数组将数字与对象联系起来。它保存类型明确的对象，查询对象时，不需要对结果做类型转换。它可以是多维的，可以保存基本类型的数据。但是，数组一旦生成，其容量就不能改变。
2).Collection保存单个的元素，而Map保存相关联的键值对。
3).像数组一样，List也建立数字与对象的关联，可以认为数组和List都是排好序的容器。List能够自动扩充容量。但是List不能保存基本类型，只能保存Object的引用，因此必须对从容器中取出的Object结果做类型转换（RTTI）。
4).如果要进行大量的随机访问，就使用ArrayList；如果要经常从List中间插入或删除元素，则应该使用LinkedList。

5). 队列、双向队列以及栈的行为，由LinkedList提供支持。

6).Map是一种将对象与对象相关联的设计。HashMap着重于快速访问；TreeMap保持“键”始终处于排序状态，所以没有HashMap快。LinkedHashMap保持元素插入的顺序，也可以使用LRU（“最近最少使用“）算法对其重排序。
7). Set不接受重复元素。HashSet提供最快的查询速度，TreeSet保持元素处于排序状态。LinkedHashSet以插入顺序保存元素。
8).新程序中不应该使用过时的Vector、Hashtable和Stack。

以上内容整理自《Java编程思想》，若有遗漏，请您不吝指出！

秒客网

《Java编程思想》之对象的集合（数组、List、Set、Map）二

相关文章