摘要:選擇從開始的連續質數來建立一個十層的哈希樹。哈希樹主要有三個方法與,它們的結構都差不多。哈希樹也沒有必要為不存在的關鍵字提前分配空間。即使數據量減少到原來的數量,但是哈希樹的總節點數不會減少。而哈希樹的查找次數和元素個數沒有關系。
哈希樹的理論基礎
質數分辨定理
n個不同的質數可以“分辨”的連續整數的個數和他們的乘積相等。“分辨”就是指這些連續的整數不可能有完全相同的余數序列。
(這個定理的證明詳見:http://wenku.baidu.com/view/1...)
例如:
從2起的連續質數,連續10個質數就可以分辨大約M(10) =23571113171923*29= 6464693230 個數,已經超過計算機中常用整數(32bit)的表達范圍。連續100個質數就可以分辨大約M(100) = 4.711930 乘以10的219次方。
而按照目前的CPU水平,100次取余的整數除法操作幾乎不算什么難事。在實際應用中,整體的操作速度往往取決于節點將關鍵字裝載內存的次數和時間。一般來說,裝載的時間是由關鍵字的大小和硬件來決定的;在相同類型關鍵字和相同硬件條件下,實際的整體操作時間就主要取決于裝載的次數。他們之間是一個成正比的關系。
程序實現我們選擇質數分辨算法來建立一棵哈希樹。
選擇從2開始的連續質數來建立一個十層的哈希樹。第一層結點為根結點,根結點下有2個結點;第二層的每個結點下有3個結點;依此類推,即每層結點的子節點數目為連續的質數。到第十層,每個結點下有29個結點。
除了根結點,不放東西,其他都動態生成一個對象,添加上key, value, occupied三個屬性。occupied是用于表示這個結點是否已經被刪除,因為我并不真正刪除節點,避免遞歸處理下面的子節點。在插入過程,已經發現有對象點著,并且occupied不為false,那么就取下一個質數重新計算,以當前對象為起點進行插入操作。
哈希樹主要有三個方法 insert, search與remove,它們的結構都差不多。
class HashTree{ constructor(){ this.root = {} } insert(key, value){ var primes = [2,3,5,7,11,13,17,19,23,29], cur = this.root for(var i = 0; i < 10; i++){ var prime = primes[i] var a = key % prime var obj = cur[a] if(!obj){ //插入成功 cur[a] = { key : key, value: value, occupied: true } break }else if(!obj.occupied){ obj.key = key obj.value = value obj.occupied = true break }else{ cur = obj } } } search(key){ var primes = [2,3,5,7,11,13,17,19,23,29], cur = this.root for(var i = 0; i < 10; i++){ var prime = primes[i] var a = key % prime var obj = cur[a] if(obj){ if(obj.key === key){ console.log(key) return obj.value }else{ cur = obj } }else{ return null } } } remove(key){ var primes = [2,3,5,7,11,13,17,19,23,29], cur = this.root for(var i = 0; i < 10; i++){ var prime = primes[i] var a = key % prime var obj = cur[a] if(obj){ if(obj.key === key){ obj.occupied = false break }else{ cur = obj } }else{ break } } } } //自己在chrome控制臺下查看 var tree = new HashTree tree.insert(7807, "a") tree.insert(249, "b") tree.insert(1073, "c") tree.insert(658, "d") tree.insert(930, "e") tree.insert(2272, "f") tree.insert(8544, "g") tree.insert(1878, "h") tree.insert(8923, "i") tree.insert(8709, "j") console.log(tree) console.log(tree.search(1878))優點
1、結構簡單
從哈希樹的結構來說,非常的簡單。每層節點的子節點個數為連續的質數。子節點可以隨時創建。因此哈希樹的結構是動態的,也不像某些哈希算法那樣需要長時間的初始化過程。哈希樹也沒有必要為不存在的關鍵字提前分配空間。
需要注意的是哈希樹是一個單向增加的結構,即隨著所需要存儲的數據量增加而增大。即使數據量減少到原來的數量,但是哈希樹的總節點數不會減少。這樣做的目的是為了避免結構的調整帶來的額外消耗。
2、查找迅速
從算法過程我們可以看出,對于整數,哈希樹層級最多能增加到10。因此最多只需要十次取余和比較操作,就可以知道這個對象是否存在。這個在算法邏輯上決定了哈希樹的優越性。
一般的樹狀結構,往往隨著層次和層次中節點數的增加而導致更多的比較操作。操作次數可以說無法準確確定上限。而哈希樹的查找次數和元素個數沒有關系。如果元素的連續關鍵字總個數在計算機的整數(32bit)所能表達的最大范圍內,那么比較次數就最多不會超過10次,通常低于這個數值。
3、結構不變
從刪除算法中可以看出,哈希樹在刪除的時候,并不做任何結構調整。這個也是它的一個非常好的優點。常規樹結構在增加元素和刪除元素的時候都要做一定的結構調整,否則他們將可能退化為鏈表結構,而導致查找效率的降低。哈希樹采取的是一種“見縫插針”的算法,從來不用擔心退化的問題,也不必為優化結構而采取額外的操作,因此大大節約了操作時間。
缺點1、非排序性
哈希樹不支持排序,沒有順序特性。如果在此基礎上不做任何改進的話并試圖通過遍歷來實現排序,那么操作效率將遠遠低于其他類型的數據結構。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/92827.html
摘要:很容易看出,前綴最壞情況下的查找也快過二叉搜索樹。這種壓縮后的被喚作前綴壓縮,或直接叫前綴樹,字典樹。最長公共前綴和的最長公共前綴是,遍歷字典樹到字母時,此時這些單詞的公共前綴是。 引子 前綴Trie, 又叫字符Tire, trie來自單詞retrieval, 一開始念作tree,后來改念try, 畢竟它與樹是不一樣的東西。網上許多文章都搞混了trie與樹。 trie是通過邊來儲存字符...
摘要:數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象,稱為結點。 本文涉及更多的是概念,代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數據結構和查找算法 本文主要是基礎的數據結構和算法概念,可能部分地方會涉及更高級的算法和算法,具體內容以...
摘要:是以太坊存儲數據的核心數據結構,它是由和結合的一種樹形結構,理解有助于我們更好的理解以太坊的數據存儲。所以就有了樹壓縮前綴樹,后面會介紹到,也被稱為,中文名稱默克爾樹,主要用于數據集較大時的文件校驗。 ??MPT(Merkle Patricia Tries)是以太坊存儲數據的核心數據結構,它是由Merkle Tree和Patricia Tree結合的一種樹形結構,理解MPT有助于我們更...
閱讀 1609·2021-09-23 11:31
閱讀 924·2021-09-23 11:22
閱讀 1347·2021-09-22 15:41
閱讀 4076·2021-09-03 10:28
閱讀 2911·2019-08-30 15:55
閱讀 3545·2019-08-30 15:55
閱讀 1954·2019-08-30 15:44
閱讀 2717·2019-08-30 13:50