031、容器

Par @Martin dans le
Tags :

总览

学过 STL 的都应该知道容器的概念, Java 中也有这样的东西.

Java 中的容器有两大接口: CollectionMap;

Collection 又分为三个小接口: ListQueueSet.

ArrayList、HashSet 和 HashMap 分别是 List、Set 和 Map 的实现类, 这三种也是使用最广泛的三个类.

Collection

Collection 接口是 List、Set 和 Queue 接口的父接口, 它定义了可用于操作 List、Set 和 Queue 的方法(增、删、改、查).

List 是元素有序并且可以重复的集合, List 可以精确控制每个元素的插入位置, 或删除某个位置的元素.

ArrayList 是数组序列, 是 List 接口的一个重要实现类, 它的底层是由数组实现的.

Set 和 List 类似, 最大的不同就是 List 是可以有序并且可重复的, 而 Set 是无序并且不能重复的.

  • List 适合经常追加数据, 插入, 删除数据, 但随即取数效率比较低.
  • Set 适合经常地随即储存, 插入, 删除, 但是在遍历时效率比较低.

这个其实也没什么好记的了, 有 STL 基础, 学这个太简单, 上一份例子代码(附视频解说):

http://yunpan.cn/cQsGPx38k4ISg 访问密码 8bf2

视频解说

需要注意的是 Java 中的泛型不能是基本数据类型, 必须是其包装类, 如, ArrayList<Integer>.

Map 家族

Map 接口提供了一种映射关系, 其中的元素以键值对(key – value)的形式存储, 能够实现根据 key 快速查找 value(和 C++ 中的 stl::map 差不多).

Map 中的键值对以 Entry 类型的对象实例形式存在(stl::map 中是 value_type).

Map 中的键值对中的 key 值是不可重复的, value 值则可以, 这一点 stl::map 也是一样的, 同样的, stl 提供了 multimap 来实现 key 值可重复的 map, Java 也提供了 key 值可以重复的 map, 就是 IdentityHashMap.

Map 插入键值对的方法不同于上一篇中学过的 add 方法, 它使用的是 put 方法, 参数为 key 值 和 value 值.

Map 中常用的方法:

  • keySet(): 返回 Map 中包含的键的 Set.
  • values(): 返回 Map 中包含的值的 Connection.
  • entrySet(): 返回 Map 中包含的映射关系的 Set.

HashMap 类是 Map 接口的一个重要实现类, 也是最常用的, 基于哈希表实现.

HashMap 中的 Entry 对象是无序排列的.

Key 和 Value 都可以为 null, 但是一个 HashMap 只能有一个 key 为 null 的映射(因为 key 不能重复).

实例:

Collection 中的例子是一个学生选课的案例, 已经可以通过 List、Set 来管理备选课程, 现在继续为其添加功能, 通过 Map 进行学生信息管理, Key 为学生 ID, value 为学生对象.

http://yunpan.cn/cQAGwDcYmtdDP  访问密码 ce09

工具类

contains in Collection

  • contains: 判斷 Collection 中是否包含某元素, 包含返回 true
  • 判斷 Collection 中是否包含指定的所有元素

需要注意的是, contains 判斷的是內存地址是否相同, 如果新建一個元素, 它的值和 Collection 中的某個元素相同, 但因為它是新創建的, 和 Collection 中相同的那個元素指向的不是同一個地址, 因此也會返回 false, 那怎麼解決這個問題?

這裡 List 和 Set 的解決方法是不同的:

先看 List:
首先要知道 List 中 contains 的原理, contains 內部其實就是遍歷使用 equals 方法, equals 方法比較的是地址, 因此我們只要重寫 equals 方法就能解決這個問題, 之前說過 String 對象可以通過 equals 來判斷字符串值是否相等, 就是因為 String 類重寫了 equals 方法.

再看 Set:
Set 中 contains 的原理和 List 中的不一樣, Object 中還定義了一個 hashCode() 方法, 它返回對象的哈希碼值, 當我們調用 HashSet 中的 contains 方法時, 先調用的是 hashCode() 判斷對象哈希碼是否相同, 再調用 equals() 判斷.

这里补充下, 经过老师指点, 证明其判断流程应该是 o1.hash == o2.hash && ((o1 == o2) || (o1.equals(o2)))
先判断两个对象的 hash, 然后判断两个对象的地址(即 == 号), 然后才是判断 equals

hashCode() 是 jdk 根据对象的地址或者字符串或者数字算出来的 int 类型的数值.
在 SetMap 中, 由于 key 是不可以重复的, 它在判断 key 是不是重复的时候就判断了 hashcode 这个方法, 而且也用到了 equals 方法, 这里不可以重复是说 equals 和 hashcode 只要有一个不等就可以了!
所以简单来讲, hashcode 相当于是一个对象的编码, 就好像文件中的 md5, 他和 equals 不同就在于他返回的是 int 型的, 比较起来不直观, 我们一般在覆盖 equals 的同时也要覆盖 hashcode, 让他们的逻辑一致.
举个例子, 如果一個對象有姓名和性别兩個屬性, 我们想要的是, 如果兩個對象的姓名和性别相等, 就说兩个对象是相等的, 那么我們就要重寫 equals 方法, 讓它判斷姓名和性別, 同時還要重寫 hashcode 方法, 讓它也要返回姓名的 hashcode 值加上性别的 hashcode 值, 这样从逻辑上, equals() 和 hashcode() 就一致了.

