哪個更適合：哈希表或BST在序列化，併發性方面？

我認爲如果我們通過鏈接進行衝突解析，哈希表會更合適，因爲對於任何讀取或寫入操作，我們都必須獲取哈希表中該條目的鎖（索引&值），而我們會必須獲得整個BST的鎖定才能對其進行更新。哪個更適合：哈希表或BST在序列化，併發性方面？

我認爲我們需要鎖定整個BST結構，因爲想象我們必須在樹中插入一個新節點，我們首先必須遍歷到達正確的父節點（比如節點A），如果我們沒有獲得鎖定樹結構可能會改變，我們不得不重新開始。

在散列表的情況下，輸入總是散列到相同的位置，並且我們知道要鎖定哪個索引，這在BST的情況下是未知的。

請糾正我，無論我錯了，並幫助我找到正確的答案。

P.S：這是一個亞馬遜面試問題。

來源

2013-02-21 studying algorithms

你讀過[由Bronson等撰寫的高效併發BST研究論文]（http://ppl.stanford.edu/papers/ppopp207-bronson.pdf）？ – thiton 2013-02-21 08:49:10

我會讀那篇文章。謝謝 – 2013-02-21 19:31:16

我認爲就併發性而言，你所說的是正確的，而散列表將是更好的選擇，但在序列化方面我認爲BST會更好。這是因爲在BST中我們只有數據節點，但是在哈希表中，我們將擁有數據的鍵和值對，以及幾個沒有值的鍵。因此，與BST相比，序列化時需要更多的空間。

來源

2013-02-21 09:27:21 abhinav

您可以做一個混合解決方案。做一個哈希表，其中每個插槽是二叉樹。所以說1024個插槽，每個插槽都有一個二叉樹。散列上的衝突進入二叉樹，不需要在插入時鎖定所有內容，只需要更新樹。

此外，如果你使用原子操作和一些聰明，你可以通過完全避免鎖定使它更加併發。原子更新插入新節點，如果原子更新失敗，另一個線程添加一個節點，只需循環直到成功。

我已經做到了這一點https://github.com/exodist/GSD/tree/master/Structures

這是一個高度併發的哈希/樹混合。它使用原子操作，沒有互斥體。它可以旋轉插入，但不會阻止讀取或更新現有密鑰。它可以調整大小/平衡/等。您可以遍歷所有條目等。管理自己的內存，並具有用於重新計數鍵/值的回調。您還可以將一個詞典中的鍵鏈接到另一個詞典中，以便更新第一個鍵中的鍵可以更改第二個鍵的值。

這樣的設計其實有性能提高，當你在這個問題投入更多的線程：

（T）是許多線程如何，忽略MI，插槽是多少哈希插槽使用，並且行動是多少項目插入（由線程劃分它，看看每個線程多少）

./performance.run 
    T, MI, Slots,  Ops:  Insert Rebalance  Update  Resize  Lookup  Immute    
    4, 16, 1024, 5000000: 2.765500363 0.915232065 2.540659476 2.172654813 2.545409560 2.089993698 
13.029449975 
    4, 16, 32768, 5000000: 2.122459866 1.403548309 2.413483374 1.885083901 2.092272466 2.643681518 
12.560529434 
    4, 16, 1048576, 5000000: 1.700994809 1.063704010 2.030809367 2.457275707 1.453413924 3.671012425 
12.377210242 
    16, 16, 1024, 5000000: 0.785675781 2.311281904 1.805610753 0.621521146 0.549546473 0.744009412 
6.817645469 
    16, 16, 32768, 5000000: 0.497359638 0.316017553 1.257663142 0.610761414 0.390849355 0.825944608 
3.898595710 
    16, 16, 1048576, 5000000: 0.328308989 0.647632801 1.267230625 1.139402693 0.342399827 1.189220470 
4.914195405 
    64, 16, 1024, 5000000: 0.129407132 0.767262021 2.631929019 0.157977313 0.103848004 0.177964574 
3.968388063 
    64, 16, 32768, 5000000: 0.087656606 0.068330231 1.365794852 0.166261966 0.079112728 0.203542885 
1.970699268 
    64, 16, 1048576, 5000000: 0.074605680 0.284322979 1.372998607 0.650503349 0.084956938 0.828653807 
3.296041360

注：與8GB的內存的酷睿i7單次運行。在從舊__sync切換到__atomic的過程中使用gcc原子內置函數，這可能有助於提高內存模型的性能。

來源

2013-11-01 00:20:45 Exodist

哪個更適合：哈希表或BST在序列化，併發性方面？

回答

相關問題