readme

来自「CKHash is an implementation of Cuckoo Ha」· 代码 · 共 80 行

Introduction
------------

Cuckoo Hashing was proposed by Pagh and Rodler (2001). The idea is to build a
dictionary data structure with two hash tables and two different hash functions.
The performance of applying Cuckoo Hashing to the real-world problem is very
promising in terms of memory consumption and lookup time (Jaruskulchai and
Kruengkrai, 2002).

CKHash is an implementation of Cuckoo Hashing that can receive the input in
the form of strings directly. The original source code can be found from this
url: http://www.it-c.dk/people/pagh/papers/cuckoo.tar. You can use functions
in CKHash by simply linking the object file with your program.
See ``test_CKHash.c'' and ``Makefile'' for more details.


Quick Start
-----------

(1) In the CKHash base directory, type:

make

(2) To test that the program works properly, type:

./test_CKHash

   You should get:

Test ``insert'' function
ckh_insert( apple, 0 ) (1)
ckh_insert( banana, 1 ) (1)
ckh_insert( banter, 2 ) (1)
ckh_insert( baseball, 3 ) (1)
ckh_insert( blueberry, 4 ) (1)
ckh_insert( brown, 5 ) (1)
ckh_insert( browser, 6 ) (1)
ckh_insert( camera, 7 ) (1)
ckh_insert( can, 8 ) (1)
ckh_insert( cantaloupe, 9 ) (1)
Current data size = 10, table size = 16

Test ``lookup'' function
        ckh_lookup: banana (1)
        ckh_lookup: cherry (0)

Test ``get'' function
        ckh_get: banana (1)
        ckh_get: cherry (-999999999)

Test ``increase value'' function
        ckh_increase_value: banana (1)
        ckh_get: banana (2)

Test ``delete'' function
        ckh_delete: cherry (0)
        ckh_delete: apple (1)
        ckh_delete: banana (1)
        ckh_delete: banter (1)
        ckh_delete: baseball (1)
        ckh_delete: blueberry (1)
        ckh_delete: brown (1)
        ckh_delete: browser (1)
        ckh_delete: camera (1)
        ckh_delete: can (1)
        ckh_delete: cantaloupe (1)
Current data size = 0, table size = 2


References
----------

Chuleerat Jaruskulchai and Canasai Kruengkrai. 2002. Building Inverted Files
Through Efficient Dynamic Hashing. Proceedings of the Fifth National Computer
Science and Engineering Conference (NCSEC-2002).
 
Rasmus Pagh and Flemming Friche Rodler. 2001. Cuckoo Hashing, Proceedings of
ESA 2001, Lecture Notes in Computer Science, vol. 2161.