学步园

map集合简介

　　stl 和 util 都提供了 map 集合，关于 map 集合，类似的概念有：

• 散列表：《算法导论》中看到的，通过哈希函数将关键字映射到一个表（数组）中，检索速度很快。
• 关联数组：《编程珠玑II》中看到的，普通数组是通过整型下标来索引的，而关联数组则可用字符串或其他类型来索引。

　　总之，map 集合是一个存储着多个 键——值 对的集合。

　　stl 中的 map 可当做关联数组来用：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    map<string, int> grades;

    grades["李雷"] = 90;
    grades["韩梅梅"] = 95;
    grades["邻居家的孩子"] = 100;

    cout<<grades["邻居家的孩子"]<<endl;

    return 0;
}

java中的map集合

　　java 中主要有两个 map 集合：HashMap、TreeMap：

• HashMap 是利用关键字的 hashCode 函数返回的哈希值来做映射的。HashMap 通过链接法解决碰撞，也就是说如果两个 键——值对 哈希映射到一个槽的时候，就都添加到那个槽的链表中，这样处理过于简单，但一般情况下索引的复杂度是O(1)。
• TreeMap 是利用关键字建立一棵红黑树，索引复杂度是O(lg n)，而且是按照关键字有序的：有提供 lowerKey、higherKey 这样的函数，而 HashMap 是无序的。

map的一个应用

　　map 集合比较复杂，我也从来没有实现过，不过既然知道有人实现好了，那我们也就不用客气了O(∩_∩)O

　　检测一个集合是否包含另一个集合的所有元素是一个比较纠结的问题，我们立刻能想出一个 O(n^2) 的算法：

// A 是否包含 B 的所有元素
boolean containsAll(int[] A, int[] B) {
    for (int b : B) {
        boolean in = false; // A是否包含b?

        for (int a : A)
            if (a == b) {
                in = true;
                break;
            }

        if (!in)
            return false;
    }
    return true;
}

　　考虑到我们有了 map 集合，map 集合能很快地查找一个关键字(HashMap是O(1)，TreeMap是O(lg n)，都比遍历查找的O(n)要好很多)，于是我们可以写出如下算法：

// A 是否包含 B 的所有元素, 算法中用到了 map 集合
boolean containsAll_useMap(int[] A, int[] B) {
    Object exist = new Object();// 标志存在的对象
    Map<Integer, Object> Amap = new HashMap<Integer, Object>();
    for (int a : A)
        Amap.put(a, exist);

    for (int b : B)
        // A中存在的元素, get会返回exist, 不存在的返回 null
        if (Amap.get(b) == null)
            return false;

    return true;
}

　　这个算法在不刻意刁难的情况下复杂度是 O(n)。