Top 10 datastructure Open-Source Projects

FluidFramework

12 4,613 10.0 TypeScript

Library for building distributed, real-time collaborative web applications

Project mention: FluidFramework: Build distributed, real-time collaborative web applications | news.ycombinator.com | 2024-01-11
staticvec

10 267 4.9 Rust

Implements a fixed-capacity stack-allocated Vec alternative backed by an array, using const generics.

Project mention: Posting asking if the Rust Reddit community is overly regulated gets regulated. | /r/programmingcirclejerk | 2023-05-27

This crate of mine for example is currently literally unusable until the deeply fundamental features that John Random kinda-sorta removed in this pull request, ostensibly in preparation for whatever shittily stated syntax is ultimately establihed by whatever the hell "keyword generics" actually is (I really don't know, like this isn't a joke, I fundamentally do not understand what the fuck they're proposing at all in any way or how it's meaningfully and usefullly different from the previous syntax).
SurveyJS

surveyjs.io
sponsored

Open-Source JSON Form Builder to Create Dynamic Forms Right in Your App. With SurveyJS form UI libraries, you can build and style forms in a fully-integrated drag & drop form builder, render them in your JS app, and store form submission data in any backend, inc. PHP, ASP.NET Core, and Node.js.
hamt

7 259 6.9 C

A hash array-mapped trie implementation in C

Project mention: Visual Introduction to Hash-Array Mapped Tries (HAMTs) | news.ycombinator.com | 2023-08-24

This isn't a very good explanation. The wikipedia article isn't great either. I like this description:
https://github.com/mkirchner/hamt#persistent-hash-array-mapp...
The name does tell you quite a bit about what these are:
* Hash - rather than directly using the keys to navigate the structure, the keys are hashed, and the hashes are used for navigation. This turns potentially long, poorly-distributed keys into short, well-distributed keys. However, that does mean you have to compute a hash on every access, and have to deal with hash collisions. The mkirchner implementation above calls collisions "hash exhaustion", and deals with them using some generational hashing scheme. I think i'd fall back to collision lists until that was conclusively proven to be too slow.
* Trie - the tree is navigated by indexing nodes using chunks of the (hash of the) key, rather than comparing the keys in the node
* Array mapped - sparse nodes are compressed, using a bitmap to indicate which logical slots are occupied, and then only storing those. The bitmaps live in the parent node, rather than the node itself, i think? Presumably helps with fetching.
A HAMT contains a lot of small nodes. If every entry is a bitmap plus a pointer, then it's two words, and if we use five-bit chunks, then each node can be up to 32 entries, but i would imagine the majority are small, so a typical node might be 64 bytes. I worry that doing a malloc for each one would end up with a lot of overhead. Are HAMTs often implemented with some more custom memory management? Can you allocate a big block and then carve it up?
Could you do a slightly relaxed HAMT where nodes are not always fully compact, but sized to the smallest suitable power of two entries? That might let you use some sort of buddy allocation scheme. It would also let you insert and delete without having to reallocate the node. Although i suppose you can already do that by mapping a few empty slots.
idx

1 78 0.0 Clojure

maps, sets and vectors with on-demand secondary indexes.
data-structure-typed

0 77 9.7 TypeScript

Javascript Data Structure & TypeScript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree, AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack.
treap

0 63 1.8 Haskell

:leaves: :deciduous_tree: :fallen_leaf: Efficient implementation of the implicit treap data structure
gograph

0 47 7.2 Go

A golang generic graph library that provides mathematical graph-theory and algorithms.
InfluxDB

www.influxdata.com
sponsored

Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
library

1 32 6.6

Data structures, algorithms, and C++ reference library (by eugnsp)
lbst

1 7 0.0 Python

Log-Balanced Search Tree
post-order-heap

1 0 0.0 C++

C++ implementation of post-order heap, as described by Harvery & Zatloukal. Adapted for heaps of any degree.

NOTE: The open source projects on this list are ordered by number of github stars. The number of mentions indicates repo mentiontions in the last 12 Months or since we started tracking (Dec 2020). The latest post mention was on 2024-01-11.