[WIL]🙈PINTOS_KAIST : Project 3. VIRTUAL MEMORY (1) : HASH TABLE 🙉

🚫 현재 글은 정확하지 않은 정보가 있을 수 있습니다. 언제든지 틀린 부분에 대해 댓글을 달아주세요! 🚫

0. Hash Table이란 뭔가요?

Hash Table이전에 Hashing에 대해 이해하면 Hash Table에 대한 이해가 빠르다.

 

(1) Hashing이란?

 '콜라', '환타', '사이다'를 임의의 자료구조에 저장한다고 하자. 예시가 3개일때는 찾기가 빠르지만 세상에 있는 모든 음료수를 저장한다고 할때, 해당 음료를 저장하고  원하는 음료를 자료구조에서 검색하는 시간은 비효율적일 것이다. 그래서 hash funtion을 통해 저장하고자 하는 값을 임의의 int형(숫자)로 변환하여 저장한다. 즉, 문자를 가져와 숫자로 변환하는 과정을 해싱(Hashing)이라고 한다.그리고 글자를 특정 숫자로 변환하는데 사용하는 코드를 해쉬 함수(hash funtion)이다.

'콜라' -> 123
'환타' -> 160
'사이다' -> 170

 

(2) Hash Table이란?

그럼 Hash Table은? 쌍으로 이루어진 값(ex: '키': 168, '나이': 20 )들의 리스트이다.  첫번째 항목은 키(key)라고 부르고, 두 번째 항목은 값이라고 부른다. keys값들은 hash function을 통해 hashing이 진행되고, 진행된 값들은 buckets이라는 곳에 저장한다. Hash Table이 검색속도가빠른이유는 하나하나 찾지 않고 hashing이 진행된 keys값들로 찾기 때문에 O(1)이 소요된다.

 

(3) 어쩜 그럼 Hash Table은 완벽한 자료구조인가요?

  Hash Table은 좋은 자료구조이지만, 세 요인에 따라서 효율성이 정해진다. 

 

•  해시 테이블에 얼마나 많은 데이터를 저장하는가 
• 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
• 어떤 해시 함수를 사용하는가. 

적은 셀에 많은 데이터를 저장하면 충돌이 많을 테고, 해시 테이블의 효율성은 떨어질 것이다. 마지막 해시 함수가 효율성을 좌우 하는 이유는 해시 함수를 통해 해싱이 진행된 특정 key값들이 특정 숫자에만 몰려 충돌이 일어날 경우이다. 좋은 해시 함수란 사용 간능한 모든 (bucket의 )셀에 데이터를 분산시키는 함수이다. 데이터를  넓게 퍼트릴 수록 충돌이 적기 때문이다. 

 

충돌 횟수를 줄어들 수록 해시 테이블의 효율성은 높다. 이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 저장공간을 확보하는 것이다. 하지만 10개 저장하고 싶다고 해시 테이블에 셀이 100000개면 충돌이 일어날 가능성은 적지만 메모리를 너무 많이 사용하게 되어 공간복잡도가 늘어나게된다. 해시 테이블은 반드시 충돌 조정을 수행해야하며, 좋은 해시테이블은 많은 메모리를 낭비하지 않으며 균형을 유지하며 충돌을 피하는 것이다. 

 

1. PINTOS에서의 Hash Table

pintos에서 해시 테이블은 hash 구조체로 표현되어 있다. hash 구조체의 실제적인 멤버는 숨겨져 있다. 즉 해시 테이블을 사용하는 코드는 직접적으로 접근할 수 없도록 숨겨져 있다.  해시 테이블은 struct hash_elem 타입의 원소로 연산하게 된다.

 

 (1) struct hash

pintos에서 bucket_cnt = 4 로 초기화 되어 있고, 리스트형 buckets가 존재한다. Hashing function을 통해 hashing될 값들이 list buckets에 담긴다.

/* Hash table. */
struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

 

 (2) hash_hash_func 

hash_hash_func은 어떻게 들어올 지 모르는 각 hash_elem에 값에 대비한 함수이다. hash_elem이 다양한 자료형으로 들어올 수 있으니, 해당 자료형에 맞춰 hash_bytes, hash_string, hash_int를 알맞게 사용하면 된다. 이 각각의 함수가 hash_funtion이다. 각 함수들은 Fowler-Noll-Vo의 비 암호 해시함수를 사용하고 있으며, define으로 정의된 소수들을 곱하고 XOR 연산을 통해 Hash collision을 막는다.

