摘要：選擇從開始的連續(xù)質(zhì)數(shù)來建立一個(gè)十層的哈希樹。哈希樹主要有三個(gè)方法與，它們的結(jié)構(gòu)都差不多。哈希樹也沒有必要為不存在的關(guān)鍵字提前分配空間。即使數(shù)據(jù)量減少到原來的數(shù)量，但是哈希樹的總節(jié)點(diǎn)數(shù)不會減少。而哈希樹的查找次數(shù)和元素個(gè)數(shù)沒有關(guān)系。

質(zhì)數(shù)分辨定理

n個(gè)不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè)數(shù)和他們的乘積相等。“分辨”就是指這些連續(xù)的整數(shù)不可能有完全相同的余數(shù)序列。
（這個(gè)定理的證明詳見：http://wenku.baidu.com/view/1...）

例如：
從2起的連續(xù)質(zhì)數(shù)，連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約M(10) =23571113171923*29= 6464693230 個(gè)數(shù)，已經(jīng)超過計(jì)算機(jī)中常用整數(shù)（32bit）的表達(dá)范圍。連續(xù)100個(gè)質(zhì)數(shù)就可以分辨大約M(100) = 4.711930 乘以10的219次方。

而按照目前的CPU水平，100次取余的整數(shù)除法操作幾乎不算什么難事。在實(shí)際應(yīng)用中，整體的操作速度往往取決于節(jié)點(diǎn)將關(guān)鍵字裝載內(nèi)存的次數(shù)和時(shí)間。一般來說，裝載的時(shí)間是由關(guān)鍵字的大小和硬件來決定的；在相同類型關(guān)鍵字和相同硬件條件下，實(shí)際的整體操作時(shí)間就主要取決于裝載的次數(shù)。他們之間是一個(gè)成正比的關(guān)系。

我們選擇質(zhì)數(shù)分辨算法來建立一棵哈希樹。
選擇從2開始的連續(xù)質(zhì)數(shù)來建立一個(gè)十層的哈希樹。第一層結(jié)點(diǎn)為根結(jié)點(diǎn)，根結(jié)點(diǎn)下有2個(gè)結(jié)點(diǎn)；第二層的每個(gè)結(jié)點(diǎn)下有3個(gè)結(jié)點(diǎn)；依此類推，即每層結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目為連續(xù)的質(zhì)數(shù)。到第十層，每個(gè)結(jié)點(diǎn)下有29個(gè)結(jié)點(diǎn)。

除了根結(jié)點(diǎn)，不放東西，其他都動(dòng)態(tài)生成一個(gè)對象，添加上key, value, occupied三個(gè)屬性。occupied是用于表示這個(gè)結(jié)點(diǎn)是否已經(jīng)被刪除，因?yàn)槲也⒉徽嬲齽h除節(jié)點(diǎn)，避免遞歸處理下面的子節(jié)點(diǎn)。在插入過程，已經(jīng)發(fā)現(xiàn)有對象點(diǎn)著，并且occupied不為false，那么就取下一個(gè)質(zhì)數(shù)重新計(jì)算，以當(dāng)前對象為起點(diǎn)進(jìn)行插入操作。

哈希樹主要有三個(gè)方法 insert, search與remove，它們的結(jié)構(gòu)都差不多。

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、結(jié)構(gòu)簡單

從哈希樹的結(jié)構(gòu)來說，非常的簡單。每層節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)為連續(xù)的質(zhì)數(shù)。子節(jié)點(diǎn)可以隨時(shí)創(chuàng)建。因此哈希樹的結(jié)構(gòu)是動(dòng)態(tài)的，也不像某些哈希算法那樣需要長時(shí)間的初始化過程。哈希樹也沒有必要為不存在的關(guān)鍵字提前分配空間。
需要注意的是哈希樹是一個(gè)單向增加的結(jié)構(gòu)，即隨著所需要存儲的數(shù)據(jù)量增加而增大。即使數(shù)據(jù)量減少到原來的數(shù)量，但是哈希樹的總節(jié)點(diǎn)數(shù)不會減少。這樣做的目的是為了避免結(jié)構(gòu)的調(diào)整帶來的額外消耗。

2、查找迅速

從算法過程我們可以看出，對于整數(shù)，哈希樹層級最多能增加到10。因此最多只需要十次取余和比較操作，就可以知道這個(gè)對象是否存在。這個(gè)在算法邏輯上決定了哈希樹的優(yōu)越性。
一般的樹狀結(jié)構(gòu)，往往隨著層次和層次中節(jié)點(diǎn)數(shù)的增加而導(dǎo)致更多的比較操作。操作次數(shù)可以說無法準(zhǔn)確確定上限。而哈希樹的查找次數(shù)和元素個(gè)數(shù)沒有關(guān)系。如果元素的連續(xù)關(guān)鍵字總個(gè)數(shù)在計(jì)算機(jī)的整數(shù)（32bit）所能表達(dá)的最大范圍內(nèi)，那么比較次數(shù)就最多不會超過10次，通常低于這個(gè)數(shù)值。

3、結(jié)構(gòu)不變

從刪除算法中可以看出，哈希樹在刪除的時(shí)候，并不做任何結(jié)構(gòu)調(diào)整。這個(gè)也是它的一個(gè)非常好的優(yōu)點(diǎn)。常規(guī)樹結(jié)構(gòu)在增加元素和刪除元素的時(shí)候都要做一定的結(jié)構(gòu)調(diào)整，否則他們將可能退化為鏈表結(jié)構(gòu)，而導(dǎo)致查找效率的降低。哈希樹采取的是一種“見縫插針”的算法，從來不用擔(dān)心退化的問題，也不必為優(yōu)化結(jié)構(gòu)而采取額外的操作，因此大大節(jié)約了操作時(shí)間。

1、非排序性

哈希樹不支持排序，沒有順序特性。如果在此基礎(chǔ)上不做任何改進(jìn)的話并試圖通過遍歷來實(shí)現(xiàn)排序，那么操作效率將遠(yuǎn)遠(yuǎn)低于其他類型的數(shù)據(jù)結(jié)構(gòu)。