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
- 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:
Initialize container
#include "HArray.h"
HArray ha;
ha.init(); //ha.init(24) set your custom capacity for big datasetsInsert 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);The code is licensed under the MIT license, see the LICENSE file for details.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent