[자료구조][Linux] Hash Table(해시 테이블)

https://subscription.packtpub.com/book /application_development/9781788833738/4/ch04lvl1sec28/hash-tables

해시 테이블을 한마디로 정의하면 공간을 팔아서 성능을 얻는 알고리즘이다...

해시 테이블을 궁극의 탐색 알고리즘이라고 부르기도 하는데, 무려 O(1)의 시간복잡도를 갖기 때문이다. 

(물론 O(n)이 최악이다)

 

blog[1] = "123123"

 

라는 딕셔너리가 있다고 가정해보자. 

 

그러면 123123이라는 데이터를 해시함수의 매개변수를 입력한다. 

해시함수는 123123이라는 데이터를 1이라는 주소값으로 바꿔서 리턴해준다. 

 

해시 함수는 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 통계적으로 봤을 때 7~80%를 넘으면 성능 저하가 나타난다고 한다...

 

해시 테이블에서는 크게 두가지의 문제가 나타날 수 있다. 

1. Collision

해시함수가 123123도 1을 return하고, 124124도 1를 return하면 큰 문제가 생길 것이다.. 이것이 collision이다. 

2. Cluster

일부 지역의 주소들을 집중적으로 반환할 때. 

 

 

 

 

Hash Table은 크게 여러 bucket들, 그 안에 한 데이터가 들어갈 수 있는 slot으로 이루어져 있다. 

hash 함수는 버킷의 번호만 리턴해준다. bucket 안에서는 들어오는 순서대로 data를 삽입한다. 

 

버킷이 넘칠 때

1. 선형 탐색법

선형 탐색법(Linear Probing) 으로 원하는 버킷이 아니라 다른 버킷에라도 데이터를 넣는 방법이다. 

바로 옆 버킷에 넣는 방법이 그나마 좋다고 평가되는데 문제는, 삭제에 굉장히 취약하다는 것이다.

 

2. rehash

대체 칸을 찾는 해시 함수를 별도로 두는 방법이다. 

 

hash함수로 해시 값을 찾는다. 만약 이 칸이 차있다면, hash2 함수로 대체 버킷을 찾고 값을 기록한다. 재해시 함수는 원래와 가급적이면 다른 해시 값을 찾는게 좋다. 

활용

캐시

- 페이지 캐시 : 파일의 내용 저장하는 캐시

- 버퍼 캐시 : 파일 시스템의 메타 데이터와 관련된 블록 저장. 2.4부터는 페이지 캐시 내부로 대부분 통합되었다고 한다!

 

 

 

---

여기까지가 개념이었고 이제 실제 리눅스에서 코드를 참조해보려고 한다. 

 

Linux Code

 

hash table에 넣을 원소 정의하기

struct mystruct {
     int data ;
     struct hlist_node my_hash_list ;
} ;

struct mystruct first = {
     .data = 10,
     .my_hash_list = 0    /* Will be initilaized when added to the hashtable */
} ;

 

hash table 정의하기

 15 #define DEFINE_HASHTABLE(name, bits)                                            \
 16         struct hlist_head name[1 << (bits)] =                                   \
 17                         { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

 

DEFINE_HASHTABLE(a, 3);

 

 

* rcu: read copy update

 57
 58 /**
 59  * hash_add_rcu - add an object to a rcu enabled hashtable
 60  * @hashtable: hashtable to add to
 61  * @node: the &struct hlist_node of the object to be added
 62  * @key: the key of the object to be added
 63  */
 64 #define hash_add_rcu(hashtable, node, key)                                      \
 65         hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
 66

hash_add(a, &first.next, first.data);

struct mystruct second = {
     .data = 20,
     .my_hash_list = 0    /* Will be initilaized when added to the hashtable */
} ;
struct mystruct third = {
     .data = 44,
     .my_hash_list = 0    /* Will be initilaized when added to the hashtable */
} ;
hash_add(a, &second.next, second.data);
hash_add(a, &third .next, third .data);

114 /**
115  * hash_for_each - iterate over a hashtable
116  * @name: hashtable to iterate
117  * @bkt: integer to use as bucket loop cursor
118  * @obj: the type * to use as a loop cursor for each entry
119  * @member: the name of the hlist_node within the struct
120  */
121 #define hash_for_each(name, bkt, obj, member)                           \
122         for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
123                         (bkt)++)\
124                 hlist_for_each_entry(obj, &name[bkt], member)

int bkt;
struct mystruct * current;
hash_for_each_entry(a, bkt, current, next){
    printk(KERN_INFO "data=%d is in bucket %d\n", current->data, bkt);
}

https://kernelnewbies.org/FAQ/Hashtables

 

 

 

[출처]

https://movefast.tistory.com/340

https://dohk.tistory.com/81