How can I make a fast dictonary ( String => Pointer and Int => Pointer ) in C without a linear search? I need a few ( or more ) lines of code, not a library, and it must be possible to use it in closed-source software (LGPL, ...).
+6
A:
Use a Hash Table. A hash table will have a constant-time lookup. Here are some excerpts in C and an implementation in C (and Portuguese :).
Andrew Keeton
2009-08-25 19:11:59
Or a binary tree, if you can't use a hash.
derobert
2009-08-25 19:14:44
Hardly portuguese if the variable names and comments are in english? ;)
unknown
2009-08-25 19:20:34
It is *NOT* constant time.
San Jacinto
2009-08-25 20:00:40
It's GPL not LGPL, so you can't (legally) use it in CSS....
NVRAM
2009-08-25 20:25:48
A hash table can potentially do O(1) reads and expected amortized O(1) writes.
Captain Segfault
2009-08-28 22:15:10
+2
A:
You need to implement a Hash Table which stores objects using a hash code. The lookup time is constant.
A Binary Tree can traverse and lookup an element in log(n) time.
unknown
2009-08-25 19:13:48
A:
If you strings will be long, you cannot consider the "Hash table" as constant time! run-time depends on the length of the string! for long strings, this will cause problems. additionally, you have the problem of collisions with too small of a table or too poor of a hash function.
if you want to use hashing, please look at karp-rabin. if you want an algorithm dependent SOLELY upon the size of the word you are searching for, please look at aho-corasick.
San Jacinto
2009-08-25 20:04:40
It's constant time with respect to N (the number of strings), but may also vary with other factors (e.g. string length). The terminology "constant time" implies "with respect to the size/number of input values". Whether it's "performant enough" in this case is up for debate.
Andrew Coleson
2009-08-25 20:11:00
Not necessarily. When you have collisions, it is no longer constant with respect to the number of stored strings. "Performant enough" is very situation-dependent, as you point out... but the fact that the algorithms mentioned before are *NOT* constant time is NOT up to debate. I can think of several applications where this matters greatly.
San Jacinto
2009-08-25 20:13:38