无序关联式容器

无序关联式容器包含unordered_set、unordered_multiset、unordered_map、unordered_multimap 四种。它们的底层使用的数据结构都是哈希表。要学习它们的使用，也可以从：初始化、遍历、查找、 插入、删除、针对自定义类型等方面进行学习。但是首先需要学习关于哈希表的几个概念：哈希函数、 哈希冲突、解决哈希冲突的方法、装载因子(装填因子、负载因子)

哈希相关概念

哈希函数

是一种根据关键码key去寻找值的数据映射的结构，即：根据key值找到key对应的存储位置。

哈希函数的构造

• 定址法： H(key) = a * key + b
• 平方取中法： key^2 = 1234^2 = 1522756 ------>227
• 数字分析法：H(key) = key % 10000；
• 除留取余法：H(key) = key mod p (p <= m, m为表长)

哈希冲突

当两个不同的key值，通过哈希函数计算后，得到相同的存储位置，即:H(key1) = H(key2)，这种现象就叫做哈希冲突。

解决哈希冲突的方法

• 开放定址法
• 链地址法 (推荐使用这种，这也是STL中使用的方法)
• 再散列法
• 建立公共溢出区

装载因子

装载因子 a = (实际装载数据的长度n)/(表长m)

a越大，哈希表填满时所容纳的元素越多，空闲位置越少，好处是提高了空间利用率，但是增加了哈希碰撞的风险，降低了哈希表的性能，所以平均查找长度也就越长；但是a越小，虽然冲突发生的概率急剧下降，但是因为很多都没有存数据，空间的浪费比较大，经过测试，装载因子的大小在[0.5~0.75]之间比较合理，特别是0.75

设计思想

用空间换时间，注意数组本身就是一个完美的哈希，所有元素都有存储位置，没有冲突，空间利用率也达到极致。

类模板声明

#include <unordered_set>
template <class Key,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>,
          class Allocator = std::allocator<Key>>
class unordered_set;
template <class Key,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>,
          class Allocator = std::allocator<Key>>
class unordered_multiset;

// unordered_map与unordered_multimap位于#include <unordered_map>中
template <class Key,
          class T,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>,
          class Allocator = std::allocator<std::pair<const Key, T>>>
class unordered_map;
template <class Key,
          class T,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>,
          class Allocator = std::allocator<std::pair<const Key, T>>>
class unordered_multimap;

针对内置类型，初始化、遍历、查找、插入、删除、修改、下标访问这些与关联式容器类似，无序关联式容器中元素没有顺序，底层采用的是哈希表。

针对于自定义类型的操作

对于无序关联式容器而言，它们的模板参数中存在两个模板参数Hash与KeyEqual，它们针对的都是Key类型，而如果Key是自定义类型，我们就需要重新改写Hash与KeyEqual。

针对于模板参数Hash而言，改写的方式有两种：特化默认的参数std::hash或者自己实现一个行为类似std::hash的类，我们称之为函数对象。

namespace std {
    template <>
    class hash<类名> {
    public:
        size_t operator()(const 类名 &rhs) const // 注意返回类型确定了就是std::size_t
        {
            // 自己在此处实现hash函数
        }
    };
} // end of namespace std

struct HashPoint {
    size_t operator()(const 类名 &rhs) const // 注意返回类型确定了就是std::size_t
    {
        // 自己在此处实现hash函数
    }
};

针对于模板参数KeyEqual而言，改写的方式有三种：特化默认的参数std::equal_to、函数对象的形式、运算符重载。

namespace std {
    template <>           // 模板的特化
    struct equal_to<类名> // 特化类型的类名
    {
        bool operator()(const 类名 &lhs, const 类名 &rhs) const {
            // 比较lhs与rhs是不是相等，相等就返回true，否则就是false
        }
    };
} // end of namespace std

// 2、函数对象的形式
struct EqualToPoint {
    bool operator()(const T &lhs, const T &rhs) const {
        // 比较lhs与rhs是不是相等，相等就返回true，否则就是false
    }
};

// 3、运算符重载形式
bool operator==(const 类名 &lhs, const 类名 &rhs) {
    // 比较lhs与rhs是不是相等，相等就返回true，否则就是false
}

可以使用具体的例子Point进行测试：

class Point {
public:
    Point(int ix = 0, int iy = 0)
        : _ix(ix), _iy(iy) {
    }
    ~Point() {
    }
    double getDistance() const {
        return hypot(_ix, _iy);
    }
    int getX() const {
        return _ix;
    }
    int getY() const {
        return _iy;
    }

    friend std::ostream &operator<<(std::ostream &os, const Point &rhs);
    friend bool operator==(const Point &lhs, const Point
                                                 &rhs); // std::equal_to
private:
    int _ix;
    int _iy;
};

std::ostream &operator<<(std::ostream &os, const Point &rhs) {
    os << "(" << rhs._ix
       << ", " << rhs._iy
       << ")";
    return os;
}

// 改写模板参数Hash，使用模板的特化
namespace std {
    template <> // 模板的特化
    struct hash<Point> {
        size_t operator()(const Point &pt) const {
            return (pt.getX() << 1) ^ (pt.getY() << 1); // 哈希函数的设置
        }
    };
} // end of namespace std

// 改写模板参数Hash，使用函数对象的形式
struct PointHasher {
    size_t operator()(const Point &pt) const {
        cout << "PointHasher::opeator()(const Point &)" << endl;
        return (pt.getX() << 1) ^ (pt.getY() << 1);
    }
};

// 改写KeyEqual，使用模板的特化
namespace std {
    template <> // 模板的特化
    struct equal_to<Point> {
        bool operator()(const Point &lhs, const Point &rhs) const {
            return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
        }
    };
} // end of namespace std

// 改写KeyEqual，使用函数对象
struct EqualToPoint {
    bool operator()(const Point &lhs, const Point &rhs) const {
        return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
    }
};

// 改写KeyEqual，使用运算符重载
bool operator==(const Point &lhs, const Point &rhs) {
    return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
}

参考资料

• cppreference-容器库