33 ms·

How to implement a hash table in C

302 points by benhoyt 6y ago

bluedino 6y ago
What if this became the new “invert a binary tree on a whiteboard”?
- deleted 6y ago
  [deleted]
- Google234 6y ago
  This is pretty straight forward stuff.
  - 0xbadcafebee 6y ago
    Hash tables are deceptively complicated, like sorting algorithms.
    - cogman10 6y ago
      Like sorting algorithms, they can be as complicated as you want them to be. A merge sort isn't the fastest sort but it's pretty easy for anyone to implement. Something like a timsort is a bit more complex but is what a lot of languages use now-a-days. Hash tables are in the same boat. A basic hashtable is pretty easy to implement. It's only when you start looking at things like ideal item placement and optimal filling that things start to get more complex.
      - kragen 6y ago
        Dunno, I wrote https://news.ycombinator.com/item?id=26595520 https://news.ycombinator.com/item?id=26595520 just now and my super dumb hash table has two bugs in its 21 lines of code: 1. It doesn't update—attempts to change the value associated with an existing key are silently ignored, although they do consume buckets. 2. It loops forever if the table is full and the key it was looking for is negative, because that invokes conversion of a negative signed value to an unsigned value, which I think is UB in C. Maybe it has more bugs I haven't found yet. Additionally the reason it took me 15 minutes to write 21 lines of code was that I changed a bunch of things in midstream, before posting the comment: 1. At first there was no "full" field in the hash table bucket, so there was no way to distinguish full buckets from empty buckets. 2. And then when I added it, I added it as "dead", with the opposite Boolean sense of "full", so I would have needed a separate initialization routine (to set all the dead fields to something nonzero). Instead I swapped the sense. 3. I was trying to detect the case where we'd looped back around to our starting point, indicating that the table was full and the search was unsuccessful, and I realized that the condition I wanted was not b == orig, which would always fail on the first iteration, but (b + 1) % table_size == orig. But doing that on every iteration seemed obscene, so I incremented b (mod table_size) to start out with instead. 4. At some point I think I realized I'd forgotten to set the .full field on newly inserted items. 5. Also I realized I'd forgotten to test the table[b].k == k condition in `get` as well, which would have made every search unsuccessful. So I think it's reasonable to say that even a pretty limited hash-table implementation has plenty of opportunities to write bugs, more than I expected. But maybe I'm just running on low blood sugar this afternoon or something.
        kragen 6y ago
        By contrast this binary search tree code I wrote in OCaml seems to have worked as soon as I got it to compile, although its worst-case performance is pretty bad, and, unlike the much longer hash table code, very likely: let rec getp k = function `Empty -> None | `Node(k1, v1, x, y) -> if k1 = k then Some v1 else getp k (if k < k1 then x else y) and putp k v = function `Empty -> `Node(k, v, `Empty, `Empty) | `Node(k1, v1, x, y) when k1 = k -> `Node(k, v, x, y) | `Node(k1, v1, x, y) -> if k < k1 then `Node(k1, v1, putp k v x, y) else `Node(k1, v1, x, putp k v y) And it's about a third the size of the hash-table code. OTOH I spent the last hour writing it. With four more lines of code it's also a sorting algorithm: and dictofp = function [] -> `Empty | (k, v)::xs -> putp k v (dictofp xs) and itemsp d = let rec iter d tl = match d with `Empty -> tl | `Node(k, v, x, y) -> iter x ((k, v) :: iter y tl) in iter d [] Look: # List.map (fun (x, y) -> x) (itemsp (dictofp (List.map (fun x -> (x, x)) ["this"; "is"; "a"; "list"; "of"; "strings"])));; - : string list = ["a"; "is"; "list"; "of"; "strings"; "this"] Of course the same comments about worst-case performance apply...