/* include/lib/kernel/hash.h  */
typedef uint64_t hash_hash_func (const struct hash_elem *e, void *aux);

/* include/lib/kernel/hash.h  */
uint64_t hash_bytes (const void *, size_t);
uint64_t hash_string (const char *);
uint64_t hash_int (int);

   

    1) hash_byte

/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
#define FNV_64_PRIME 0x00000100000001B3UL
#define FNV_64_BASIS 0xcbf29ce484222325UL

/* Returns a hash of the SIZE bytes in BUF. */
uint64_t
hash_bytes (const void *buf_, size_t size) {
	/* Fowler-Noll-Vo 32-bit hash, for bytes. */
    
	const unsigned char *buf = buf_;
	uint64_t hash;

	ASSERT (buf != NULL);

	hash = FNV_64_BASIS;
	while (size-- > 0)
		hash = (hash * FNV_64_PRIME) ^ *buf++;

	return hash;
}

 

 

 2) hash_string

/* Returns a hash of string S. */
uint64_t
hash_string (const char *s_) {
	const unsigned char *s = (const unsigned char *) s_;
	uint64_t hash;

	ASSERT (s != NULL);

	hash = FNV_64_BASIS;
	while (*s != '\0')
		hash = (hash * FNV_64_PRIME) ^ *s++;

	return hash;
}

 

 3) hash_int 

uint64_t
hash_int (int i) {
	return hash_bytes (&i, sizeof i);
}

 

(3) hash_init

/* Initializes hash table H to compute hash values using HASH and
   compare hash elements using LESS, given auxiliary data AUX. */
/* hash funtion들을 사용하여 hash table을 초기화한다. */
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;
}

 

(4) hasy_entry(elem, type, member)

hash_elem 구조체의 포인터인 elem 구조체를 포함한 구조체의 포인터를 반환하는 함수이다. 

#define hash_entry (elem, type, member) { /* Omit details */ }

 

(5) rehash 

버킷당 요소가 쏠리지 않도록 관리

/* Element per bucket ratios. */
#define MIN_ELEMS_PER_BUCKET  1 /* Elems/bucket < 1: reduce # of buckets. */
#define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
#define MAX_ELEMS_PER_BUCKET  4 /* Elems/bucket > 4: increase # of buckets. */

/* Changes the number of buckets in hash table H to match the
   ideal.  This function can fail because of an out-of-memory
   condition, but that'll just make hash accesses less efficient;
   we can still continue. */
static void
rehash (struct hash *h) {
	size_t old_bucket_cnt, new_bucket_cnt;
	struct list *new_buckets, *old_buckets;
	size_t i;

	ASSERT (h != NULL);

	/* Save old bucket info for later use. */
	old_buckets = h->buckets;
	old_bucket_cnt = h->bucket_cnt;

	/* Calculate the number of buckets to use now.
	   We want one bucket for about every BEST_ELEMS_PER_BUCKET.
	   We must have at least four buckets, and the number of
	   buckets must be a power of 2. */
	new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
	if (new_bucket_cnt < 4)
		new_bucket_cnt = 4;
	while (!is_power_of_2 (new_bucket_cnt))
		new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);

	/* Don't do anything if the bucket count wouldn't change. */
	if (new_bucket_cnt == old_bucket_cnt)
		return;

	/* Allocate new buckets and initialize them as empty. */
	new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
	if (new_buckets == NULL) {
		/* Allocation failed.  This means that use of the hash table will
		   be less efficient.  However, it is still usable, so
		   there's no reason for it to be an error. */
		return;
	}
	for (i = 0; i < new_bucket_cnt; i++)
		list_init (&new_buckets[i]);

	/* Install new bucket info. */
	h->buckets = new_buckets;
	h->bucket_cnt = new_bucket_cnt;

	/* Move each old element into the appropriate new bucket. */
	for (i = 0; i < old_bucket_cnt; i++) {
		struct list *old_bucket;
		struct list_elem *elem, *next;

		old_bucket = &old_buckets[i];
		for (elem = list_begin (old_bucket);
				elem != list_end (old_bucket); elem = next) {
			struct list *new_bucket
				= find_bucket (h, list_elem_to_hash_elem (elem));
			next = list_next (elem);
			list_remove (elem);
			list_push_front (new_bucket, elem);
		}
	}

	free (old_buckets);
}