Eclipse 提供了快捷重寫 hashCode() 和 equasl() 方法的功能, 在 [編輯] – [源碼] 裡就能找到.

contains in Map

  • containskey() 用來判斷 Map 中是否包含某個 key 值.
  • containsValue() 用來判斷 Map 中是否包含某個 value 值.

這兩個內部還是調用的 equals 和 hashcode 方法, 如果有特殊需求, 可以重寫這兩個方法.

indexOf

獲取 List 中某元素的最先出現的索引位置(下標), 失敗返回 –1, 它的內部也是調用 equals() 方法;

lastIndexOf

獲取 List 中某元素的最後出現的索引位置(下標), 失敗返回 –1, 它的內部也是調用 equals() 方法;

Collections

Collections 是 Java.util 中的一個工具類, 它提供了一個對 Collection 的操作.

Collections.sort()

排序, 默認是升序排序, 如果要對容器進行排序, 那麼容器裡的保存的對象必須實現 Comparable 接口, 具體應用參考 api 幫助.

  • Comparable 接口 -- 默認排序規則
  • Comparator 接口 -- 臨時比較規則

Comparable -- 可比较的

  • 实现该接口表示: 这个类的实例可以比较大小, 可以进行自然排序
  • 定义了默认的比较规则
  • 其实现类需实现 compareTo() 方法
  • compareTo() 方法返回正数表示大, 负数表示小, 0 表示相等

Comparator -- 比较工具接口

  • 用于定义_临时_比较规则, 而不是默认比较规则
  • 其实现类需要实现 compare() 方法
  • Comparator 和 Comparable 都是 Java 集合框架的成员

關於這兩個接口的用法可以參考網文:
Comparable接口的实现和使用

到這裡, Java 的集合框架的成員也就學習的差不多了.

迭代器

迭代器是一个对象, 它的工作是遍历并选择 Collection 中的对象, 而我们不必知道或者关心该 Collection 底层的结构.

  • 使用 next() 获得序列中的下一个元素
    • 迭代器的 next() 方法是自动向下取元素, 要避免出现 NoSuchElementException
    • 迭代器的 next() 方法返回值类型是 Object, 所以要记得类型换
  • 使用 hasNext() 检查序列中是否还有元素
  • 使用 remove() 将迭代器新返回的元素删除
import java.util.*;

public class SimpleIteration {

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(new Integer(0));
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(3));
        list.add(new Integer(4));

        Iterator<Integer> it = list.iterator();

        // iterator 方式遍历
        while (it.hasNext()) {
            Integer integer = it.next();
            System.out.print(integer + " | ");
        }
        System.out.println();

        // 泛型 for 遍历
        for (Integer integer : list) {
            System.out.print(integer + " | ");
        }
        System.out.println();

        // 删除元素
        System.out.println(list); // 输出原始的 list
        it = list.iterator(); // 重新赋值 iterator
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
        System.out.println(list);
    }
}

执行结果:

0 | 1 | 2 | 3 | 4 |
0 | 1 | 2 | 3 | 4 |
[0, 1, 2, 3, 4]
[]

如果只是希望遍历, 而并不打算修改 Collection 对象本身, 那么使用 foreach 语法会更简单.

TreeMap

TreeMap 中所有的元素都保持着某种固定的顺序, 如果你需要得到一个有序的结果你就应该使用 TreeMap(HashMap 中元素的排列顺序是不固定的).

TreeMap 中的元素将按照升序排列, 缺省是按照自然排序进行排列, 意味着 TreeMap 中的元素要实现 Comparable 接口, 或者有一个自定义的比较器, 可以在构造 TreeMap 对象时, 传递实现 Comparator 接口的比较器对象.
如果我们自己定义的一个类的对象要加入到 TreeSet 当中, 那么这个类必须要实现 Comparable 接口.

  • HashMap: 基于哈希表实现, 有调优选项
  • TreeMap: 基于红黑树实现, 没有调优选项, 因为该树总处于平衡状态.

  • HashMap: 适用于在 Map 中插入、删除和定位元素

  • Treemap: 适用于按自然顺序或自定义顺序遍历键(key)

HashMap 通常比 TreeMap 快一点(树和哈希表的数据结构使然), 建议多使用 HashMap, 在需要排序的 Map 时候才用 TreeMap.

TreeSet

TreeSet 是依靠 TreeMap 来实现的.

所以, 同 TreeMap, TreeSet 也是一个有序集合, TreeSet 中的元素将按照升序排列, 缺省是按照自然排序进行排列, 意味着 TreeSet 中的元素要实现 Comparable 接口, 或者有一个自定义的比较器, 可以在构造 TreeSet 对象时, 传递实现 Comparator 接口的比较器对象.

import java.util.Iterator;
import java.util.*;

public class TreeSetTest {
    public static void main(String[] args) {
        Set ts = new TreeSet();
        ts.add("abc");
        ts.add("xyz");
        ts.add("rst");
        Iterator it = ts.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

执行结果:

abc
rst
xyz

打印结果不是和先前加入的顺序一样, 它是按照一个字母的排序法进行排序的, 这是因为 String 类实现了 Comparable 接口;
同样的, 如果自己定义的一个类的对象要加入到 TreeSet 当中, 那么这个类必须要实现 Comparable 接口.

hashtable

hashtable 是线程安全的, 而 hashmap 是非线程安全的.

待完善.