問題：

 

吳老師，這些數據結構之所以這麼來設計， 除了可以抽象出很多事物的共性以外，是不是還因為更適合機器的處理方式呢？

 

吳軍：

 

這個問題問得很好！對這個問題簡單的回答是肯定的，即數據結構的出現和計算機本身工作的方式有關。今天演化出來的很多數據結構， 甚至和圖靈機的原理，以及計算機底層的馮．諾依曼結構也有關。比如鏈表這種數據結構， 就和圖靈機的設計直接相關。

 

世界上很多抽象化的結果，都和我們人容易掌握的工具有關。比如我們將大部分零件做成圓形的，或者有圓形的切割和開口，主要是因為圓形好加工。我過去做過金屬工藝的加工， 非常能體會使用機械（比如車床）切出一個圓的東西是很容易的事情，但是要切出一個方的是極為費勁的。

 

因此，誰要是在機械設計時搞了一堆方的設計，會被認為缺乏基本的機械設計素養。如果你到製造業的工廠去看看，基本上就只有兩種運動，直線運動和圓周運動，其它所有的運動都是它們的組合 ( 而且用得並不多 )。這並不是說世界上只有這兩種運動，但是將運動抽象成這兩種，就容易在機械中實現了。

 

 

 

問題：

 

請問，哈希表在一定程度上是否兼有數組和鏈錶的優點呢？

 

吳軍：

 

這個問題問得很好！這個問題有點專業化，我盡可能簡單地做一下解答。

 

首先還是要說明，世界是沒有只有優點沒有缺點的東西，就如同沒有只有正面沒有反面的紙張一樣，哈希表不可能只有數組和鏈錶的優點而沒有缺點。

 

其次，數組、鏈錶和哈希表是三個不同的東西，它們有一些相關性，但是使用的目的有區別。

 

數組是為了便於直接查找訪問，它要求數據項基本上是整齊的，比如大家的姓名長度都差不多，格式都是一串漢字或者英文字母。

 

鏈錶強調的是前後的依賴關係，一個連著一個，比如某個學位選課的次序，一門課和它的先修課就是這種鏈接關係，只有先完成了先修課，才能選下一門課。課程的一二三四五編號，倒並不重要。

 

哈希表的本質是通過隨機化，把一個比較大的、稀疏的空間．映射到一個比較小的、緊密的空間中。在計算機中，它通常是通過數組實現的。相比一般的數組，它有三個優點：

 

1. 動態增加或者刪除一個數據項比較快。

 

2. 數組只能根據下標直接查找，下標和數據內容無關，如果要根據內容查找，效率就比較低，哈希表的下標是根據數據內容計算出來的，囚此根據內容查找比較快。

 

3. 數組在處理多個維度時變得很複雜，哈希表可以將多個維度的數據映射到一個維度。

 

但是，哈希表是需要額外成本的，它其實是以空間換時間。其次，數組可以一次順序存取很多項數據，而哈希表存取數據只能一個個進行。

 

 

 

問題：

 

計算機的數據儲存要有結構，我們人腦記憶知識也需要結構化記憶嗎？我們常說的結構化記憶跟計算機的鏈式數據有相通之處嗎？

 

吳軍：

 

人腦本身的記憶很難刻意把它結構化，因為人腦是怎樣記憶的至今還沒有搞得很清楚，認知科學家和腦科學家目前所掌握的人腦知識可能連人腦認知的 1％ 都不到。但是，我們人可以設計出幫助我們記憶，以及提醒我們記憶的工具。所謂的結構化記憶就是這樣一種工具。

 

結構化記憶和計算機的鍊錶沒有多大關係，倒是和計算機的數據庫存儲方法有關係。關於數據庫我以後還會專門介紹，這裡講它在存儲和查找數據上的兩個要點：

 

1. 它把我們現實生活中很具體的、結構並不是很清晰的數據抽象成結構化的。比如在單位裡我們每一個人的人事記錄，在現實狀態下不可能相同。有的人因為在單位時間長，內容多一些，有的人少一點；有的人比別人多一些選項，比如得過很多獎，有的人記錄很不完整。當然使用計算機進行人事管理，就需要有相對統一的格式，從大家的共性中抽象化出一些具體的結構就很重要。比如大家都有姓名、性別、年齡，以及按照時間次序組織起來的工作經歷等等。

 

2. 抽象化的過程要超脫數據原來物理式的結構。比如原來的檔案是一個人一個口袋，各種數據鬍子連著眉毛放在一起，在計算機中這樣存放就難以查找使用，因此需要根據共同的數據變成一個個方便查找使用的表格，比如人的姓名、出生年月、性別等簡單信息是一個表， 人的履歷是另一個表，單位裡某項任務和人的關係是第三個表格。這些抽象出來的表格，和真實世界就有差距了，它們被設計出來的目的是為了便於管理，也便於計算機處理。

 

結構化的數據通常和鏈錶沒有什麼關係，倒反而容易用數組來存儲。一般來講，格式固定， 數據項大小固定的數據，改動較小的數據，採用數組存儲比較好。格式不固定，經常變動的數據，採用鍊錶存儲方便些。

 

 

 

問題：

 

計算機程序也有一個數據類型的概念，那它跟數據結構的區別是什麼？和數據結構又有什麼聯繫？

 

吳軍：

 

這是一個太具體的問題，為了方便非計算機專業的讀者理解，我這樣打比方。

 

比如蓋房子，需要各種預製件，它們就是數據結構。但是你使用的鋼筋有尺寸和標號的差別，比如 10 米長，1/2 英寸粗，高碳鋼的鋼筋，或者 5 米長，1/4 英寸粗，普通鋼的鋼筋。

 

這就相當於計算機的數據類型，一個數字可以是 32 位有正負之分的整數，64 位有正負之分的整數，32 位沒有正負之分的整數，或者 64 位的浮點數，即數學上所說的實數或者小數。這些就相當於是不同編號的鋼筋。在建築中， 做一個橫梁可能需要使用前一種鋼筋，做樓梯的隔板需要使用後一種鋼筋。

 

類似地，在計算機中，設計大學裡學生的學號，使用 32 位的無符號整數就可以了，因為學號不會是負數，也不會上億，而設計我們的身份證號，使用 32 位二進制就不夠了，需要使用 64 位。

 

 

 

問題：

 

作為二元樹的變種，哈夫曼樹和紅黑樹是不是在查詢或者寫入效率上做了優化呢？如何更有效地優化二元樹在大數據量下的讀寫性能呢？

 

吳軍：

 

這個問題太過專業化，我簡單回答如下。

 

1. 哈夫曼樹主要是對應於哈夫曼編碼，即信息論裡的最短編碼。這樣可以保證平均的訪問時間最短。當然，哈夫曼編碼的條件是必須事先知道每個碼出現的頻率。

 

2. 紅黑樹主要是為了防止二元樹一個枝子太長，另一個太短。比如一邊50層，另一邊 3 層，這樣效率就不高了。使用紅黑樹，可以保證各個枝子的長度基本相等。當然，代價是需要不斷維持平衡。

 

它們的目的不同。

 

 

來源：《吳軍-問答：計算機數據結構的出現與計算機本身的關係》