- SavantIdiot 6y ago
  This shouldn't be a mystery to someone who's had a datastructures course. It's a fundamental data structure. Yes, optimization always goes down a rabbit-hole, but Knuth's "Algorithms in C" was mandatory in most engineering schools' CS degrees in the early 90's, and it essentially what this website describes, but with more rigor.
  - philzook 6y ago
    Sedgewick's?
  - deleted 6y ago
    [deleted]
  - oldmanhorton 6y ago
    Ok, but school was years ago. I've had years of relevant experience that would make me a good fit for some job since, but I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?
    - jstanley 6y ago
      Knowing how to implement a hash table in C doesn't strike me as something you can "forget". If you know how to write C and you know how a hash table works, what is there to forget?
    - 908B64B197 6y ago
      Honestly it's such a simple concept it shouldn't be hard to remember.
    - kragen 6y ago
      "Is that really the gatekeeper we want?" Yes, I think so? I mean implementing a hash table in C is really easy. What is there to "forget"? If you can't do it, either you don't know what a hash table is, or you don't know how to program in C. enum { table_size = 1024 }; typedef struct item { int k, v, full; } item; static item table[table_size]; void put(item kv) { size_t orig = kv.k % table_size; // dumbest possible hash function size_t b = (orig + 1) % table_size; // use linear probing for collisions while (table[b].full && b != orig) b = (b + 1) % table_size; if (b == orig) abort(); // table full table[b] = kv; table[b].full = 1; } item *get(int k) { size_t orig = k % table_size; size_t b = (orig + 1) % table_size; while (table[b].full && table[b].k != k && b != orig) { b = (b + 1) % table_size; } return (table[b].full && table[b].k == k) ? &table[b] : NULL; } I haven't tested that (just as I wouldn't in a whiteboard interview) so I don't know if it works. I did briefly skim the article we're talking about, but I concluded I didn't have anything to learn from it, so I didn't read it. I found a bunch of bugs in my implementation as I was writing it. And of course it's a pretty dumb hash table: linear probing is very suboptimal, it uses a statically-allocated non-resizable hash table, it's specialized for a certain type of keys, and so on. But are you saying you can't even do that? Probably it would be bad to hire you for a C programming job, then, unless it was an entry-level position for you to learn C in. ⁂ Evidently the above comment took me 15 minutes to write. Oh, and now I see another bug or at least lacuna: if you try to update the value of an existing key, it doesn't fail, but it also doesn't update, instead adding a new entry that will never be read. And then I did write a minimal smoke test and run it, and unsurprisingly, it does work: int main() { put((item) { 4, 7 }); put((item) { 1028, 9 }); put((item) { 3, 25 }); printf("%d %d %d %p %p\n", get(4)->v, get(1028)->v, get(3)->v, get(5), get(3)); return 0; } Writing the test and the above additional commentary, and running the test, took another 8 minutes. Oh, and there's another bug where it will loop infinitely when the hash table is full and the key is negative. (Actually it invokes UB but typically the result will just be an infinite loop.) If it takes you 60 or 100 minutes to write this, or to write something better, maybe you still know C and know what hash tables are. But if you throw up your hands and say "I don't remember, it's been a long time since I was in school"? Either you don't know C, or you don't know what a hash table is, which probably means you've never written anything in C but toy programs. (This is a toy program, of course, but many toy programs in C don't need hash tables.) The compilable and fixed toy program in question is at http://canonical.org/~kragen/sw/dev3/dumbhash.c http://canonical.org/~kragen/sw/dev3/dumbhash.c if you want to probe it for bugs. It occurs to me that you might have been talking about something that isn't a C programming job. For example, we might be talking about a job programming an HTML database front-end in Python using Django. And of course it would be silly to reject someone for a job like that because they didn't know C, unless they claimed to know C on their résumé. And it's totally reasonable for a Python programmer, or a Python/Perl/JS/bash programmer, to not understand hash tables.
- thrower123 6y ago
  Hashtables are probably more directly useful than all the binary tree gymnastics. The K&R C Programming Language book has nearly the same example (although I recall it using linked-lists for hash collisions and not probing). I would be mildly suspicious of anyone claiming to have a recent CS degree who wasn't familiar with the ideas.
- seanwilson 6y ago
  I wouldn't ask someone to whiteboard it but I think "what is a hash table?" is a brilliant interview question. The depth someone can go into tells you a lot and can bring up lots of other topics to discuss. It tells you a lot if a senior developer doesn't know what a hash table is or only knows "it's a class from Java" too.
  - 908B64B197 6y ago
    > I wouldn't ask someone to whiteboard it I did. Works very well as an interview question.
- anaerobicover 6y ago
  Who said anything about interviews? This is just in the context of "something interesting to read with your morning cuppa".
e12e 6y ago
I guess the idea is to contrast dyi bsearch vs dyi hash table - but it's a bit odd to mention bsearch is in the standard lib, then not use it? > Here’s how you’d do it in C (with and without bsearch). Juding by random hit on the net - it would've been quite straightforward to use the stdlib version? https://www.tutorialspoint.com/c_standard_library/c_function_bsearch.htm https://www.tutorialspoint.com/c_standard_library/c_function...
- smcameron 6y ago
  The article actually does both (uses bsearch, and also the home made one) presumably just to demonstrate both.
  - smcameron 6y ago
    (I noticed this because I was wondering why the cmp() function was taking void pointers only to cast them to "item*", and it occurred to me it would make sense if it were passed as a function pointer to a generic library function with no knowledge of "item*"... as it is when bsearch is used.)
  - e12e 6y ago
    Heh, I missed that - just skimming the code on mobile. Maybe there should be a slight edit in the text and/or the custom binary search could be dropped (as it's not the main focus of the article).
- st_goliath 6y ago
  POSIX actually specifies a hash table interface in the standard library as well: https://man7.org/linux/man-pages/man3/hsearch.3.html https://man7.org/linux/man-pages/man3/hsearch.3.html In typical Unix fashion, however, it is designed to use internal, global state, so you can only have one table at a time. There is a GNU extension that provides the same functions with an `_r` suffix that allow you to work with more than one table.
  - Tyrubias 6y ago
    I’ve never really understood why standard Unix functions rely on internal global state. For example, strtok(): https://en.cppreference.com/w/c/string/byte/strtok https://en.cppreference.com/w/c/string/byte/strtok Was there some reason it was optimal to write these functions this way back in the early days of Unix?
frankenst1 6y ago
JavaScript also lacks a proper hash table. I wonder how much faster a native implementation could possibly be over say `Map()` (which keeps insertion order by maintaining linked lists and does not have constant op).
- perlgeek 6y ago
  What's wrong with using objects as hashes?
  - tyingq 6y ago
    There's a table at the bottom of https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... that shows some reasons why.
  - frankenst1 6y ago
    They can be faster than `Map` but: 1) Slower than hash tables 2) `{}` is not empty but has default keys 3) `{}` has multiple read-only keys 2 and 3 are caused by the prototype chain (properties not present on the initial object will be attempted to be resolved via the prototype hierarchy) which can be avoided via `Object.create(null)`
tirrex 6y ago
You skipped hs_remove but depending on implementation, hs_remove strategy may change your hs_set, e.g using tombstones. I’ve recently learnt that you don’t need tombstones at all in linear hashmaps, you just do backshift removals, it may be a simple addition to your map. Check out these repos for the example implementation: (C) https://github.com/tezc/sc/tree/master/map https://github.com/tezc/sc/tree/master/map (C++) https://github.com/rigtorp/HashMap https://github.com/rigtorp/HashMap
- speps 6y ago
  A more detailed explanation of "backward shift deletion": https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ https://codecapsule.com/2013/11/17/robin-hood-hashing-backwa...
- chrchang523 6y ago
  Well, he did say "simple hash table". In my experience, many applications have no need for single-element deletion.
- attractivechaos 6y ago
  I wrote a blog post [1] on this a couple of years ago. This is a quite old technique [2] but was not widely used until recently. I was surprised that I hadn't found this earlier. [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ https://attractivechaos.wordpress.com/2019/12/28/deletion-fr... [2] https://en.wikipedia.org/wiki/Linear_probing#Deletion https://en.wikipedia.org/wiki/Linear_probing#Deletion
  - tirrex 6y ago
    I can’t find right now but I saw one older version of wiki page, it had C code example how to do deletion with this. This is how I discovered it. I knew your blog but apperantly I didn’t visit recently. > I think the new deletion algorithm without tombstones is overall better than traditional algorithms. It should become the preferred way to implement hash tables I agree with you 100%. Tombstone has no advantage over this.
varjag 6y ago
FWIW there's a standard hash table API in POSIX.
- jandrese 6y ago
  Yeah, but it's pretty lame since you have to specify the size of the table up front and can't change it later. They didn't implement the hard stuff!
  - ludocode 6y ago
    There are many reasons why it's lame! Here's a short list: - There is only one global hash table for the whole process! If you want individual hash tables you need to use implementation-specific extensions (hcreate_r().) - There is no way to remove a key from a hash table. No implementation I know of provides an extension to do it. If you want to truly remove a key you must destroy and rebuild the table. - There is no requirement for a means to grow the table. On some platforms it's possible to run out of space. If you want to truly grow you must destroy and rebuild the table. - There is no standard way to free keys or data stored in the table. Destroying the table leaks all contents; you must keep track of keys and data externally and free them yourself. Only OpenBSD frees keys by default, and only NetBSD has extensions to call callbacks to free keys and data. - Keys must be strings. You cannot provide custom types or void pointers as keys. There is no way to specify custom hash or comparison functions. The quality of the hash function is unspecified. - When using ENTER, you may not want to allocate the key unless it is necessary to insert a new entry. Since the given key is inserted directly, it's not necessarily safe to use a stack-allocated buffer for lookups. It's awkward to replace the key with an allocation after insertion and it's unclear whether it's allowed. This doesn't even get into incompatibilities between the various implementations. You will encounter all of the above flaws even if your only target is glibc. No one should ever be encouraged to use POSIX hash tables. They should be deprecated and we should all just pretend they don't exist.
    - jandrese 6y ago
      IMHO this is one area where the C committee could improve the situation by mandating a sane and useful hashtable implementation for the stdlib. Or at the very least just deprecate the old one. I can't remember ever seeing it used in code.
