C散列表Set/Get void *唯一內存地址

-1

散列表在表中的每個條目處使用鏈接列表。哈希碼算法生成一個索引。哈希碼算法的輸入是來自鍵/值對的關鍵字。散列碼算法接受一個char *輸入並輸出一個整數索引。 Hashtable Get/Set方法可以通過使用void *和數據的大小來接受任何類型的輸入。爲了生成幾乎唯一的索引，輸入字符串必須是唯一的，但Set/Get函數需要彼此對應，以便如果在Set函數中鍵是「foobar」，則稍後使用「foobar」映射調用Get到相同的散列表索引。C散列表Set/Get void *唯一內存地址

問題是輸入是void *，需要一個唯一的字符串來生成一個索引，然後我唯一能想到的就是鏈接列表中節點中的密鑰的唯一內存地址的字符串表示將存儲在散列表中的索引處。

設定功能（部分示例代碼）

struct Node* node_to_set = Node_Create(entry->key, entry->data, entry->keysize, entry->datasize); 
void* key = Node_Get_Key(node_to_set); 
char string_key[256] = {'\0'}; 
int bytes = sprintf(string_key, "%p", key); 
int index = Hashtable_HashCode(hashtable->size, string_key);

獲取函數（即唯一的字符串是輸給外線來電）

//do not know what the memory address is because its in the table 
//searching for it would defeat the purpose of a constant time lookup

還有沒有其他的方法可以做到這一點使用無效*？

來源

2017-06-11 eat_a_lemon

我至少讀過三次這樣的內容，不得不承認我失去了什麼問題*是*。這聽起來像你正在使用鏈表的衝突鏈哈希表。一旦您獲得了給定鍵的哈希索引，您需要遍歷碰撞鏈來查找條目是否存在，以及分別取決於操作（set/get）添加，更新或獲取。等價性測試*必須*成爲關鍵算法的一部分。無論如何，不要真的關注你的問題，儘管它遲到了，所以它可能只是我。 – WhozCraig

有許多不同的哈希表實現，您的示例代碼可能適用於多個哈希表。通常，鏈接列表只有在索引發生衝突時纔會發揮作用。然後將索引中的鍵替換爲列表中的第一個節點，以解決該桶中的衝突。現在你關於* nul-terminating *唯一內存地址的一般問題是分開的。如果您將密鑰存儲在唯一的位置，則該地址的十六進制表示只能包含可以表示爲字符串中的字符的字符。所以我不明白你爲什麼不能嘗試。 –

@WhozCraig不，現在還不算太晚，而不僅僅是你，我又讀了一遍，得出了同樣的結論。 '：）' –

而不是使用內存地址的字符串表示傳遞給散列函數。我使用了獨特的解除引用值，因爲它是一個關鍵字。我通過將void *轉換爲一個無符號字符*來解除引用，然後將它傳遞給散列函數。

int index = Hashtable_HashCode(hashtable->size, (unsigned char*)entry->key); 

unsigned long Hashtable_HashCode(unsigned int size, unsigned char *str) { 
     if(str != NULL) { 
       unsigned long hash = 5381; 
       unsigned int c = 0; 
       while(c = *str++) { 
         hash = ((hash << 5) + hash) + c; 
       } 
       hash = hash % size; 
       hash = (hash < 0) ? hash * -1 : hash; 
       return hash; 
     } 
     return -1; 
}

來源

2017-06-11 16:06:17

C散列表Set/Get void *唯一內存地址

回答

相關問題