Earticle

초록

영어

A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Due to its very fast mapping operation of O(1), it has been widely used in various areas such as databases, bioinformatics, and distributed computing. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In order to fully exploit the performance of such modern computer architectures, the data structures and algorithms considering parallelism become more important than ever. This paper implements three cache-conscious hashing methods, linear hashing and chained hashing, and also, a modern hashing method, hopscotch hashing, and analyzes their performance under Intel 32-core CPU of Nehalem microarchitecture. We implement each hashing method using state-of-the-art techniques such as lock-free data structures, especially based on compare-and-swap (CAS) operations, and refinable data structures. To the best of our knowledge, the work done by this paper is the first work analyzing the performance of three all hashing methods under the same implementation framework. Experimental results using data of 223 (i.e., about eight millions) key-value pairs shows that lock-free linear hashing is the best for insert operation among three hashing methods, and lock-free chained hashing is the best for lookup operation. Hopscotch hashing shows the second best performance of lookup operation. However, hopscotch hash table size is much bigger than other hash table size. Through experiments, we have found that the hopscotch hashing is relatively not efficient than other hash methods.

목차

Abstract
 1. Introduction
 2. Related work
  2.1. Linear hashing
  2.2. Chained hashing
  2.3. Hopscotch hashing
 3. Implementation
  3.1. Lock-free linear hashing
  3.2. Lock-free chained hashing
  3.3. Refinable lock-based hopscotch hashing
 4. Performance evaluation
  4.1. Experimental data and experiment environment
  4.2. Insert operation performance
  4.3. Lookup operation performance
  4.4. Hash table size
 5. Conclusions
 Acknowledgements

키워드

저자

• Euihyeok Kim [ Department of Information & Communication Engineering, Daegu Gyeongbuk Institute of Science & Technology ]
• Min-Soo Kim [ Department of Information & Communication Engineering, Daegu Gyeongbuk Institute of Science & Technology ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Control and Automation

• 간기

  월간

• pISSN

  2005-4297

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605