SavantIdiot 6y ago
How are keys removed so that the table doesn't overflow? Are you really going to recommend growing the table by duplicating it? > Beware: this is a teaching tool and not a library, so it’s not very well tested. Dear OP: This really bugs me. If you're not going to put the effort in, and instead crank out some content that might be buggy, then please don't pollute the web with more half-assed "look what I can do" pages.
- kljsandjb 6y ago
  100% agree with U.
- the-dude 6y ago
  This comment bugs me.
- tyingq 6y ago
  I suppose it's a personal preference thing, but I like over simplified implementations when the purpose is educational. I am more bugged by the accusation that the author did this because "look what I can do". I don't see any evidence of that.
- ffdeadbeef 6y ago
  do we really need more hostile, sneering, condescending, toxic pricks like you policing the web?
- kstenerud 6y ago
  A teaching tool is deliberately simplified so as not to overwhelm students with details they don't need to worry about yet. This is absolutely the right way to go about it.
- le-mark 6y ago
  >Are you really going to recommend growing the table by duplicating it? Setting a reasonable initial size then doubling it and copying when (if!) it needs to grow is a pragmatic, reasonable approach that’s quite common!
selimnairb 6y ago
And depending on your use case, you may not need to implement growing the hash table, or deletions, making it even simpler/less daunting to implement in C (since this avoids a lot of the memory management parts of the job).
- benhoyt 6y ago
  Yeah, good point. And then you can allocate the hash table struct and all your buckets in one call to malloc().
ape4 6y ago
This is a fun exercise, but if anyone is thinking about doing this for a project - don't - use a library.
- kevin_thibedeau 6y ago
  Existing libraries make decisions that aren't necessarily suitable for all applications. Most hash table code makes excessive use of malloc/realloc or has power of two growth which is problematic in memory constrained systems. If you want to minimize waste by using high load factors you're going to want Robin Hood hash which is still relatively uncommon in lib code.
  - attractivechaos 6y ago
    Although Robin Hood hashing has good performance under high load, it needs to record the probe length in each bucket. This partly cancels its advantage especially for small keys. In my evaluation, Robin Hood hashing doesn't use less memory in comparison to others. > Most hash table code makes excessive use of malloc/realloc or has power of two growth Libraries based on open addressing only call malloc when there is not enough room. That is not "excessive". Also, if you know the maximum size before hand, many libraries allow you to preallocate buckets such that you never trigger rehashing in this case.
- philwelch 6y ago
  “But Doctor, I am Pagliacci!”
