Operating-System/Experiment/OS_exp/experiment_04/实验四_报告.md

实验四 文件系统——散列结构文件

一、实验内容

理解 Linux 文件系统内部技术，掌握文件系统调用，建立面向随机检索的散列结构文件。

设计散列文件创建、打开、关闭、读、写、删除等函数，编写测试程序验证。

二、实验设计

2.1 文件结构

+------------------+
|  HashFileHeader  |  (文件头：签名、记录长度、总记录数、当前记录数)
+------------------+
|  CFTag | Record  |  ← 桶0 (冲突链)
+------------------+
|  CFTag | Record  |  ← 桶1
+------------------+
|  ...             |  ← 桶n (线性探测)
+------------------+

2.2 数据结构

struct HashFileHeader {
    int sig;              // 签名31415926，标识有效文件
    int reclen;           // 记录长度
    int total_rec_num;    // 总记录数
    int current_rec_num;  // 当前记录数
};

struct CFTag {
    char collision;        // 冲突计数
    char free;            // 是否空闲 (1=空闲, 0=占用)
};

2.3 函数设计

函数	功能
hashfile_creat()	创建散列文件，写入文件头和空桶
hashfile_open()	打开文件，验证签名
hashfile_close()	关闭文件
hashfile_read()	按key查找并读取记录
hashfile_write()	写入记录（调用saverec）
hashfile_delrec()	删除记录
hashfile_findrec()	散列查找核心函数
hashfile_saverec()	保存记录，处理冲突
hash()	散列函数
readHashFileHeader()	读取文件头

2.4 调用关系

hashfile_saverec()
├── hash() 计算桶地址
├── 读取桶标签，增加collision计数
└── 线性探测找空闲位置
    └── 写入标签和记录

hashfile_findrec()
├── hash() 计算桶地址
├── 遍历冲突链
│   ├── 跳过free==0的已删除位置
│   └── 逐字节比较key
└── 返回记录偏移量

hashfile_delrec()
├── hashfile_findrec() 定位记录
├── 设置free=0（逻辑删除）
├── 减少collision计数
└── 减少current_rec_num

三、编码实现

3.1 散列函数

int hash(int keyoffset, int keylen, void *buf, int total_rec_num) {
    int i = 0, addr = 0;
    char *p = (char *)buf + keyoffset;
    for (i = 0; i < keylen; i++) {
        addr += (int)(*p);
        p++;
    }
    // COLLISIONFACTOR=0.5，实际桶数为 total_rec_num * 0.5
    return addr % (int)(total_rec_num * COLLISIONFACTOR);
}

修改要点： 将key的每个字节ASCII值累加，再取模。COLLISIONFACTOR 控制冲突链长度。

3.2 保存记录（处理冲突）

int hashfile_saverec(int fd, int keyoffset, int keylen, void *buf) {
    if (checkHashFileFull(fd)) return -1;

    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);

    // 计算散列地址
    int addr = hash(keyoffset, keylen, buf, hfh.total_rec_num);
    int offset = sizeof(struct HashFileHeader) + addr * (hfh.reclen + sizeof(struct CFTag));

    lseek(fd, offset, SEEK_SET);
    struct CFTag tag;
    read(fd, &tag, sizeof(struct CFTag));
    tag.collision++;
    lseek(fd, sizeof(struct CFTag) * (-1), SEEK_CUR);
    write(fd, &tag, sizeof(struct CFTag));

    // 线性探测找空闲位置
    while (tag.free != 0) {
        offset += hfh.reclen + sizeof(struct CFTag);
        if (offset >= lseek(fd, 0, SEEK_END))
            offset = sizeof(struct HashFileHeader);
        lseek(fd, offset, SEEK_SET);
        read(fd, &tag, sizeof(struct CFTag));
    }

    // 写入标签和记录
    tag.free = 1;
    lseek(fd, sizeof(struct CFTag) * (-1), SEEK_CUR);
    write(fd, &tag, sizeof(struct CFTag));
    write(fd, buf, hfh.reclen);

    hfh.current_rec_num++;
    lseek(fd, 0, SEEK_SET);
    return write(fd, &hfh, sizeof(struct HashFileHeader));
}

3.3 查找记录

