哈希树讲解

       哈希树(HashTree)是哈希(Hash)算法的一种延续。传统数据结构中对如何避免哈希冲突都有一定的描述和解释，但是这些描述和解释都是泛泛而谈，并没有提出比较好的解决方案。这里所提到的哈希树(HashTree)算法就是要提供一种在理论上和实际应用中均能有效地处理冲突的方法。
        有关哈希树(HashTree)算法的理论解释以及与其他算法的评估可以参考文档《哈希树（HashTree）》。文中的理论和有关的数据操作描述还不见得完善，这里可以给出有关的源代码和相关编译后的可验证文件。点击这里下载源代码和可验证文件。整个代码使用Java编写，建议使用Eclipse、JBuilder或者NetBean等Java编译工具进行编译。
        本文中所提到的哈希树(HashTree)算法与其他哈希(Hash)算法相比有如下特点：
        (1)本文中解决哈希树(HashTree)冲突的算法是以“无限定”算法映射“无限定”范围的键值，因此解决冲突的方法永远有效。实际应用中会有一定限制，例如：最多4G个对象。
        (2)本文中哈希树(HashTree)算法对键值的长度和类型范围没有任何要求。可以是整数，也可以是字符串；不需要对键值压缩或者重新编码。实际应用中会对键值范围有一定限定，例如：键值最长为64字节。
        当然也可以调整程序全局设置，使其支持256字节甚至更长的键值。这种调整不会影响算法理论上的效率。算法理论上的效率仅和所需要分辨的对象个数有关，与键值长度无关。
        (3)“最小”哈希树(HashTree)在从4G个对象中找出所匹配的对象，比较次数不超过10次。也就是说：最多属于O(10)。在实际应用中，调整了质数的范围，使得比较次数一般不超过5次。也就是说：最多属于O(5)。因此可以根据自身需要在时间和空间上寻求一个平衡点。
        (4)本文中哈希树(HashTree)算法对哈希(Hash)算法对空间需求的无限膨胀提出了有效的解决方法。一般的哈希(Hash)算法都是O(1)的，而且基本是以空间换时间。这很容易导致对存储空间无限制的需求。
        本文中哈希树(HashTree)算法在实际操作中使用了一些技巧使得对空间的需求控制在一定范围内。即空间需求仅和所需要存储的对象个数有关，不会无限制地“膨胀”下去。
        (5)在一些索引算法中，如果遇到数据的反复增、删、改过程，很容易导致数据结构的退化。为了避免这种退化，就需要经常对数据结构作出“平衡”调整。
        本文中哈希树(HashTree)算法在数据的反复增、删、改过程中，无需对数据结构做出任何“平衡”操作。即使长期处于复杂的数据操作过程中，仍能很好地保持其基本性质。
        所提供的代码已经经过实际六年以上的运行检验，完全可以值得信赖。有关理论方面的了解还是请参考文档《哈希树（HashTree）》。这里主要介绍有关代码使用方面的问题。
        基于哈希树(HashTree)算法的文件存储模式核心代码文件就两个：HashFileNodeBuffer.java和HashFileContainer.java。这两个类均在目录“/source/com/simpleteam/container/hash”下。如果想使用数据包的功能，可以参考HashFileContain下面的main函数，里面有一个标准的例子。主要的步骤如下：
        步骤1.创建一个文件。

File file = new File("container.file");

        步骤2.创建一个类要求使用指定的文件，以及定义存储数据的空间。这个空间要求数据都能存储在里面，不能超过此空间大小要求。

HashFileContainer container = new HashFileContainer(file,pageSize);

步骤3.检查文件是否安全关闭。如果没有安全关闭可以选择重建所有数据。如果数据量很大，重建数据可能会需要很多时间。

if(!container.isSafelyClosed()) {……container = rebuild(container)……}

        步骤4.在以上操作完毕之后，可以进行以下相关操作：
        (1)检查容器中是否存在某键值。

if(container.exists(key)) {……}

        (2)获得键值所对应的数值。

Object value = container.get(key);

        (3)存储键值以及其所对应的数据。常见的Integer、Long、byte[]、String均可存储，可存储对象要求至少能Serializable。对于Expiration可以填写，也可以不填写。

container.put(key,value);container.put(key,value,expiration);

        (4)删除键值所对应的数据。如果提取到数据，那么原始数据将从数据文件中被删除。

Object value = container.remove(key);

        步骤5.安全关闭该容器。

container.close();

        以上所有操作均不是线程安全的。也就是说如果想将该容器类用于多线程操作，请单独进行安全操作封装。
        HashFileContainer.main函数的主要意图是建立了一个线性表用来验证哈希数(HashTree)操作的正确性和有效性。测试中要求对1000000数据进行反复的增、删操作。打印部分展示了有关哈希树(HashTree)的三个参数：数据量(size)；当前1000个数据的平均操作时间；总的数据平均操作时间。一般来说随着数据量的增加，操作时间会逐渐增加。
        由于该程序使用Java编写，而且所有的操作基本基于磁盘操作，因此效率有限。如果使用C/C++根据原理改写相关的代码，效率至少在3~10倍以上