jun-wiki
해시 테이블
이번 프로젝트 2하며
리스트를 자주 사용했는데
아무래도 선형탐색이다보니 좀 느린게 불만이었다
그리고 Pintos에서는 해시테이블이 존재한다…
없어도 괜찮지만 사용하면 훨씬 좋기에 어떻게 쓰는지 알아보자
미리 요약해보자면 배열 + 해시/비교 함수로 동작하는 간단한 구조로
꼭 해야 할 일은 3가지만 해주면 된다
-
“엔트리” 구조체에
struct hash_elem넣고 -
키에 맞는
hash_hash_func와hash_less_func를 작성하고 -
hash_init()으로 테이블을 만들고hash_insert/find/delete등을 호출
언제든 써먹기 위한 치트시트와 함께 좀 더 알아보자
준비
일단 기본적으로 사용할 구조체에
struct hash_elem을 넣어줘야 한다
struct list_elem 넣어주듯이
struct foo {
KeyType key; // 키(예: void* upage, int fd, char* name 등)
/* ... 값 필드 ... */
struct hash_elem he; // 필수
};
그리고 콜백 함수도 2개 정도 만들어놔야 준비 끝이다
/* 해시 함수 */
/* 같은 키면 같은 값이 나오게 한다 */
static uint64_t foo_hash(const struct hash_elem *e, void *aux) {
const struct foo *f = hash_entry(e, struct foo, he);
// 포인터/정수면 이렇게
return hash_bytes(&f->key, sizeof f->key);
// 문자열이면 이렇게
return hash_string(f->key_str);
}
/* 정렬(less) 함수: 키만 비교 */
/* 동치 판단 내린다 */
static bool foo_less(const struct hash_elem *a,
const struct hash_elem *b, void *aux) {
const struct foo *fa = hash_entry(a, struct foo, he);
const struct foo *fb = hash_entry(b, struct foo, he);
// 포인터/정수면 이렇게
return fa->key < fb->key;
// 문자열이면 이렇게
return strcmp(fa->key_str, fb->key_str) < 0;
}
해시, 정렬 둘다 문자열이나 포인터주소 둘 중 하나로 통일 해줘야 한다
코드 그대로return두 개 넣으면 터지니까 상황에 맞춰 둘 중 하나로 쓰자
당연하게도 위에것만 보고 이해하기는 어렵기에 추가 설명 하겠다
알다시피 해시는 버킷 안에 배열하고 키값으로 이를 찾는 자료구조다
그리고 버킷안에 여러 값이 존재할 경우 요구하는 값을 정확히 찾아야 하는데 이를 위해 사용하는 게 less(정렬)다
해시 없으면 전부 뒤져야 해서 사실상 리스트고
less 없으면 그냥 찾질 못한다
생성/삽입/검색/삭제/파기
테이블 생성
struct hash ht;
/* aux가 필요 없으면 NULL */
hash_init(&ht, foo_hash, foo_less, NULL);
삽입
struct foo *x = malloc(sizeof *x);
x->key = K; /* 키 채우기 */
/* ... 값 필드들도 채우기 ... */
struct hash_elem *old = hash_insert(&ht, &x->he);
/* 이미 같은 키가 들어있으면 old != NULL 이고, 새 원소 x는 넣지 않음 */
if (old != NULL) {
free(x);
}
검색
여기서 두 가지 방법이 있다
포인터를 갖고 있을때와 키밖에 모를때 말이다
포인터 있으면 그냥 쓰면 되지만
키밖에 모를때는 포인터 알아와야 하는데 이게 어렵거나 할때에 쓸 수 있다
어차피 hash_find()에서는 hash_func(해시)와 less_func(정렬/동치판정)을 통해 원소와 같은 키 갖는 실제 원소를 찾는다
키만 맞으면 나머지는 필요 없다는 거다
그래서 검색과 삭제만 할때에는 실제 테이블에 없는 원소라도,
키 필드만 채운 임시(스택) 구조체를 하나 만들고 그 안의 he 주소(= struct hash_elem *)를 넘겨도 된다
이게 가짜 엔트리다
어지간해선 포인터도 있을 거긴 하다
그래도 혹시 모르기도 하고 알고 있어서 나쁠건 없다
실물 포인터 O
/* p가 정말 테이블에 들어있는지 확인하고 싶을 때 */
struct hash_elem *e = hash_find(&ht, &p->he);
ASSERT(e == &p->he); /* 들어있다면 자기 자신을 반환 (assert는 옵션이다) */
실물 포인터 X (가짜 엔트리 사용)
/* 키만 채운 임시(스택) 구조체 */
struct foo key_only = { .key = K };
/* &key_only.he 를 넘겨서 검색 */
struct hash_elem *e = hash_find(&ht, &key_only.he);
/* 실제 포인터로 복구 */
struct foo *found = e ? hash_entry(e, struct foo, he) : NULL;
가짜 엔트리는 find/delete 전용 패턴이다
해시와 정렬이 포인터 말고 키만 사용하도록 작성되어있어야 한다
추가로 실제 포인터로 복구가 필요한 이유는
hash_find()에서 struct hash_elem* 테이블이 쓰는 노드 내부 노드만 돌려주기에 우리가 쓸 struct foo의 주소를 알기 위해 쓴다
이를 위해 list_entry처럼 hash_entry로 컨테이너 타입으로 돌려 받는다
삭제
실물 포인터 O
/* 이미 p를 알고 있다면 바로 삭제 가능 */
struct hash_elem *victim_he = hash_delete(&ht, &p->he);
if (victim_he) {
/* 테이블에서 제거만 했으므로 메모리 해제는 사용자 몫 */
free(p);
}
실물 포인터 X (가짜 엔트리 사용)
/* 키만 채운 임시(스택) 구조체 */
struct foo key_only = { .key = K };
/* &key_only.he 를 넘겨서 삭제 */
struct hash_elem *victim_he = hash_delete(&ht, &key_only.he);
if (victim_he) {
struct foo *victim = hash_entry(victim_he, struct foo, he);
free(victim);
}
가짜 엔트리는 검색/삭제 전용임을 유의하자
파기
/* 각 엔트리를 free하는 destructor 콜백 함수 */
static void foo_free(struct hash_elem *e, void *aux) {
struct foo *f = hash_entry(e, struct foo, he);
free(f); // 여기서 메모리 해제
}
/* 전체 파기(메모리까지 정리) */
hash_destroy(&ht, foo_free);
/* 또는 내용만 비우기 */
hash_clear(&ht, foo_free);
hash_destroy()/hash_clear()는 테이블에서 원소를 빼주기만 하므로,
엔트리 메모리 해제가 필요하면 반드시 destructor 콜백에서 free해야 한다
순회
반복자(iterator)패턴과 일괄 적용(apply) 방식이 있다
어지간해선 반복자 쓰는게 편한 거 같다
반복자
struct hash_iterator it;
/* 시작점 */
hash_first(&it, &ht);
/* 다음이 있으면 계속 이동 */
while (hash_next(&it)) {
struct foo *f = hash_entry(hash_cur(&it), struct foo, he);
/* 수행할 코드 여기다가 */
}
일괄 적용
/* 사용할 콜백 함수 */
static void dump_one(struct hash_elem *e, void *aux) {
struct foo *f = hash_entry(e, struct foo, he);
/* 수행할 코드 여기다가 */
}
/* 일괄 적용하는 함수 */
hash_apply(&ht, dump_one);
hash_apply라이브러리 안에서 for문으로 순회돈다
딱 보면 알수 있듯이
굳이 일괄 적용 쓸 이유가 없다
리스트 쓰던 거 마냥 반복자 쓰자
뭐, 더 짧고 간결하게 쓰고 싶다면 apply 방식도 좋다
그치만 중간에 멈출 수 없다는 것에 유의하자
그리고 둘 다 순회 중 테이블 수정 금지다
순회 끝난 뒤 실제 삭제 하겠다면 아래 패턴 활용하자
// 1) 지울 후보를 모집
struct hash_elem *bin[128]; size_t n = 0;
struct hash_iterator it;
hash_first(&it, &ht);
while (hash_next(&it)) {
struct foo *f = hash_entry(hash_cur(&it), struct foo, he);
if (need_delete(f) && n < 128) bin[n++] = &f->he;
}
// 2) 순회 끝난 뒤 실제 삭제
for (size_t i = 0; i < n; ++i) {
struct hash_elem *victim = hash_delete(&ht, bin[i]);
if (victim) free(hash_entry(victim, struct foo, he));
}
여담
추가 정보로 여러 인덱스 필요하다면 구조체에 hash_elem 여러개 박아두자
예시
struct foo { int id; char *name; struct hash_elem by_id; struct hash_elem by_name; };