세 개의 테이블을 사용하는 쿠쿠 해시 테이블
Cuckoo Hashing with Three Hash Tables
- 주제(키워드) Key-value data structure , Cuckoo hashing , Hash table , Load factor , False negative
- 주제(기타) 전자/정보통신공학
- 설명문(URI) https://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART002614941
- 등재 KCI등재
- 발행기관 대한전자공학회
- 발행년도 2020
- URI http://www.dcollection.net/handler/ewha/000000176171
- 본문언어 한국어
초록/요약
해시 테이블은 대표적인 키-값 데이터 구조로 다양한 네트워크 어플리케이션에 사용되지만, 로드 비율이 증가할수록 해시 충돌이 증가한다는 단점이 있다. 충돌이 일어나면 원소를 삽입할 수 없고 삽입에 실패한 원소는 검색 시 거짓 음성을 초래한다. 본 논문에서는 제한된 메모리에서 쿠쿠 해시 테이블을 구축할 때, 테이블을 2개 사용하는 것보다 3개 사용하는 것이 검색 실패를 유발하는 오버플로우를 감소시키는데 효율적임을 제안한다. 즉 쿠쿠 해시 테이블에서 해시 테이블의 개수를 늘리면, 해시 충돌이 감소되고, 삽입 시 접근 횟수가 크게 감소하는 것을 알 수 있다. 실험을 통해 로드 비율이 증가함에 따라 테이블을 3개 사용하는 것이 같은 메모리를 사용할 때 오버플로우 측면에서 큰 성능 향상을 나타냄을 보였다.
more초록/요약
A hash table is a representative key-value data structure, which is frequently used in various network applications. Overflows can occur in insertion procedure because of hash collisions, and the overflows cause false negatives in search procedure. This paper claims that Cuckoo hashing with 3 hash tables (3-CH) has better performance than Cuckoo hashing with 2 hash tables (2-CH). In insertion procedure, the number of hash table accesses of 3-CH is much less than that of 2-CH, and in search procedure, that of 3-CH is slightly more than that of 2-CH. Additionally, using more tables in Cuckoo hashing can store more elements by reducing hash collisions. Therefore, 3-CH is more effective than 2-CH in a limited amount of memory. Performance evaluation results show that 3-CH has much lower overflow rates than 2-CH in the same amount of memory.
more