judyhash judyhash is a software that provides several hash map (and set) based on Judy array.
Download

judyhash Ranking & Summary

judyhash Tags

hash maps hash maps Judy array Judy

judyhash Description

judyhash is a software that provides several hash map (and set) based on Judy array. judyhash is a software that provides several hash map (and set) based on Judy array. All these maps and sets are implemented using C++ programming language and have an API similar to that of SGI STL's hash_map (or std::unordered_map) and STL library.ALGORITHMS AND COMPLEXITYIn traditional hash tables http://en.wikipedia.org/wiki/Hash_table linear array is used for mapping a hash value to an element, most often by making modulo operation where divisor is the hash table size. Traditional hash tables has two main problems. The first one is hash table resizing, i.e. increasing it when there are too many elements and decreasing when only a few has table cells are actually used. The second problem is collisions.Instead of linear array, judyhash classes use a JudyL set of functions from Judy library (See url below). JudyL implements a high-performance map from an integer type to a pointer type (actually a map from Word_t to Word_t which is capable to store both int and void *).As a result we have:1) some overhead for mapping a hash value to an element (actuallychain of elements) (JudyL is slower than 'pointer');2) hash value in a range (the default on 32/64 platforms) andtherefore very rare collisions;3) dynamic resizing of hash table, i.e. memory is allocated (and freed)as soon as it is needed (or unneeded anymore).In case of collisions judy_map_{l,m} and judy_set_{l,m} classes use a chaining technique to resolve the collision, i.e. external storage is used for storing conflicting elements. judy_{set,map}_l classes use list, while judy_{set,map}_m use map (or set), this is why judy_{set,map}_m classes require Less predicate in addition to Equal.judy_map_kdcell is actually a C++ STL-like wrapper for JudyL functions and therefore both key and data should be of integer or pointer type.judy_set_cell is actually a C++ STL-like wrapper for Judy1 functions and therefore the type of key should be integer or pointer.

judyhash Related Software