# HashTest

**Repository Path**: Jame_sz/hash-test

## Basic Information

- **Project Name**: HashTest
- **Description**: 可信计算hash作业
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-08
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# HashTest

#### 介绍
可信计算hash作业

#### 软件架构
软件架构说明


#### 文件夹说明

1.  hash文件夹是解决hash冲突的线性探测法的实现
2.  hash2文件夹是解决hash冲突的二次探测再散列的实现
3.  linehash文件夹是解决hash文件夹中hash冲突的线性探测法的溢出问题的实现

#### hash文件夹代码说明

1.  DataItem：hash表中存放的数据格式的定义，目前我只定义了int类型。
2.  HashTable：hash表的具体实现，包含遍历、增加、删除、查找。还有哈希表的构建。
3.  HashTableApplication：方法的具体实现。需要输入创建哈希表的大小的size与相应的操作的命令。并在控制台显示。
4.  整体流程说明：首先键盘输入数字size，HashTable根据size创建哈希表。
    再键入n，程序将通过随机函数与定义的随机因子的大小创建n个数，并按照线性探测法的方法放入hash表中。
    键入s，hash表输出展示，为空输出**。
    键入i，hash表按照线性探测法的方法插入。
    键入d，hash表按照关键字删除，按照线性探测法的方法查找关键字，对比成功后，删除。
    键入f，hash表按照关键字查找，按照线性探测法的方法查找关键字，对比成功后，输出显示。
5.  线性探测法：将关键字与size取模，结果为hash表下标，查找。为空，插入。不为空，查找下一个。
    达到末尾时，从头开始，依次循环只到查找到空位。
6.  存在问题：hash表的大小被限定了，当存在超过size的数据时，无法插入，使程序崩溃。
7.  解决方法：线性哈希桶分裂

#### hash2文件夹代码说明

1.  DataItem：hash表中存放的数据格式的定义，目前我只定义了int类型。
2.  HashTable：hash表的具体实现，包含遍历、增加、删除、查找。还有哈希表的构建。
3.  HashTableApplication：方法的具体实现。需要输入创建哈希表的大小的size与相应的操作的命令。并在控制台显示。
4.  整体流程说明：首先键盘输入数字size，HashTable根据size创建哈希表。
    再键入n，程序将通过随机函数与定义的随机因子的大小创建n个数，并按照二次探测再散列的方法放入hash表中。
    键入s，hash表输出展示，为空输出**。
    键入i，hash表按照二次探测再散列的方法插入。
    键入d，hash表按照关键字删除，按照二次探测再散列的方法查找关键字，对比成功后，删除。
    键入f，hash表按照关键字查找，按照二次探测再散列的方法查找关键字，对比成功后，输出显示。
5.  二次探测再散列法：将关键字与size取模，结果为hash表下标，查找。为空，插入。
    不为空，将关键字与5取模，用5-取模结果，再将减后的结果与关键字取模的结果相加，再将相加的结构与size取模，结果为hash表下标，查找。
    为空，插入，不为空，重复上一步骤。
6.  存在问题：hash表的大小被限定了，当存在超过size的数据时，无法插入，使程序崩溃。
7.  解决方法：线性哈希桶分裂

#### LineHash文件夹代码说明
1.  线性哈希桶分裂的数学原理:假定key = 5、9、13，模为4，key % 4 = 1，现在我们对8求余，5 % 8 = 5、9 % 8 = 1、13 % 8 = 5
    由上面的规律可以得出：(任意key) % n = M，(任意key) %2n = M或 (任意key) %2n = M + n。
2.  线性哈希桶分裂实现算法过程：
    （1）为了使哈希表能进行动态的分裂，我们从桶0开始设定一个分裂点。
    （2）一个桶的容量为listSize = 5，当桶的容量超出后就从分裂点开始进行分裂。
    （3）hash函数为 h0 = key %4  h1 = key % 8，h1会在分裂时使用。
    （4）整个表初始化包含了4个桶，桶号为0-3，并已提前插入了部分的数据。
    （5）现在插入key = 27
    （6）进行哈希运算，h0 = 27 % 4 = 3
    （7）将key = 27插入桶3，但发现桶3已经达到了桶的容量，所以触发哈希分裂
    （8）由于现在分裂点处于0桶，所以我们对0桶进行分割。这里需要注意虽然这里是3桶满了，但我们并不会直接从3桶进行分割，而是从分割点进行分割。这里为什么这么做，在下面会进一步介绍。
    （9）对分割点所指向的桶(桶0)所包含的key采用新的hash函数(h1)进行分割。
3.  说明：
    （1）如果下一次key插入0、1、2、4桶，是不会触发分裂。（没有超出桶的容量）如果是插入桶3，用户在实现时可以自己设定，可以一旦插入就触发，也可以等溢出页达到listSize再触发新的分裂。
    （2）现在0桶被分裂了，新数据的插入怎么才能保证没分裂的桶能正常工作，已经分裂的桶能将部分插入到新分裂的桶呢?
         只要分裂点小于桶的总数，我们依然采用h0函数进行哈希计算。
         如果哈希结果小于分裂号，那么表示这个key所插入的桶已经进行了分割，那么我就采用h1再次进行哈希，而h1的哈希结果就这个key所该插入的桶号。
         如果哈希结果大于分裂号，那么表示这个key所插入的桶还没有进行分裂。直接插入。
         这也是为什么虽然是桶3的容量不足，但分裂的桶是分裂点所指向的桶。如果直接在桶3进行分裂，那么当新的key插入的时候就不能正常的判断哪些桶已经进行了分裂。
    （3）如果使用分割点，就具备了无限扩展的能力。当分割点移动到最后一个桶(桶3)。再出现分裂。
         那么分割点就会回到桶0，到这个时候，h0作废，h1替代h0, h2(key % 12)替代h1。那么又可以开始动态分割。那个整个初始化状态就发生了变化。就好像没有发生过分裂。那么上面的规则就可以循环使用。

#### 参与贡献

1.  Fork 本仓库
2.  新建 Feat_xxx 分支
3.  提交代码
4.  新建 Pull Request


#### 特技

1.  使用 Readme\_XXX.md 来支持不同的语言，例如 Readme\_en.md, Readme\_zh.md
2.  Gitee 官方博客 [blog.gitee.com](https://blog.gitee.com)
3.  你可以 [https://gitee.com/explore](https://gitee.com/explore) 这个地址来了解 Gitee 上的优秀开源项目
4.  [GVP](https://gitee.com/gvp) 全称是 Gitee 最有价值开源项目，是综合评定出的优秀开源项目
5.  Gitee 官方提供的使用手册 [https://gitee.com/help](https://gitee.com/help)
6.  Gitee 封面人物是一档用来展示 Gitee 会员风采的栏目 [https://gitee.com/gitee-stars/](https://gitee.com/gitee-stars/)