[科普中國(guó)]-無(wú)序關(guān)聯(lián)容器

C++程序設(shè)計(jì)語(yǔ)言中，unordered_map、unordered_multimap、unordered_set、unordered_multiset是標(biāo)準(zhǔn)模板庫(kù)（STL）提供的一類無(wú)序關(guān)聯(lián)容器（unordered associative containers），是通過哈希表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。無(wú)序是指元素的名字（或者鍵值）的存儲(chǔ)是無(wú)序的；這與用平衡二叉樹實(shí)現(xiàn)的元素名字是有序存儲(chǔ)的“關(guān)聯(lián)容器”是相對(duì)概念。

歷史SGI的STL提供了hash_map,hash_set,hash_multimap,hash_multiset等類模板。由于其有用性，很快其它的C++編譯器也支持了這一特性，如GCC、libstdc++以及MSVC（在stdext命名空間）。

C++ TR1語(yǔ)言標(biāo)準(zhǔn)中提出了增加hash_*類模板，最終接受為unordered_*。Boost C++ Libraries也提供了一種實(shí)現(xiàn)。1

定制哈希函數(shù)定制的哈希函數(shù)的參數(shù)為到定制類型的const引用，返回類型為size_t1。

struct X{int i,j,k;};struct hash_X{ size_t operator()(const X &x) const{ return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k); }};定制哈希函數(shù)作為std::unordered_map的模板參數(shù)使用。

std::unordered_map my_map;或者通過特化std::hash來使用。

namespace std { template class hash{ public : size_t operator()(const X &x ) const{ return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k); } };}//... std::unordered_map my_map;標(biāo)準(zhǔn)模板庫(kù)標(biāo)準(zhǔn)模板庫(kù)（英文：Standard Template Library，縮寫：STL），是一個(gè)C++軟件庫(kù)，大量影響了C++標(biāo)準(zhǔn)程序庫(kù)但并非是其的一部分。其中包含4個(gè)組件，分別為算法、容器、函數(shù)、迭代器。

模板是C++程序設(shè)計(jì)語(yǔ)言中的一個(gè)重要特征，而標(biāo)準(zhǔn)模板庫(kù)正是基于此特征。標(biāo)準(zhǔn)模板庫(kù)使得C++編程語(yǔ)言在有了同Java一樣強(qiáng)大的類庫(kù)的同時(shí)，保有了更大的可擴(kuò)展性。1

散列表散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

一個(gè)通俗的例子是，為了查找電話簿中某人的號(hào)碼，可以創(chuàng)建一個(gè)按照人名首字母順序排列的表（即建立人名{\displaystyle x}到首字母{\displaystyle F(x)}的一個(gè)函數(shù)關(guān)系），在首字母為W的表中查找“王”姓的電話號(hào)碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字，“取首字母”是這個(gè)例子中散列函數(shù)的函數(shù)法則{\displaystyle F()}，存放首字母的表對(duì)應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。2

本詞條內(nèi)容貢獻(xiàn)者為:

李岳陽(yáng) - 副教授 - 江南大學(xué)