【STL】哈希表 uthash.h

散清單（Hash

table，也叫哈希表），是根據（Key

value）而直接通路在記憶體存儲位置的。線性表查找的時間複雜度為O(n）而平衡二叉樹的查找的時間複雜度為O(log(n))。無論是采用線程表或是樹進行存儲，都面臨面随着資料量的增大，查找速度将不同程度變慢的問題。而哈希表正好解決了這個問題。

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的位址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash)

函數 

函數f (key)常用的對應關系：

：取關鍵字或關鍵字的某個線性函數值為散列位址。即或，其中為常數（這種散列函數叫做自身函數）

：假設關鍵字是以r為基的數，并且哈希表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若幹數位組成哈希位址。

：取關鍵字平方後的中間幾位為哈希位址。通常在標明哈希函數時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合适，而一個數平方後的中間幾位數和數的每一位都相關，由此使随機分布的關鍵字得到的哈希位址也是随機的。取的位數由表長決定。

：将關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（舍去進位）作為哈希位址。

：取關鍵字被某個不大于散清單表長m的數p除後所得的餘數為散列位址。即, 。不僅可以對關鍵字直接取模，也可在、等運算之後取模。對p的選擇很重要，一般取素數或m，若p選擇不好，容易産生碰撞。

由于C語言中，并沒有對hash表這類的進階資料結構進行支援，即使在目前通用的C++中，也隻支援棧、隊列等幾個資料結構，對于map，其實是以樹結構來實作的，而不是以hash表實作。

uthash是一個C語言的hash表實作。它以宏定義的方式實作hash表，不僅加快了運作的速度，而且與關鍵類型無關的優點。

uthash使用起來十分友善，隻要将頭檔案uthash.h包含進去就可以使用。

目前，uthash的最新版本（1.9）支援如下平台：

Linux

  Mac OS X

Windows using vs2008 and vs 2010

Solaris

OpenBSD

      通常這足夠通用了。唯一的不足是在windows下，在uthash這舊版本中，并不支援vs2008和2010，而是支援MinGW。

 uthash支援：增加、查找、删除、計數、疊代、排序、選擇等操作。

在Cocos2d-x裡面有幾處使用的

複雜的用法就可以參考Cocos2d-x ActionManager 的應用了

此處貼出cpp源碼；