HArray

Probably, this is most optimized Trie structure in the World ! Thats all what you need know about this project :)

HArrayInt - Key\Value In Memory structure for 32bit keys

HArray - Key\Value In Memory structure for keys with variety size

HArrayChar - Wrapper for HArray with interfaces: char key, uint32 keyLen, char value, uint32 valueLen

HArrayUniqueIntValueList - Wrapper for HArray with inteterfaces: uint32* key, uint32 keyLen, List\<uint32> listOfUniqueValues

Start overview from Benchmarks

Overview

High optimized Trie structure implemented in more than 8K lines
Tested on 1 Billion keys succesfully
Keys with variable length inside one instance of the container
Without any Stop World events such as Rebuild/Rehashing on Insert key.
Without any Hash Functions, the container has adpative algorithm for different nature of keys
Scan by Prefix/Scan by Range functionality as bonus
All Keys are sorted. Ability to set your Custom Order of Keys
Predictable behaviour even in worst case: smoothly consuming memory, almost constantly latency on insert/lookup
Prefix Compression helps reduce memory when keys have the same prefix: urls, file paths, words etc.
Serialize/Deserialize from/to file at a speed close to the max speed of the hard drive
Fair Delete operation with smoothly dismantling each Key. Dead fibres are used for insert new keys, so structure perfect works in massive insert/delete scenarios.

Build Library and Benchmarks

Prerquisites

The following need to be installed and configured on development box:

C++ development tools.
CMake.

Build on Linux and Mac

mkdir build
cmake -Bbuild
cd build && make

To build release version of the library and benchmarks run instead:

cmake -Bbuild -DCMAKE_BUILD_TYPE=Release

The library (libharray.a) and benchmark application (HArrayBenchmark) will be created in build folder.

Build on Windows

md build
cmake -Bbuild
msbuild build\HArray.sln

To build release version run:

msbuild build\HArray.sln /property:Configuration=Release

The benchmark application HArrayBenchmark.exe together with static library libharray.lib will be in build\Debug or build\Release folder.

Why we love Trie ? Because it has much more functionality and stability than Hashtables and much more faster than Binary Trees. Let's compare properties:

alt tag

Trie ? I heard about Trees and Hastables but don't know anything about Trie

Explain me as for Beginners

Examples

Initialize container

#include "HArray.h"

HArray ha;
ha.init(); //ha.init(24) set your custom capacity for big datasets

Insert a key

uint32 key[] = { 10, 20, 30, 40 };
uint32 keyLen = sizeof(key) / 4; //in key segments
uint32 value = 1;

ha.insert(key, keyLen, value);

Get value by key. Will return 0 if key is not found

uint32 value;
if(ha.getValueByKey(key, keyLen, value))
{
   printf("%d", value)
}
else
{
   //key is not found
}

Get all keys by range from min key to max key.

HArrayPair pairs[5];
uint32 pairsSize = 5;

uint32 minKey[] = { 10, 10 };
uint32 minKeyLen = sizeof(minKey) / 4; //in key segments

uint32 maxKey[] = { 20, 20 };
uint32 maxKeyLen = sizeof(maxKey) / 4; //in key segments

uint32 count = ha.getKeysAndValuesByRange(pairs, pairsSize, minKey, minKeyLen, maxKey, maxKeyLen);
for (uint32 i = 0; i < count; i++)
{
   uint32* key = pairs[i].Key;
   uint32 keyLen = pairs[i].KeyLen;

   uint32 value = pairs[i].Value;

   //here your code
}

Scan all keys through visitor

bool visitor(uint32* key, uint32 keyLen, uint32 value, uchar8 valueType, void* pData)
{
   //handle founded key here
   // ...

   //return true to continue scaning or false otherwise
   return true;
}

//Start scanning

void* pData = 0; //useful data in context

ha.scanKeysAndValues(&visitor, pData);

Serialize/Deserialize containter from/to file

ha.saveToFile("c:\\dump");

ha.loadFromFile("c:\\dump");

Check if container has part of key

uint32 key[] = { 10, 20, 30 };
uint32 keyLen = sizeof(key) / 4; //in key segments

if(ha.hasPartKey(key, keyLen))
{
   //code here
}

Set specific comparator to redefine order of keys in the container.

float key[] = { 10.0, 20.0, 30.0 };
uint32 keyLen = sizeof(key) / 4; //in key segments

uint32 value = 1;

//Set float comparator for right sorting
//Another options: setStrComparator, setInt32Comparator, setUInt32Comparator 
//or define your custom comparator through setCustomComparator
ha.setFloatComparator();

ha.insert((uint32*)key, keyLen, value);

Delete Key and Value from container

ha.delValueByKey(key, keyLen);

How to Run

git clone github.com/Bazist/HArray.git
cd HArray/HArray
make
./HArray

License

The code is licensed under the GNU General Public License v3.0, see the LICENSE file for details.

Bazist / HArray

readme