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

## 一、实验内容

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

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

## 二、实验设计

### 2.1 文件结构

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

### 2.2 数据结构

```cpp
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 散列函数

```cpp
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 保存记录（处理冲突）

```cpp
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 查找记录

```cpp
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 编译与运行

```bash
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 测试命令

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

# 运行
./hashfile_test

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

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

### 4.1 创建散列文件

```cpp
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()**

```cpp
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. **散列算法选择**：根据数据分布选择合适的散列函数，避免聚集现象