什麼是重新哈希最快的方法？

從馬克·韋斯的數據結構與算法分析C++：什麼是重新哈希最快的方法？

/** 
* Rehashing for quadratic probing hash table. 
*/ 
void rehash() 
{ 
    vector<HashEntry> oldArray = array; 

    // Create new double-sized, empty table 
    array.resize(nextPrime(2 * oldArray.size())); 
    for(auto & entry : array) 
     entry.info = EMPTY; 

    // Copy table over 
    currentSize = 0; 
    for(auto & entry : oldArray) 
     if(entry.info == ACTIVE) 
      insert(std::move(entry.element)); 
}

好像不必通過去每一個元素在表中，並檢查看的真的很痛苦的操作，如果該元素處於活動狀態或不。特別是，有沒有一種實現只是通過插入元素的數量（而不是整個表格）呢？

來源

2016-04-08 blueman

鏈接的散列結構（其中條目也作爲雙向鏈接列表連接）將允許您直接遍歷元素而不是整個表格（並允許您按插入順序而不是任意順序遍歷表格）。這會起作用嗎？ – ShadowRanger

這將工作在一個封閉的哈希場景（我的目標）？作爲參考：打開哈希（單獨鏈接）：在打開的哈希中，鍵存儲在鏈接列表中，該列表附加到散列表的單元格中。封閉散列（Open Addressing）：在封閉散列中，所有的鍵都存儲在散列表本身中，而不使用鏈表。 – blueman

當插入元素的數量至少是表格大小的一半時，您只需重新哈希即可，因此檢查所有表格單元格的代價並不高。 –

參見Per-Ake Larson，Dynamic Hashing， CACM 1988年4月，第446-457頁。他描述了一個哈希系統，其中可以拆分存儲桶並且只有拆分存儲桶的哈希碼需要重新計算。

你會發現一個'C' version of it coded as an hsearch(3) replacement，在Usenet comp.sources.misc檔案1998年7月，由[email protected]（我）提供。此代碼隨後進入Berkeley DB和其他各種場所，包括OpenLDAP。對不起，我還沒有原始的源代碼，但我確實有一個Java實現。

來源

2016-04-08 02:34:03 EJP

你不使用開放散列（例如'p =＆q-> Next;'）嗎？關於封閉散列的問題（*「對二次探測散列表的重新散列」*） - 所以這些技術是完全不同的。 –

什麼是重新哈希最快的方法？

回答

相關問題