TonyTrapp 6y ago
If you'd have to implement the hash table every time you want to use one, you'd probably realize that there is a better alternative data structure. Quite often you data is not as randomly distributed as you may initially think it is.
- jolux 6y ago
  What?
  - selljamhere 6y ago
    I think the parent comment is highlighting that a hash table is just one implementation of a "Map" abstract data type. Depending on the use case, other implementations (such as using a heap, in the C++ STL) may have better performance.
    - wffurr 6y ago
      Or for the example of word frequencies in the article, a prefix trie.
      - ziml77 6y ago
        I tried a trie with data that I thought would work perfectly with it. There were a good amount of shared prefixes. But it ended up performing worse than a hash map. I don't remember all the details now, but after seeing that I'll just keep reaching for hash maps first (unless I'm sure that there's only going to be a very small number of elements, then I'll just iterate in order over a vector).
    - jolux 6y ago
      True, but as far as I know it's rarely the worst choice you can make, and it's plenty fast for a lot of applications. I don't know that there's a single data structure that's always better, which is what the GP seems to be implying.
    - rurban 6y ago
daneelsan 6y ago
This might not be the best place to ask but: I'm wondering what the best data structure is for these needs: * there are fields and values, similar to a struct * I know at initialization time what fields there are (assume a string) * at run time I want to be able to get this values accessing via the key/field * also I want to update those values * what I don't care about is inserting/deleting fields because that's now allowed, I guess what I want is a struct like data structure, but in an interpreted language Mightve typed to fast...
- tyingq 6y ago
  "I guess what I want is a struct like data structure, but in an interpreted language" Python ffi is an option: https://cffi.readthedocs.io/en/latest/using.html#working-with-pointers-structures-and-arrays https://cffi.readthedocs.io/en/latest/using.html#working-wit... Though I don't know what advantage that route would have over most interpreted language's already existing associative arrays / hashmaps / dicts. There may be some module already built that serves your needs. DiscoDB is a good example..a very fast hashmap that uses mmap(). https://discodb.readthedocs.io/en/latest/ https://discodb.readthedocs.io/en/latest/
- brundolf 6y ago
  Sounds like you want a struct except you want to be able to reflect on the property keys (which you can't do normally in C/C++/Rust)? I got thrown off by "but in an interpreted language" so I'm not sure whether you're requesting this for C or for another language. In JS, at least the V8 engine does some of this for you: if you have a group of objects that always have the same set of properties, V8 will detect this in many cases and optimize them under the hood as a struct or class (it must also store the string keys somewhere since those can be iterated in JS). In C/C++ you'd have to store the keys as strings somehow, and also add some way to index the struct via those keys (since you can't even do that with a normal struct). You may be stuck with a hashmap one way or another.
  - nicoburns 6y ago
    Rust allows you to do this with a macro. The serde macros are pretty close to what you need, but a slight variant could give you a much more ergonomic API.
varajelle 6y ago
> Even while writing this I realized I’d used malloc instead of calloc to allocate the entries array, which meant the keys may not have been initialized to NULL. I think this is still UB to allocate a struct containing pointer with calloc without explicitly set these pointers to 0 (or NULL). The C standard doesn't specify the binary representation of the null pointer value. In practice, that will work in virtually all current platforms, but it's still UB.
- ncmncm 6y ago
  Any particular platform can declare it to be defined, by fiat. "With our compiler, all zeroed raw storage treated as pointers are null." Anywhere that they technically could, you can treat it as if they actually had so declared, and just didn't publicize it enough.
- cygx 6y ago
  Implementation-defined as far as I'm aware. If pointers with all bits zero actually represent null pointers, things will be fine. edit: I haven't found any smoking gun quotation in the C11 standard on short notice, but there is footnote 296 (p.348) on calloc() zeroing all bits: > Note that this need not be the same as the representation of floating-point zero or a null pointer constant. Nothing about this being UB in cases where it does represent a null pointer constant.
  - benhoyt 6y ago
    Wow, thanks, I did not know that. Though that would be a kinda crazy platform or implementation! I'm betting that a lot of people depend on this.
- dpedu 6y ago
  NULL is guaranteed to equal integer 0 by standard, and converting 0 to a pointer is guaranteed to be a NULL pointer. > An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
ModernMech 6y ago
Small nit: in table 2 with the columns labeled "Key, Hash, Hash modulo 16", the thing called "hash" is actually known as a "prehash", while the "hash modulo 16" is the hash. In the context of hash tables, pre-hashing is when you take something like a string or a data structure and turn it into a number. Hashing is the mapping from that number to one of the hash table bins. The distinction is often lost in practice, but if we're talking about hash table design and implementation it's important to make this clear at least once.
- joosters 6y ago
  Is that always true? It depends whether or not you think of the hash as a property of the hashtable, or a property of the key itself. e.g. you may have string objects that store their hash values internally - a useful optimisation if you are dealing with lots of long read-only strings, given that the hash function will have a cost of at least O(n) for the string length. Inserting a string into a hashtable wouldn't change its hash (what if the string is inserted into two tables of different sizes?)
  - ModernMech 6y ago
    Right, it does depend on this perspective, which is why I say the distinction is often lost in practice. But from the perspective of hash table designers (at least historically), the hash can in fact change and is dependent on the size of the table. The distinction is important because the two operations are separable. I guess people didn't want to call one thing a "hash" and the other "hash mod k" because there are ways to do this other than mod. They could have called one "hash" and the other "post hash" but it is what it is. All I'm trying to say is if you want to know more about hash tables, and you bother to venture into the literature or some textbooks, you're going to run into this distinction sooner rather than later, so I wanted to point that out here.
sobriquet9 6y ago
Will this expression correctly handle overflow? size_t mid = (low + high) / 2;
- chrchang523 6y ago
  Not an issue since the following is at the top of the function: if (size + size < size) { return NULL; // size too big; avoid overflow }
- kt66 6y ago
  what about low>>1 + high>>1 + (1 & low & high)
  - nwallin 6y ago
    Careful about operator precedence. low>>1 + high>>1 + (1&low&high) is the same as low>>(1 + high>>(1 + (1&low&high)))
- mywittyname 6y ago
  Interesting question. Since this is integer division, I think you can do: size_t low_s = low >> 1; size_t high_s = high >> 1; size_t mid = (low_s + high_s) ...With no overflow worries. (expanded for clarity) That would effectively be distributing the division. So it's equivalent to low / 2 + high / 2.
  - saagarjha 6y ago
    This gives a different result when both low and high are odd.
    - deleted 6y ago
      [deleted]
tengbretson 6y ago
Unless you need the specific memory characteristics of a hash table, a trie data structure is a pretty good solution to a lot of the same problems and in my opinion is conceptually easier to understand.
- deleted 6y ago
  [deleted]
- taeric 6y ago
  I have never seen a true described as easier than a hash table. Curious what makes you say they are easier?
  - tengbretson 6y ago
    I find their performance characteristics easier to naively understand without resorting to profiling with production data.
    - taeric 6y ago
      I should have worded my question more as "do you have a recommendation to describe tries?" In particular, construction is tough.
      - tengbretson 6y ago
        The C# implementation here is pretty approachable for just about any kind of programming background. https://www.geeksforgeeks.org/trie-insert-and-search/ https://www.geeksforgeeks.org/trie-insert-and-search/
vram22 6y ago
IIRC, a very simple implementation of a hash table was shown in the classic Kernighan & Ritchie C book, "The C Programming Language" (which was one of the first good programming books that I bought and read, early in my programming career). It was in either the 1st (pre-ANSI C) or the 2nd (ANSI C) edition. Just a handful of lines of C code, and easy enough for even beginners to understand. Of course, it was not a production-quality hash table implementation, nor was it meant to be. I still remember my excitement at understanding the logic and its usefulness at the time, even though I did not know about the importance of data structures and algorithms then. Edit: Even though it was simple, IIRC, it handled at least collisions.
- benhoyt 6y ago
  Nice. Yeah, looks like it's in section "6.6 Table Lookup", and it implements a simple, fixed-size hash table (array size 101) of char* to char*, and it handles collisions via linked lists.
  - vram22 6y ago
    Cool, thanks for looking it up :)
    - vram22 6y ago
      >looking it up Pun not intended but noticed, ha ha.
thamer 6y ago
> When the hash table gets too full, we need to allocate a larger array and move the items over. This is absolutely required when the number of items in the hash table has reached the size of the array, but usually you want to do it when the table is half or three-quarters full. Yes, but how you resize is important too: if you have a threshold size (like 3/4 full) at which you block and re-distribute all elements into a new array, you will incur a significant pause when this happens, e.g. https://log.kv.io/post/2009/05/15/leaky-hashtables https://log.kv.io/post/2009/05/15/leaky-hashtables Instead, when you reach the threshold amount you can create the new array and then gradually migrate the keys in small batches either with each operation or with a background thread. So on `get` if we're in the process of resizing: first check the new table, then the old one, and before returning migrate N keys from the old table to the new one. Free the old array once all the keys are migrated. I wrote a small hash table implementation with gradual re-hashing a while back, search for DICT_MAX_LOAD and dict_rehash here: https://github.com/nicolasff/ht/blob/master/dict.c#L193 https://github.com/nicolasff/ht/blob/master/dict.c#L193
- OskarS 6y ago
  It’s usually not the right call to use a hash table like you’re describing. You’re not saving any work (all keys have to be migrated sooner or later) and by doing it like this you incur a non-trivial amount of overhead on most operations. Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap. In practice, this is almost always a fine assumption, and it is how the vast majority of hash tables in all programming languages work. The kinds of hash tables you are talking about have their uses in places where you have soft real-time constraints, but that is honestly a pretty niche use case.
  - sgerenser 6y ago
    Agreed this seems like major overkill, but then again so does writing your own hash table from scratch in C. :shrug:
  - jeffffff 6y ago
winrid 6y ago
Isn't a faster way to, instead of using a backing array, to use a pool of memory that you just point into with pointers addressed with the hash? Nasty stuff that you can do in a language like C :)
- ufo 6y ago
  As far as the CPU is concerned, there isn't a big difference if you access a block of memory via pointers or via an array. Converting the hash result to a memory address is not the bottleneck. The main bottlenecks are the hash function itself and the logic for dealing with collusions
  - winrid 6y ago
    I definitely agree that is where the main bottlenecks are!
yudlejoza 6y ago
99% of the effort is 'what hash function?'
nojvek 6y ago
When you need to scan billions of rows and get sorted unique strings, theory like this is really useful. You can’t just use a library and call it a day. Sometimes you gotta build your own hash table and profile it out. Then tweak it, and profile it until you get every last bit of juice from CPU and RAM. Articles like this are really useful for someone who wants to under the hood.

302 points by benhoyt 6y ago

bluedino 6y ago

What if this became the new “invert a binary tree on a whiteboard”?

deleted 6y ago
[deleted]
Google234 6y ago
This is pretty straight forward stuff.
- 0xbadcafebee 6y ago
  Hash tables are deceptively complicated, like sorting algorithms.
  - cogman10 6y ago
    Like sorting algorithms, they can be as complicated as you want them to be. A merge sort isn't the fastest sort but it's pretty easy for anyone to implement. Something like a timsort is a bit more complex but is what a lot of languages use now-a-days. Hash tables are in the same boat. A basic hashtable is pretty easy to implement. It's only when you start looking at things like ideal item placement and optimal filling that things start to get more complex.
    - kragen 6y ago
      Dunno, I wrote https://news.ycombinator.com/item?id=26595520 https://news.ycombinator.com/item?id=26595520 just now and my super dumb hash table has two bugs in its 21 lines of code: 1. It doesn't update—attempts to change the value associated with an existing key are silently ignored, although they do consume buckets. 2. It loops forever if the table is full and the key it was looking for is negative, because that invokes conversion of a negative signed value to an unsigned value, which I think is UB in C. Maybe it has more bugs I haven't found yet. Additionally the reason it took me 15 minutes to write 21 lines of code was that I changed a bunch of things in midstream, before posting the comment: 1. At first there was no "full" field in the hash table bucket, so there was no way to distinguish full buckets from empty buckets. 2. And then when I added it, I added it as "dead", with the opposite Boolean sense of "full", so I would have needed a separate initialization routine (to set all the dead fields to something nonzero). Instead I swapped the sense. 3. I was trying to detect the case where we'd looped back around to our starting point, indicating that the table was full and the search was unsuccessful, and I realized that the condition I wanted was not b == orig, which would always fail on the first iteration, but (b + 1) % table_size == orig. But doing that on every iteration seemed obscene, so I incremented b (mod table_size) to start out with instead. 4. At some point I think I realized I'd forgotten to set the .full field on newly inserted items. 5. Also I realized I'd forgotten to test the table[b].k == k condition in `get` as well, which would have made every search unsuccessful. So I think it's reasonable to say that even a pretty limited hash-table implementation has plenty of opportunities to write bugs, more than I expected. But maybe I'm just running on low blood sugar this afternoon or something.
      - kragen 6y ago
        By contrast this binary search tree code I wrote in OCaml seems to have worked as soon as I got it to compile, although its worst-case performance is pretty bad, and, unlike the much longer hash table code, very likely: let rec getp k = function `Empty -> None | `Node(k1, v1, x, y) -> if k1 = k then Some v1 else getp k (if k < k1 then x else y) and putp k v = function `Empty -> `Node(k, v, `Empty, `Empty) | `Node(k1, v1, x, y) when k1 = k -> `Node(k, v, x, y) | `Node(k1, v1, x, y) -> if k < k1 then `Node(k1, v1, putp k v x, y) else `Node(k1, v1, x, putp k v y) And it's about a third the size of the hash-table code. OTOH I spent the last hour writing it. With four more lines of code it's also a sorting algorithm: and dictofp = function [] -> `Empty | (k, v)::xs -> putp k v (dictofp xs) and itemsp d = let rec iter d tl = match d with `Empty -> tl | `Node(k, v, x, y) -> iter x ((k, v) :: iter y tl) in iter d [] Look: # List.map (fun (x, y) -> x) (itemsp (dictofp (List.map (fun x -> (x, x)) ["this"; "is"; "a"; "list"; "of"; "strings"])));; - : string list = ["a"; "is"; "list"; "of"; "strings"; "this"] Of course the same comments about worst-case performance apply...
SavantIdiot 6y ago
This shouldn't be a mystery to someone who's had a datastructures course. It's a fundamental data structure. Yes, optimization always goes down a rabbit-hole, but Knuth's "Algorithms in C" was mandatory in most engineering schools' CS degrees in the early 90's, and it essentially what this website describes, but with more rigor.
- philzook 6y ago
  Sedgewick's?
- deleted 6y ago
  [deleted]
- oldmanhorton 6y ago
  Ok, but school was years ago. I've had years of relevant experience that would make me a good fit for some job since, but I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?
  - jstanley 6y ago
    Knowing how to implement a hash table in C doesn't strike me as something you can "forget". If you know how to write C and you know how a hash table works, what is there to forget?
  - 908B64B197 6y ago
    Honestly it's such a simple concept it shouldn't be hard to remember.
  - kragen 6y ago
    "Is that really the gatekeeper we want?" Yes, I think so? I mean implementing a hash table in C is really easy. What is there to "forget"? If you can't do it, either you don't know what a hash table is, or you don't know how to program in C. enum { table_size = 1024 }; typedef struct item { int k, v, full; } item; static item table[table_size]; void put(item kv) { size_t orig = kv.k % table_size; // dumbest possible hash function size_t b = (orig + 1) % table_size; // use linear probing for collisions while (table[b].full && b != orig) b = (b + 1) % table_size; if (b == orig) abort(); // table full table[b] = kv; table[b].full = 1; } item *get(int k) { size_t orig = k % table_size; size_t b = (orig + 1) % table_size; while (table[b].full && table[b].k != k && b != orig) { b = (b + 1) % table_size; } return (table[b].full && table[b].k == k) ? &table[b] : NULL; } I haven't tested that (just as I wouldn't in a whiteboard interview) so I don't know if it works. I did briefly skim the article we're talking about, but I concluded I didn't have anything to learn from it, so I didn't read it. I found a bunch of bugs in my implementation as I was writing it. And of course it's a pretty dumb hash table: linear probing is very suboptimal, it uses a statically-allocated non-resizable hash table, it's specialized for a certain type of keys, and so on. But are you saying you can't even do that? Probably it would be bad to hire you for a C programming job, then, unless it was an entry-level position for you to learn C in. ⁂ Evidently the above comment took me 15 minutes to write. Oh, and now I see another bug or at least lacuna: if you try to update the value of an existing key, it doesn't fail, but it also doesn't update, instead adding a new entry that will never be read. And then I did write a minimal smoke test and run it, and unsurprisingly, it does work: int main() { put((item) { 4, 7 }); put((item) { 1028, 9 }); put((item) { 3, 25 }); printf("%d %d %d %p %p\n", get(4)->v, get(1028)->v, get(3)->v, get(5), get(3)); return 0; } Writing the test and the above additional commentary, and running the test, took another 8 minutes. Oh, and there's another bug where it will loop infinitely when the hash table is full and the key is negative. (Actually it invokes UB but typically the result will just be an infinite loop.) If it takes you 60 or 100 minutes to write this, or to write something better, maybe you still know C and know what hash tables are. But if you throw up your hands and say "I don't remember, it's been a long time since I was in school"? Either you don't know C, or you don't know what a hash table is, which probably means you've never written anything in C but toy programs. (This is a toy program, of course, but many toy programs in C don't need hash tables.) The compilable and fixed toy program in question is at http://canonical.org/~kragen/sw/dev3/dumbhash.c http://canonical.org/~kragen/sw/dev3/dumbhash.c if you want to probe it for bugs. It occurs to me that you might have been talking about something that isn't a C programming job. For example, we might be talking about a job programming an HTML database front-end in Python using Django. And of course it would be silly to reject someone for a job like that because they didn't know C, unless they claimed to know C on their résumé. And it's totally reasonable for a Python programmer, or a Python/Perl/JS/bash programmer, to not understand hash tables.
thrower123 6y ago
Hashtables are probably more directly useful than all the binary tree gymnastics. The K&R C Programming Language book has nearly the same example (although I recall it using linked-lists for hash collisions and not probing). I would be mildly suspicious of anyone claiming to have a recent CS degree who wasn't familiar with the ideas.
seanwilson 6y ago
I wouldn't ask someone to whiteboard it but I think "what is a hash table?" is a brilliant interview question. The depth someone can go into tells you a lot and can bring up lots of other topics to discuss. It tells you a lot if a senior developer doesn't know what a hash table is or only knows "it's a class from Java" too.
- 908B64B197 6y ago
  > I wouldn't ask someone to whiteboard it I did. Works very well as an interview question.
anaerobicover 6y ago
Who said anything about interviews? This is just in the context of "something interesting to read with your morning cuppa".

e12e 6y ago

I guess the idea is to contrast dyi bsearch vs dyi hash table - but it's a bit odd to mention bsearch is in the standard lib, then not use it? > Here’s how you’d do it in C (with and without bsearch). Juding by random hit on the net - it would've been quite straightforward to use the stdlib version? https://www.tutorialspoint.com/c_standard_library/c_function_bsearch.htm https://www.tutorialspoint.com/c_standard_library/c_function...

smcameron 6y ago
The article actually does both (uses bsearch, and also the home made one) presumably just to demonstrate both.
- smcameron 6y ago
  (I noticed this because I was wondering why the cmp() function was taking void pointers only to cast them to "item*", and it occurred to me it would make sense if it were passed as a function pointer to a generic library function with no knowledge of "item*"... as it is when bsearch is used.)
- e12e 6y ago
  Heh, I missed that - just skimming the code on mobile. Maybe there should be a slight edit in the text and/or the custom binary search could be dropped (as it's not the main focus of the article).
st_goliath 6y ago
POSIX actually specifies a hash table interface in the standard library as well: https://man7.org/linux/man-pages/man3/hsearch.3.html https://man7.org/linux/man-pages/man3/hsearch.3.html In typical Unix fashion, however, it is designed to use internal, global state, so you can only have one table at a time. There is a GNU extension that provides the same functions with an `_r` suffix that allow you to work with more than one table.
- Tyrubias 6y ago
  I’ve never really understood why standard Unix functions rely on internal global state. For example, strtok(): https://en.cppreference.com/w/c/string/byte/strtok https://en.cppreference.com/w/c/string/byte/strtok Was there some reason it was optimal to write these functions this way back in the early days of Unix?

frankenst1 6y ago

JavaScript also lacks a proper hash table. I wonder how much faster a native implementation could possibly be over say `Map()` (which keeps insertion order by maintaining linked lists and does not have constant op).

perlgeek 6y ago
What's wrong with using objects as hashes?
- tyingq 6y ago
  There's a table at the bottom of https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... that shows some reasons why.
- frankenst1 6y ago
  They can be faster than `Map` but: 1) Slower than hash tables 2) `{}` is not empty but has default keys 3) `{}` has multiple read-only keys 2 and 3 are caused by the prototype chain (properties not present on the initial object will be attempted to be resolved via the prototype hierarchy) which can be avoided via `Object.create(null)`

tirrex 6y ago

You skipped hs_remove but depending on implementation, hs_remove strategy may change your hs_set, e.g using tombstones. I’ve recently learnt that you don’t need tombstones at all in linear hashmaps, you just do backshift removals, it may be a simple addition to your map. Check out these repos for the example implementation: (C) https://github.com/tezc/sc/tree/master/map https://github.com/tezc/sc/tree/master/map (C++) https://github.com/rigtorp/HashMap https://github.com/rigtorp/HashMap

speps 6y ago
A more detailed explanation of "backward shift deletion": https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ https://codecapsule.com/2013/11/17/robin-hood-hashing-backwa...
chrchang523 6y ago
Well, he did say "simple hash table". In my experience, many applications have no need for single-element deletion.
attractivechaos 6y ago
I wrote a blog post [1] on this a couple of years ago. This is a quite old technique [2] but was not widely used until recently. I was surprised that I hadn't found this earlier. [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ https://attractivechaos.wordpress.com/2019/12/28/deletion-fr... [2] https://en.wikipedia.org/wiki/Linear_probing#Deletion https://en.wikipedia.org/wiki/Linear_probing#Deletion
- tirrex 6y ago
  I can’t find right now but I saw one older version of wiki page, it had C code example how to do deletion with this. This is how I discovered it. I knew your blog but apperantly I didn’t visit recently. > I think the new deletion algorithm without tombstones is overall better than traditional algorithms. It should become the preferred way to implement hash tables I agree with you 100%. Tombstone has no advantage over this.

varjag 6y ago

FWIW there's a standard hash table API in POSIX.

jandrese 6y ago
Yeah, but it's pretty lame since you have to specify the size of the table up front and can't change it later. They didn't implement the hard stuff!
- ludocode 6y ago
  There are many reasons why it's lame! Here's a short list: - There is only one global hash table for the whole process! If you want individual hash tables you need to use implementation-specific extensions (hcreate_r().) - There is no way to remove a key from a hash table. No implementation I know of provides an extension to do it. If you want to truly remove a key you must destroy and rebuild the table. - There is no requirement for a means to grow the table. On some platforms it's possible to run out of space. If you want to truly grow you must destroy and rebuild the table. - There is no standard way to free keys or data stored in the table. Destroying the table leaks all contents; you must keep track of keys and data externally and free them yourself. Only OpenBSD frees keys by default, and only NetBSD has extensions to call callbacks to free keys and data. - Keys must be strings. You cannot provide custom types or void pointers as keys. There is no way to specify custom hash or comparison functions. The quality of the hash function is unspecified. - When using ENTER, you may not want to allocate the key unless it is necessary to insert a new entry. Since the given key is inserted directly, it's not necessarily safe to use a stack-allocated buffer for lookups. It's awkward to replace the key with an allocation after insertion and it's unclear whether it's allowed. This doesn't even get into incompatibilities between the various implementations. You will encounter all of the above flaws even if your only target is glibc. No one should ever be encouraged to use POSIX hash tables. They should be deprecated and we should all just pretend they don't exist.
  - jandrese 6y ago
    IMHO this is one area where the C committee could improve the situation by mandating a sane and useful hashtable implementation for the stdlib. Or at the very least just deprecate the old one. I can't remember ever seeing it used in code.

SavantIdiot 6y ago

How are keys removed so that the table doesn't overflow? Are you really going to recommend growing the table by duplicating it? > Beware: this is a teaching tool and not a library, so it’s not very well tested. Dear OP: This really bugs me. If you're not going to put the effort in, and instead crank out some content that might be buggy, then please don't pollute the web with more half-assed "look what I can do" pages.

kljsandjb 6y ago
100% agree with U.
the-dude 6y ago
This comment bugs me.
tyingq 6y ago
I suppose it's a personal preference thing, but I like over simplified implementations when the purpose is educational. I am more bugged by the accusation that the author did this because "look what I can do". I don't see any evidence of that.
ffdeadbeef 6y ago
do we really need more hostile, sneering, condescending, toxic pricks like you policing the web?
kstenerud 6y ago
A teaching tool is deliberately simplified so as not to overwhelm students with details they don't need to worry about yet. This is absolutely the right way to go about it.
le-mark 6y ago
>Are you really going to recommend growing the table by duplicating it? Setting a reasonable initial size then doubling it and copying when (if!) it needs to grow is a pragmatic, reasonable approach that’s quite common!

selimnairb 6y ago

And depending on your use case, you may not need to implement growing the hash table, or deletions, making it even simpler/less daunting to implement in C (since this avoids a lot of the memory management parts of the job).

benhoyt 6y ago
Yeah, good point. And then you can allocate the hash table struct and all your buckets in one call to malloc().

ape4 6y ago

This is a fun exercise, but if anyone is thinking about doing this for a project - don't - use a library.

kevin_thibedeau 6y ago
Existing libraries make decisions that aren't necessarily suitable for all applications. Most hash table code makes excessive use of malloc/realloc or has power of two growth which is problematic in memory constrained systems. If you want to minimize waste by using high load factors you're going to want Robin Hood hash which is still relatively uncommon in lib code.
- attractivechaos 6y ago
  Although Robin Hood hashing has good performance under high load, it needs to record the probe length in each bucket. This partly cancels its advantage especially for small keys. In my evaluation, Robin Hood hashing doesn't use less memory in comparison to others. > Most hash table code makes excessive use of malloc/realloc or has power of two growth Libraries based on open addressing only call malloc when there is not enough room. That is not "excessive". Also, if you know the maximum size before hand, many libraries allow you to preallocate buckets such that you never trigger rehashing in this case.
philwelch 6y ago
“But Doctor, I am Pagliacci!”

TonyTrapp 6y ago

If you'd have to implement the hash table every time you want to use one, you'd probably realize that there is a better alternative data structure. Quite often you data is not as randomly distributed as you may initially think it is.

jolux 6y ago
What?
- selljamhere 6y ago
  I think the parent comment is highlighting that a hash table is just one implementation of a "Map" abstract data type. Depending on the use case, other implementations (such as using a heap, in the C++ STL) may have better performance.
  - wffurr 6y ago
    Or for the example of word frequencies in the article, a prefix trie.
    - ziml77 6y ago
      I tried a trie with data that I thought would work perfectly with it. There were a good amount of shared prefixes. But it ended up performing worse than a hash map. I don't remember all the details now, but after seeing that I'll just keep reaching for hash maps first (unless I'm sure that there's only going to be a very small number of elements, then I'll just iterate in order over a vector).
  - jolux 6y ago
    True, but as far as I know it's rarely the worst choice you can make, and it's plenty fast for a lot of applications. I don't know that there's a single data structure that's always better, which is what the GP seems to be implying.
  - rurban 6y ago

daneelsan 6y ago

This might not be the best place to ask but: I'm wondering what the best data structure is for these needs: * there are fields and values, similar to a struct * I know at initialization time what fields there are (assume a string) * at run time I want to be able to get this values accessing via the key/field * also I want to update those values * what I don't care about is inserting/deleting fields because that's now allowed, I guess what I want is a struct like data structure, but in an interpreted language Mightve typed to fast...

tyingq 6y ago
"I guess what I want is a struct like data structure, but in an interpreted language" Python ffi is an option: https://cffi.readthedocs.io/en/latest/using.html#working-with-pointers-structures-and-arrays https://cffi.readthedocs.io/en/latest/using.html#working-wit... Though I don't know what advantage that route would have over most interpreted language's already existing associative arrays / hashmaps / dicts. There may be some module already built that serves your needs. DiscoDB is a good example..a very fast hashmap that uses mmap(). https://discodb.readthedocs.io/en/latest/ https://discodb.readthedocs.io/en/latest/
brundolf 6y ago
Sounds like you want a struct except you want to be able to reflect on the property keys (which you can't do normally in C/C++/Rust)? I got thrown off by "but in an interpreted language" so I'm not sure whether you're requesting this for C or for another language. In JS, at least the V8 engine does some of this for you: if you have a group of objects that always have the same set of properties, V8 will detect this in many cases and optimize them under the hood as a struct or class (it must also store the string keys somewhere since those can be iterated in JS). In C/C++ you'd have to store the keys as strings somehow, and also add some way to index the struct via those keys (since you can't even do that with a normal struct). You may be stuck with a hashmap one way or another.
- nicoburns 6y ago
  Rust allows you to do this with a macro. The serde macros are pretty close to what you need, but a slight variant could give you a much more ergonomic API.

varajelle 6y ago

> Even while writing this I realized I’d used malloc instead of calloc to allocate the entries array, which meant the keys may not have been initialized to NULL. I think this is still UB to allocate a struct containing pointer with calloc without explicitly set these pointers to 0 (or NULL). The C standard doesn't specify the binary representation of the null pointer value. In practice, that will work in virtually all current platforms, but it's still UB.

ncmncm 6y ago
Any particular platform can declare it to be defined, by fiat. "With our compiler, all zeroed raw storage treated as pointers are null." Anywhere that they technically could, you can treat it as if they actually had so declared, and just didn't publicize it enough.
cygx 6y ago
Implementation-defined as far as I'm aware. If pointers with all bits zero actually represent null pointers, things will be fine. edit: I haven't found any smoking gun quotation in the C11 standard on short notice, but there is footnote 296 (p.348) on calloc() zeroing all bits: > Note that this need not be the same as the representation of floating-point zero or a null pointer constant. Nothing about this being UB in cases where it does represent a null pointer constant.
- benhoyt 6y ago
  Wow, thanks, I did not know that. Though that would be a kinda crazy platform or implementation! I'm betting that a lot of people depend on this.
dpedu 6y ago
NULL is guaranteed to equal integer 0 by standard, and converting 0 to a pointer is guaranteed to be a NULL pointer. > An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

ModernMech 6y ago

Small nit: in table 2 with the columns labeled "Key, Hash, Hash modulo 16", the thing called "hash" is actually known as a "prehash", while the "hash modulo 16" is the hash. In the context of hash tables, pre-hashing is when you take something like a string or a data structure and turn it into a number. Hashing is the mapping from that number to one of the hash table bins. The distinction is often lost in practice, but if we're talking about hash table design and implementation it's important to make this clear at least once.

joosters 6y ago
Is that always true? It depends whether or not you think of the hash as a property of the hashtable, or a property of the key itself. e.g. you may have string objects that store their hash values internally - a useful optimisation if you are dealing with lots of long read-only strings, given that the hash function will have a cost of at least O(n) for the string length. Inserting a string into a hashtable wouldn't change its hash (what if the string is inserted into two tables of different sizes?)
- ModernMech 6y ago
  Right, it does depend on this perspective, which is why I say the distinction is often lost in practice. But from the perspective of hash table designers (at least historically), the hash can in fact change and is dependent on the size of the table. The distinction is important because the two operations are separable. I guess people didn't want to call one thing a "hash" and the other "hash mod k" because there are ways to do this other than mod. They could have called one "hash" and the other "post hash" but it is what it is. All I'm trying to say is if you want to know more about hash tables, and you bother to venture into the literature or some textbooks, you're going to run into this distinction sooner rather than later, so I wanted to point that out here.

sobriquet9 6y ago

Will this expression correctly handle overflow? size_t mid = (low + high) / 2;

chrchang523 6y ago
Not an issue since the following is at the top of the function: if (size + size < size) { return NULL; // size too big; avoid overflow }
kt66 6y ago
what about low>>1 + high>>1 + (1 & low & high)
- nwallin 6y ago
  Careful about operator precedence. low>>1 + high>>1 + (1&low&high) is the same as low>>(1 + high>>(1 + (1&low&high)))
mywittyname 6y ago
Interesting question. Since this is integer division, I think you can do: size_t low_s = low >> 1; size_t high_s = high >> 1; size_t mid = (low_s + high_s) ...With no overflow worries. (expanded for clarity) That would effectively be distributing the division. So it's equivalent to low / 2 + high / 2.
- saagarjha 6y ago
  This gives a different result when both low and high are odd.
  - deleted 6y ago
    [deleted]

tengbretson 6y ago

Unless you need the specific memory characteristics of a hash table, a trie data structure is a pretty good solution to a lot of the same problems and in my opinion is conceptually easier to understand.

deleted 6y ago
[deleted]
taeric 6y ago
I have never seen a true described as easier than a hash table. Curious what makes you say they are easier?
- tengbretson 6y ago
  I find their performance characteristics easier to naively understand without resorting to profiling with production data.
  - taeric 6y ago
    I should have worded my question more as "do you have a recommendation to describe tries?" In particular, construction is tough.
    - tengbretson 6y ago
      The C# implementation here is pretty approachable for just about any kind of programming background. https://www.geeksforgeeks.org/trie-insert-and-search/ https://www.geeksforgeeks.org/trie-insert-and-search/

vram22 6y ago

IIRC, a very simple implementation of a hash table was shown in the classic Kernighan & Ritchie C book, "The C Programming Language" (which was one of the first good programming books that I bought and read, early in my programming career). It was in either the 1st (pre-ANSI C) or the 2nd (ANSI C) edition. Just a handful of lines of C code, and easy enough for even beginners to understand. Of course, it was not a production-quality hash table implementation, nor was it meant to be. I still remember my excitement at understanding the logic and its usefulness at the time, even though I did not know about the importance of data structures and algorithms then. Edit: Even though it was simple, IIRC, it handled at least collisions.

benhoyt 6y ago
Nice. Yeah, looks like it's in section "6.6 Table Lookup", and it implements a simple, fixed-size hash table (array size 101) of char* to char*, and it handles collisions via linked lists.
- vram22 6y ago
  Cool, thanks for looking it up :)
  - vram22 6y ago
    >looking it up Pun not intended but noticed, ha ha.

thamer 6y ago

> When the hash table gets too full, we need to allocate a larger array and move the items over. This is absolutely required when the number of items in the hash table has reached the size of the array, but usually you want to do it when the table is half or three-quarters full. Yes, but how you resize is important too: if you have a threshold size (like 3/4 full) at which you block and re-distribute all elements into a new array, you will incur a significant pause when this happens, e.g. https://log.kv.io/post/2009/05/15/leaky-hashtables https://log.kv.io/post/2009/05/15/leaky-hashtables Instead, when you reach the threshold amount you can create the new array and then gradually migrate the keys in small batches either with each operation or with a background thread. So on `get` if we're in the process of resizing: first check the new table, then the old one, and before returning migrate N keys from the old table to the new one. Free the old array once all the keys are migrated. I wrote a small hash table implementation with gradual re-hashing a while back, search for DICT_MAX_LOAD and dict_rehash here: https://github.com/nicolasff/ht/blob/master/dict.c#L193 https://github.com/nicolasff/ht/blob/master/dict.c#L193

OskarS 6y ago
It’s usually not the right call to use a hash table like you’re describing. You’re not saving any work (all keys have to be migrated sooner or later) and by doing it like this you incur a non-trivial amount of overhead on most operations. Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap. In practice, this is almost always a fine assumption, and it is how the vast majority of hash tables in all programming languages work. The kinds of hash tables you are talking about have their uses in places where you have soft real-time constraints, but that is honestly a pretty niche use case.
- sgerenser 6y ago
  Agreed this seems like major overkill, but then again so does writing your own hash table from scratch in C. :shrug:
- jeffffff 6y ago

winrid 6y ago

Isn't a faster way to, instead of using a backing array, to use a pool of memory that you just point into with pointers addressed with the hash? Nasty stuff that you can do in a language like C :)

ufo 6y ago
As far as the CPU is concerned, there isn't a big difference if you access a block of memory via pointers or via an array. Converting the hash result to a memory address is not the bottleneck. The main bottlenecks are the hash function itself and the logic for dealing with collusions
- winrid 6y ago
  I definitely agree that is where the main bottlenecks are!

yudlejoza 6y ago

99% of the effort is 'what hash function?'

nojvek 6y ago

When you need to scan billions of rows and get sorted unique strings, theory like this is really useful. You can’t just use a library and call it a day. Sometimes you gotta build your own hash table and profile it out. Then tweak it, and profile it until you get every last bit of juice from CPU and RAM. Articles like this are really useful for someone who wants to under the hood.