[TOC] ### hah_map ***** hash_map 不是標準的。筆者寫該文檔時本來想嘗試些一個 hash_map 例程，但發現自己用 Qt + MSVC2010 編譯器出現了編譯錯誤。網上原因好像說是 STL 加入標準C++之時，hash_map系列當時還沒有完全實現，所以很多平臺上雖然安裝了 g++ 編譯器，但不一定有 hash_map 的實現。所以如果有平臺移植的內容，盡量少用 hash_map。 ### map ***** #### map 容器屬性 * 關聯性： 關聯容器中的元素的參考地址指的是其 Key 值，而不是他們在容器中的絕對地址； * 有序性： 容器中的元素一直按照排序方式嚴格排序，所有插入元素都按照該順序排列； 映射： 每個元素中，一個 Key 值與一個映射值相關。Key 值是用來標識其主要內容是映射值的元素； * 唯一 Key 值： 容器中不存在同時擁有相同 Key 值的兩個元素； * 分配感知 (Allocator-aware)： map 容器使用分配器對象動態處理其存儲需求。 ` ` ### unordered_map ***** unordered\_map 是一種關聯容器，用于存儲由**關鍵值 (Key Value，以下稱為Key 值)**和**映射值 (Mapped Value，以下稱為映射值)**組成的元素，并且允許根據其 Key 值快速檢索各個元素。 `unordered_map`(等價于`hash_map`)和`map`類似，都是存儲的`key-value`的值，可以通過`key`快速索引到`value`。 不同的是`unordered_map`不會根據`key`的大小進行排序， unordered\_map 內部實現了一個 Hash 表，所以其元素的排列順序是雜亂無序的。 ` ` #### 容器屬性 * 關聯性 關聯容器中的元素的參考地址指的是其 Key 值，而不是他們在容器中的絕對地址； * 無序性 無序容器使用 Hash 表來組織元素，這些 Hash 表允許無序容器通過 Key 值快速訪問元素； * 映射 每個元素將一個 Key 值與映射值關聯起來，Key 值用于標識其主要內容是映射值的元素； * 唯一關鍵值 容器中不存在同時擁有相同 Key 值的兩個元素； * 分配器感知 map 容器使用分配器對象動態處理其存儲需求。 ` ` ### **unordered_map和map的區別在哪里** ***** `hash_map`，`unordered_map`本質是一樣的，只不過`unordered_map`被納入了C++標準庫標準。 1. map 內部數據的組織，基于紅黑樹實現，紅黑樹具有自動排序的功能，因此map內部所有的數據，在任何時候，都是有序的。 2. unordered_map(hash_map) 基于哈希表，數據插入和查找的時間復雜度很低，幾乎是常數時間，而代價是消耗比較多的內存。底層實現上，使用一個下標范圍比較大的數組來存儲元素，形成很多的桶，利用hash函數對key進行映射到不同區域進行保存。 3. 用法的區別就是，map的key需要定義operator<。 而unordered_map需要定義hash_value函數并且重載operator==。對于內置類型，如string，這些都不用操心。對于自定義的類型做key，就需要自己重載operator==或者hash_value()了。 ` ` ### 優缺點 ***** #### map： * 優點： 有序性：這是map結構最大的優點，其元素的有序性在很多應用中都會簡化很多的操作； 紅黑樹，內部實現一個紅黑書使得 map 的很多操作在 log n 的時間復雜度下就可以實現，因此效率非常的高； * 缺點： 空間占用率高，因為 map 內部實現了紅黑樹，雖然提高了運行效率，但是因為每一個節點都需要額外保存父節點，子節點以及紅/黑性質，使得每一個節點都占用大量的空間； 適用于具有順序要求的問題； #### hash_map： * 優點： hash_map 查找速度會比map快，而且查找速度基本和數據量大小無關，屬于常數級別（但不能說一定比 map 的 log n 級別快，因為 hash 函數本身也有耗時）； * 缺點： 空間占用多，如果對內存使用很嚴格，需要認真考慮是否使用 hash_map ；特別是當 hash_map 對象特別多時，更加難以控制； 適用于對效率要求較高的環境； #### unordered_map： * 優點： 內部實現了 Hash 表，所以查找速度很快； * 缺點： Hash 表的建立比較比較費時； 適用于查找問題； ### **紅黑樹和hash表的時間復雜度** ***** `紅黑樹`保證了一個穩定的動態操作時間，查詢、插入、刪除都是O(logN)，最壞和平均都是. `哈希表`的查詢時間雖然是O(1)，但是并不是`unordered_map`查詢時間一定比`map`短，因為實際情況中還要考慮到數據量，而且`unordered_map`的hash函數的構造速度也沒那么快.所以不能一概而論，應該具體情況具體分析。 ` `