純C實現從單個字符到指針的映射

我擁有較高級語言的編程經驗，並且幾星期前已經開始使用純C語言編寫代碼（出於學術原因）。我想實現一個類似於map<char,myStruct*>的數據結構。純C實現從單個字符到指針的映射

如果這還不夠清楚：我想爲每個可能的SINGLE char映射一個指向我定義的結構的指針。如果有辦法確保沒有2 char可以指向相同的struct（在將新元素插入到地圖上時不檢查其他每個char），但這並不是絕對必要的。我還需要能夠從地圖中刪除配對，並用相同的密鑰但不同的指針重新插入配對。我認爲這通過，並認爲我可以創建一個指針數組所有可能的字符的長度，並存儲相應的指針使用char作爲數組索引（因爲它只是一個數字常量）。這可能工作得很好，但如果我最終只在我的應用程序中使用幾個字符，那麼爲地址分配這麼多空間似乎是低效的。

儘管如此，我還是沒有想到任何其他的解決方案（考慮到我是一個C新手，並不令人驚訝）。如果有任何含糊不清的建議，我將很感激您的正確方向。

來源

2011-12-08 MHaaZ

我建議你看看Glib庫 - 它包括哈希和各種各樣的東西。你可以從他們那裏「偷走」一些想法。如果你想要「模板」，它會變得很難看，如果你想爲你的嚴格類型實現一個地圖，這並不難。純C「模板」或「泛型」背後的一般想法是告訴你的容器結構的「sizeof」並使用它。然後使用#defined'd宏在訪問特定類型時將其轉換爲特定類型。然後將實際的結構存儲器存儲爲char數組。 – Matej

其基本思想是使用對結構進行操作的函數。結構將需要知道它所表示的映射的某些內容：鍵的大小，存儲數據的大小，指向散列函數的指針（如果您希望它可配置）等等。我記得看到一些與斯坦福大學有關的YouTube視頻，並會看看我能否找到它們。 – Corbin

你想要什麼被稱爲哈希表。我的猜測是你的密鑰是一個字符串，所以這將是一個char *，而不是char（可以通過一個普通的'void * array [256];'來實現）。 – wildplasser

正如你說的（作爲一個評論者建議），最簡單的辦法就是隻是做數組與靜態的大小等於字符數據類型的最大值：

#include <limits.h> 
void * mapping[1u << CHAR_BIT];

假設64位指針和8位char s，這會佔用整個映射的8 * 256 = 2,048個字節的內存（當然不包括您存儲的「用戶數據」）。對於在64位系統上運行的程序來說，2 KB的內存是微不足道的，而且從我的角度來看，易於實現和加速可以很好地平衡浪費的內存。

如果你仍然想限制數組的「物理」大小，最簡單的做法是散列單個字符，但是你需要開始處理散列衝突，這會立即使它更加複雜。

你可以這樣做：

struct ValueChain 
{ 
    struct ValueChain *next; 
    void *value; 
    char key; 
} 

#define MAP_SIZE 127 /* This should be prime. */ 
struct ValueChain* mapping[MAP_SIZE];

這裏我們已經減半指針數組的大小，但每個值的成本有所增加。在插入衝突的值時，你也需要動態分配。

你可以進一步壓縮它，例如，

#define MAP_SIZE 31 
struct ValueChain mapping[MAP_SIZE];

在這裏，陣列中的每個值是一個完整的ValueChain「列表頭」，而不是僅僅一個指針到一個。在一臺64位機器上，mapping陣列可能會使用大約558字節，但在檢測到衝突之前，您不需要執行任何動態分配。

對於這些哈希可能只是const char key = myChar % MAP_SIZE;第一次近似，我猜。

來源

2011-12-08 12:44:08 unwind

非常感謝，這正是我所期待的。 – MHaaZ

我假設你的鑰匙是一個字符串。

那麼......如果你不需要自己實現這個，只需要don't。

理論上並不難。

創建一個包含鍵和值以及指向鏈接列表的可選指針的數組。

在訪問散列映射時，取出散列鍵的模數，這是數組中的位置。然後，您必須將未加密的密鑰與存儲的密鑰進行比較以檢測衝突。如果他們匹配，你發現它。如果沒有，則必須遍歷鏈表並比較鍵直到匹配。

顯然這是一個簡單的實現，你可以做更多的事情來節省內存和提高性能。

來源

2011-12-08 11:38:28 Mythli

我的鑰匙不是字符串。它是一個單一的字符，我不需要散列那些簡單的東西（我編輯標題以反映這一點）。 – MHaaZ

struct myStruct array[1u << CHAR_BIT]; 

#define uchar_to_mystruct_ptr(c) (c >=0 && c < (1u << CHAR_BIT) ? &array[c] : NULL)

來源

2011-12-08 13:09:54 wildplasser

但是這意味着爲每個可能存在的問題保留空間，即使它們相當大。我正在爲嵌入式系統工作，因此只想使用實際插入到映射中的（char，pointer）配對的內存。 – MHaaZ

所以你有*非常少的條目（比如10..20）？只需使用線性搜索（或二分搜索），使用具有{名稱，值}對的表格。 – wildplasser

我可能只有10個條目，但也有幾萬個。我只需要保持內存儘可能乾淨，並避免未使用的空間。 – MHaaZ

純C實現從單個字符到指針的映射

回答

相關問題