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

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

Start overview from Benchmarks

Overview

• High optimized Trie structure implemented in more than 8K lines
• Tested on 1 Billion keys succesfully
• 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.

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:

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);
uint32 value = 1;

ha.insert(key, keyLen, value);

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

uint32* pValue = ha.getValueByKey(key, keyLen);

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);

uint32 maxKey[] = { 20, 20 };
uint32 maxKeyLen = sizeof(maxKey);

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);

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);

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);

License

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