首页 > 代码库 > 散列树(Hash Tree)

散列树(Hash Tree)

      用质数分辨算法来建立一棵散列树(Hash树)。
  选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点,根结点下有2个结点;第二层的每个结点下有3个结点;第三层的每个结点下有5个结点;依此类推,即每层结点的子节点数目为连续的质数。到第十层,每个结点下有29个结点。
  同一结点中的子结点,从左到右代表不同的余数结果。例如:第二层结点下有三个子节点。那么从左到右分别代表:除3余0,除3余1,除3余2.
      对质数进行取余操作得到的余数决定了处理的路径。结点:结点的关键字(在整个树中是唯一的),结点的数据对象,结点是否被占据的标志位(标志位为真时,关键字才被认为是有效的),和结点的子结点数组。

特点

  1. 哈希树的结构是动态的,也不像某些哈希算法那样需要长时间的初始化过程,只需要初始化根结点就可以开始工作。哈希树也没 有必要为不存在的关键字提前分配空间。
  2. 查找迅速,最多只需要10次取余和比较操作,就可知道这个对象是否存在。哈希树的查找次数和元素个数没有关系。
  3. 结构不变,哈希树在删除的时候并不做任何结构调整。这也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整。
  4. 非排序性,哈希树不支持排序,没有顺序特性。需要注意的是:哈希树是一个单向增加的结构,即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量,但是哈希树的总结点树不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。

C代码见百度百科
http://baike.baidu.com/link?url=_UUaD3G1AUkhgZvfmjFqqOx6VIuZm3R1BHHjM1bGqy8pdJZ9G7Xn4AjnSMiNBAvQYeB7nlT9MP9hSQYHMIgMSK

散列树(Hash Tree)