int hashfile_findrec(int fd, int keyoffset, int keylen, void *buf) {
    struct HashFileHeader hfh;
    readHashFileHeader(fd, &hfh);

    int addr = hash(keyoffset, keylen, buf, hfh.total_rec_num);
    int offset = sizeof(struct HashFileHeader) + addr * (hfh.reclen + sizeof(struct CFTag));

    lseek(fd, offset, SEEK_SET);
    struct CFTag tag;
    read(fd, &tag, sizeof(struct CFTag));

    char count = tag.collision;
    if (count == 0) return -1;

recfree:
    // 跳过已删除位置
    if (tag.free == 0) {
        offset += hfh.reclen + sizeof(struct CFTag);
        lseek(fd, offset, SEEK_SET);
        read(fd, &tag, sizeof(struct CFTag));
        goto recfree;
    }

    // 读取记录并比较key
    char *p = (char *)malloc(hfh.reclen);
    read(fd, p, hfh.reclen);
    char *p1 = (char *)buf + keyoffset;
    char *p2 = p + keyoffset;
    int j = 0;
    while (*p1 == *p2 && j < keylen) {
        p1++; p2++; j++;
    }
    if (j == keylen) {
        free(p);
        return offset;  // 找到
    }
    free(p);

    // 继续遍历冲突链
    offset += hfh.reclen + sizeof(struct CFTag);
    lseek(fd, offset, SEEK_SET);
    read(fd, &tag, sizeof(struct CFTag));
    goto recfree;
}

3.4 编译与运行

gcc HashFile.c exp04_test.c -o hashfile_test
./hashfile_test

输出示例：

Tag is <2,1>    Record is {1,jing}
Tag is <1,1>    Record is {2,wang}
Tag is <1,1>    Record is {3,li}
Tag is <1,1>    Record is {4,zhang}
Tag is <1,1>    Record is {5,qing}
Tag is <0,1>    Record is {6,yuan}

四、实验结果

4.0 测试命令

# 编译
gcc HashFile.c exp04_test.c -o hashfile_test

# 运行
./hashfile_test

# 查看生成的散列文件
ls -la jing.hash

# 以十六进制查看文件内容
hexdump -C jing.hash

4.1 创建散列文件

int fd = hashfile_creat(FILENAME, O_RDWR | O_CREAT, RECORDLEN, 6);

• 文件头写入签名31415926
• 分配6个桶，每个桶包含CFTag和32字节记录
• COLLISIONFACTOR=0.5，实际桶数为3

4.2 插入测试

插入: {1,jing} → hash(1) = 1 % 3 = 1
插入: {2,wang} → hash(2) = 2 % 3 = 2
插入: {3,li}   → hash(3) = 3 % 3 = 0
插入: {4,zhang}→ hash(4) = 4 % 3 = 1 (冲突，向后探测)
插入: {5,qing} → hash(5) = 5 % 3 = 2 (冲突，向后探测)
插入: {6,yuan} → hash(6) = 6 % 3 = 0 (冲突，向后探测)

结果说明：

• collision字段表示有多少记录映射到该桶
• free字段表示该位置是否被占用
• 线性探测解决冲突

4.3 查找测试

查找key=4时：

1. hash(4) = 1，计算偏移量到桶1
2. 桶1位置是 {2,wang}，key不匹配
3. 沿冲突链向下查找
4. 找到位置 {4,zhang}，key匹配

五、实验结果思考与体会

5.1 散列文件特点

特性	说明
查找复杂度	平均 O(1)，最坏 O(n)
空间利用率	约50%（COLLISIONFACTOR）
冲突处理	线性探测
删除操作	逻辑删除（free=0）

5.2 思考问题解答

问题1：实现 hashfile_update()

int hashfile_update(int fd, int keyoffset, int keylen, void *buf) {
    int offset = hashfile_findrec(fd, keyoffset, keylen, buf);
    if (offset != -1) {
        lseek(fd, offset + sizeof(struct CFTag), SEEK_SET);
        return write(fd, buf, hfh.reclen);
    }
    return -1;
}

问题2：内核级实现困难

• 需要修改VFS层
• 处理文件锁和并发
• 缓存管理复杂
• 调试困难

5.3 实验体会

1. 散列文件优势：随机访问效率高，适合关键字查找场景

2. 冲突处理：线性探测简单但可能产生聚集，改进方案包括二次探测、再散列

3. 文件结构设计：

   • 文件头存储元数据
   • 每条记录前有标签（CFTag）
   • 标签包含collision和free信息

4. Linux文件系统调用：熟练掌握creat/open/close/read/write/lseek等系统调用

5. 散列算法选择：根据数据分布选择合适的散列函数，避免聚集现象