이번주에는 악명 높은 virtual memory를 구현하는 것이 목표입니다... (벌써 힘드네요)
Memory Management
Anonymous Page
Stack Growth
Memory Mapped Files
Swap In/Out
1주일 차에는 5개 중에 2개를 구현했습니다. 개념 공부를 찐득~허니 하느라고 생각보다 많이 못한 것 같지만? anonymous는 정말 힘들었다.
이번주에는 글에는 내가 궁금해서 깊게 고민해보았던 minor한 주제들에 대해서 정리해보려고 한다.
쓸모없는 개념이란건 없겠지만, 이것보다 더 주요한 것을 깊게 다뤘으면 좋았겠다 라는 후회?가 조금 든다.
bucekt_cnt 는 왜 4일까?
bool
hash_init (struct hash *h,
hash_hash_func *hash, hash_less_func *less, void *aux) {
h->elem_cnt = 0;
h->bucket_cnt = 4;
h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
h->hash = hash;
h->less = less;
h->aux = aux;
if (h->buckets != NULL) {
hash_clear (h, NULL);
return true;
} else
return false;
}hash를 초기화해주는 부분에서 왜 bucket의 개수가 1도 아니고 8도 아니고 10 아니고 개뜬금 숫자 4일까? 궁금해졌다.
해시 테이블에서 버킷의 개수는 일반적으로 2의 제곱수로 설정이 된다고 한다. (절대적인건 아니다.)
그 이유는 두가지 이유가 있다.
- 해시 함수가 반환하는 해시 값의 분포를 균등하게 만들기 위함이라고 한다.
분포가 균등해지면 뭐가 좋냐? 해시 테이블의 성능이 좋아지고 충돌이 최소화 된다.
- 하위 2비트만 이용하여 버킷 인덱스를 계산할 수 있다.
근데 뭐 버킷의 개수를 결정하는 데에는 다양한 방법들이 존재하며, 어떤 방법이 좋은지는 해시 함수의 특성이나 실제 데이터에 따라 다르다고 한다.
중요한건, 버킷의 개수가 너무 작으면 충돌이 더 많이 발생할 수 있고, 버킷의 개수가 너무 크면 불필요한 메모리 공간을 사용하게 된다는 단점이 있다.
뭐든 적절한게 좋지만 가장 어려운건 뭐다? 적절한거 찾는 거다~
우리는 어떤 hash 함수를 사용할까?
Fowler-Noll-Vo(FNV) hash 알고리즘을 사용한다.
hasy_bytes, hash_string 함수를 살펴보면 된다.
해싱 과정에서 각 바이트(또는 문자)를 XOR 연산하고, FNV prime 값과의 곱셈을 통해 해시 값을 갱신하는 방식으로 해시 값을 계산한다. 이러한 과정을 데이터의 모든 바이트에 대해 반복하면 입력 데이터의 해시 값이 계산된다. (그렇다고 한다. 나도 잘은 이해하지 못했다. 추후 시간이 나면 정리를 더 해봐야지... 기술 부채 하나더 적립이요~)
해당 알고리즘은 단순하고 빠른 해싱을 제공하는 특징을 가지고 있다. 그러나! 충돌 가능성이 높은 데이터 세트에서는 다른 해시 알고리즘보다 충돌이 발생할 가능성이 높다.
