search

srdja / Collections-C

A library of generic data structures for the C language.
http://srdja.github.io/Collections-C
GNU Lesser General Public License v3.0
2.8k stars 328 forks source link

Adding a Ternary Search Tree #133

Closed alkeldi closed 4 years ago

alkeldi commented 4 years ago

Hash tables are an excellent data structure for amortized constant time operations. But, calculating the hash is not actually O(1). It's more like O(h), where h is the length of the hashed key. With a ternary search tree, it's possible to get similar results to those obtained from a Hash Table without the need of resizing the table, or having extra unused entries as with the hash table.

srdja commented 4 years ago

Yeah, it sounds good. We already have two different tables with different time/space properties, so I don't see why we shouldn't add another. More tools in the toolbox.