Pintos의 hash.h와 hash.c는 커널 내에서 사용할 수 있는 범용 해시 테이블 구현을 제공합니다. 이 구조는 특히 supplemental page table (SPT) 같은 VM 구현에서 자주 사용되며, 아래에 그 사용법을 구조체 설계부터 삽입/탐색/삭제까지 전반적으로 설명하겠습니다.

1. 구조체 설계

해시 테이블에 삽입될 구조체는 반드시 struct hash_elem 멤버를 포함해야 합니다.

#include "threads/synch.h"
#include "lib/kernel/hash.h"

struct my_entry {
    int key;
    int value;
    struct hash_elem elem; // 필수
};

2. 해시 함수 및 비교 함수 정의

// 해시 함수
static uint64_t my_hash(const struct hash_elem *e, void *aux UNUSED) {
    struct my_entry *entry = hash_entry(e, struct my_entry, elem);
    return hash_int(entry->key);
}

// 비교 함수 (정렬 기준)
static bool my_less(const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
    struct my_entry *ea = hash_entry(a, struct my_entry, elem);
    struct my_entry *eb = hash_entry(b, struct my_entry, elem);
    return ea->key < eb->key;
}

3. 해시 테이블 초기화

struct hash my_hash_table;

void init_table(void) {
    hash_init(&my_hash_table, my_hash, my_less, NULL);
}

4. 삽입

struct my_entry *e = malloc(sizeof(struct my_entry));
e->key = 42;
e->value = 100;

struct hash_elem *prev = hash_insert(&my_hash_table, &e->elem);
if (prev != NULL) {
    // 기존 키가 있었다면 prev가 반환됨 → e는 삽입되지 않음
    free(e);
}

5. 탐색

struct my_entry lookup;
	lookup.key = 42;

struct hash_elem *found = hash_find(&my_hash_table, &lookup.elem);
if (found != NULL) {
    struct my_entry *e = hash_entry(found, struct my_entry, elem);
    printf("Found value: %d\\n", e->value);
}

6. 삭제

struct hash_elem *deleted = hash_delete(&my_hash_table, &lookup.elem);
if (deleted != NULL) {
    struct my_entry *e = hash_entry(deleted, struct my_entry, elem);
    free(e); // 직접 메모리 해제 필요
}