有沒有一種數據結構，查找、刪除和插入效率都比較高呢？

01-05

用於存放一個有序的數列，這個序列有插入（插入的位置不定，任意位置），有刪除，有查找，有不有什麼數據結構能夠高效的實現這三種操作呢？

看你要求的是在現實硬體上跑得快，還是在RAM上的複雜度低，還是在pointer machine上複雜度低。

三者的答案分別是：

Buffer tree

Van Emde Boas tree （有global ordering）或 Balanced BST / skip list （反之）

Balanced BST / skip list

對於後兩個問題，既然我們只說複雜度的話，那各種實現都沒有區別。

Buffer tree在數據足夠大的時候效果很好，不過query是batched的。不過通常也不會只有一兩個query，否則直接寫個數組就好了。如果你非要一個個query且立刻拿到返回值，就不行。

數據小的時候就不好說了，要看你多小了，100還是10000的規模，數據結構肯定是不一樣的。

Van Emde Boas tree

如果你的key是固定位長的整數類型，這個結構所有操作時間均為O(log log M)，與n無關。比平衡樹的O(log n)快。

不過如果不是定長整數，只提供比較器的話，那隻好用平衡樹/skiplist。

skiplist

b+tree 加 hashmap 。。。

其實難點是並發安全能力

balanced binary trees: avl tree, red-black tree, treap, splay tree...

skip-lists

judy array

b-tree

哈希表加一個雙鏈表。

其實這種結構很常見，例如說：memcached、其餘很多內存管理/內存資料庫、很多腳本語言的數組……

需要具體問題具體分析, 如果題主需要的查找操作僅僅是簡單的KV操作, 那麼Hash Table應該是最合適的了.

如果題主的查找操作包含了Seek, 也就是說要找一個Key的後繼, 那就需要二叉樹或者Skip List這種數據結構了.

說一下我的看法. 在並發訪問的條件下, 相比於二叉平衡樹, Skip List甚至有lock-free的實現, 所以我更傾向與使用Skip List.

具體實例:

HBase -&> 二叉平衡樹

LevelDB -&> Skip List(懶惰刪除)

二叉平衡樹，全都是lgn，效率比較高

數組

（最開始的答案就是這麼簡潔）

_______________________________________________

補充：數組最快，沒有之一

int[] fast = new int[2147483647];


// 插入x

fast[x]++; 
// 刪除x

if(--fast[x] &< 0)
    fast[x] = 0; 

// 查找是否存在x
return fast[x] &> 0;

// 有序輸出所有元素 for(int x = 0; x &< fast.length; x++) { int repeat = fast[x]; for(int i = repeat; --i &>= 0;) { println(i); } }

以上：有序的理解是數列中數字的順序

_______________________________________________

以下：有序如果按數列生成的順序理解（因為題主也沒說是啥順序。。。）

如果需求是以數列中數字為key高效查找、插入、刪除：

Java的LinkedHashMap，時間複雜度O(1)

原理——每個節點即加入哈希表也加入到一個鏈表裡

如果需求是以數列的位置為key高效查找、插入、刪除，抱歉，我想不到高效的數據結構

註：經 @羅啟盛提醒，注意到題主要求有序這個條件，HashMap並不能保證有序。

HashMap--在合理設置的情況下，HashMap在查找、刪除和插入都具有近似O(1)的複雜度，也正是由於這個原因，LevelDB等KV資料庫和NoSQL資料庫才選擇其作為其數據LRU cache的核心數據結構。另外，HashMap還可以通過簡單的修改實現引用計數功能和concurrent功能，因此，在工業界使用相當廣泛。

SBT / Weight Balanced Tree

如果我沒理解錯題主是想維護一個數組，但是可以按位置增刪查改

這種情況下SBT是一個好選擇，因為SBT可以很方便的查找整顆樹中第幾個元素在哪。

其他平衡樹結構加上Size域後也能完成這樣的操作，SBT優勢在於Size就是它的平衡信息。

此外跳躍表(SkipList)效率也很好，據說比平衡樹在實際應用中更快，但是我真的沒寫過(捂臉)，就不評價了。

hash table，每個slot掛一個AVL tree。在正常情況下(avg-case)可以獲得O(1+alpha)的runtime。(alpha=n/m, n是elements的總量，m是hash table 的slot數量)。簡直就是duang！

二叉平衡樹中的紅黑樹。有人做過研究，在各種二叉樹中性能是高的。貌似有篇論文講這個，不好意思，沒找到。

link hash。這兩個東西想辦法組合一下。

Treap

斐波那契堆

hash table，插入，刪除，查找的平均複雜度都是O(1)，就是空間複雜度高

二叉平衡樹。其實紅黑樹不一定是效率最高的，還有很多，比如奇怪的Size Balance Tree，AVL，沒有必要造輪子因為多數編程語言都有內建實現。如果你實在想造輪子可以從Treap學起。