Myths about Hash Tables

http://hughewilliams.com/2012/10/01/five-myths-about-hash-tables/

by zengr • 14 years ago

101 100 14 years ago

recursive• 14 years ago

The first two myths aren't really myths.

In "The worst case is terrible", the author goes on to explain that the worst case is unlikely. That may be true, but it's still O(n).

In "Hash tables become full, and bad things happen", if I'm reading it correctly, the author shows how you can make each hash table bucket a linked list so that each bucket never becomes full. But what happens when you have 1000 items in each bucket? If you keep adding elements and you want to keep reads fast, sooner or later you're going to have to add more buckets, at which time you need to re-hash every element in the table.

I'm a fan of hashtables, but there's some rather suspicious handwaving in this article.

alexholehouse• 14 years ago

I think at the point of having 1000 items in each bucket, a hashtable was never a good idea. I read it more as like, "Don't worry if you have collisions cos it'll be OK" as opposed to "Collisions have no impact on performance".

jff2• 14 years ago

When you have 1000 items per bucket, you realize that you needed a bigger table. Depending on the implementation you're using, it may be able to expand the table without going "ok, hold everything, I have to rehash all this existing content". For instance, you can create a second hash table, start putting new additions in there. When you get an access, first check the new table, then the original one. If it's in the original table, return the value and move the k/v pair to the new table. Lots of papers have surely been written on this topic.

robrenaud• 14 years ago

I am not going to buy a lottery ticket because the super unlikely best case is really good. For the same reason, I am not going to avoid a hash table because the super unlikely worst case is kind of bad.

You never have 1000 items in each bucket. You resize well before then.

jff2• 14 years ago

If things are being hashed evenly, and you have a 100 bucket table, putting 200, 300, etc. elements into the table isn't a terribly big deal, because it's just not slow to traverse a few nodes of a linked list. Of course, there's no reason not to make the table much bigger--it's just an array of pointers, make it 1,000,000 entries and you're still within a few megabytes.

Now, if someone wants to be a jerk, and figures out how to easy collide on your hash function, then you could have problems. He could stuff 1 million elements into the same hash table element, which will suck for linked-list traversal. So get a good hash algorithm :)

marshray14• 14 years ago

It's not just a "good" hash algorithm, it has to be one that cannot be made to behave in a way predictable to an attacker.

Picking a new secure random seed value at startup time and prepending it to every hashed value is generally what you need to do.

cube13• 14 years ago

The fundamental problem, especially wrt to 1 and 2, is that you're starting to deal more with the design and implementation of the hash table than anything else. There are two things that need to be considered for a good hash table implementation:

1. Collisions should be expected, and handled correctly.

2. The hashing algorithm should minimize collisions as much as possible.

Yes, the worst case running time is linear. However, assuming a properly defined hashing function, it's practically a linear running time over the expected number of collisions per bucket, which should be a tiny fraction of the total expected data size.

The problem that the second gives us is that proper hash algorithms are tailored to the specific problem at hand. MD5 is overkill when your entire pool of data is 1000 names. And knowing your data set makes it so you can avoid having a relatively large percentage of your data in one bucket.

sounds• 14 years ago

Minor correction:

The worst case runtime is not O(n), it is defined by how you store your nodes in a hash bucket. If you choose to use a linked list, then searching a linked list is O(n). Also, obviously, there is no free lunch, so using a hash table in each bucket does not magically produce O(1) lookups.

Pick a data structure that has O(log n) runtime for lookups and use it when the hash table breaks down - that is, use it when searching in a bucket.

On the other hand, if your hash table has enough nodes in a bucket that you even notice the difference between O(very small n) and O(log very small n), you really should migrate to a larger hash table.

GlennS• 14 years ago

You could make each hash bucket a tree instead?

kroidkrensen4• 14 years ago

I'm the author of the article. I've tried that -- the downside is that the data structures (nodes in particular) take more space, and have more costs to manage / reorganize. Using a linked list with move-to-front-on-access works better in all experiments I've tried.

marshray14• 14 years ago

goes on to explain that the worst case is unlikely. That may be true, but it's still O(n).

It's not O(n), it's more like O(1 + max(0, n - m)) where n is the number of elements in the table and m is the number of buckets. The table can grow up to about n == m and it's still approximately O(1).

But what happens when you have 1000 items in each bucket?

Don't do that. Rather if you do that, then you don't get to complain that the performance of your data structure is that of the fallback strategy instead of a properly sized hashtable.

You should have begin executing your growth strategy back at about 0.5 items in each bucket.

If you keep adding elements and you want to keep reads fast, sooner or later you're going to have to add more buckets,

Sooner or later you're going to have to put more RAM in the machine too. But in the meantime, your trusty old hash-based data structure will give you reliable service.

at which time you need to re-hash every element in the table.

If latency is a concern this re-hashing can be done incrementally.

If the hashing of elements itself is expensive, you can store the resulting hash value for each element.

Note that there are three zero bits at the bottom of each 64-bit-aligned pointer value. You could use these to store three additional bits of the hash value, allowing you to grow your table by a factor of 8 without rehashing.

tptacek4• 14 years ago

Isn't that just the long way of saying "O(n)"? It's a worst-case bound.

kroidkrensen4• 14 years ago

I;'m the author. It's not hand waving, it's an attempt to write a simple, approachable article -- I'm not trying to be Knuth.

If you want details, read the two articles that are linked into the text -- in those I delve into plenty of details, and include real-world experiments.

marshray14• 14 years ago

I thought it was a great article.

chojeen• 14 years ago

> Engineers irrationally avoid hash tables...

Really? That seems about as likely as the statement 'carpenters irrationally avoid using screws'.

aidenn05• 14 years ago

Indeed, I find academia is averse to hashtables (because of the poor worst-case performance) but engineers think they are the best thing since sliced bread.

dclusin• 14 years ago

Agreed! And taken to the logical extreme often times they are used as an excuse for lazy thinking. One example is stream processing where you're processing lots of messages per second and typically have some sort of originating request ID. Keeping a map of request ID's -> handlers gets very expensive if your goal is low latency (because you perform the map lookup on every operation).

marshray14• 14 years ago

This "worst-case" issue seems silly to me.

If all your elements magically hash to the same bucket somehow and you end up having to make a list or a tree out of them, you're still no worse off than if you used a list or a tree in the first place.

Jach• 14 years ago

Language affects matters here, I think. I haven't met a Python programmer who doesn't love dictionaries, but I've seen C programmers (and to an extent, C++ programmers where 'std::map' is a red black tree) that avoid them because they have to roll their own or find and trust (and learn how to use) someone else's. Java programmers are more mixed. When the language forces you if you want to have nested hash tables to write "Map<String, Map<String, Map<String, Map<String, String>>> > meta_data = new HashMap<String, Map<String, Map<String, Map<String, String>>> >();" instead of "meta_data = {}", it's a pretty strong incentive to not use these things.

mappu• 14 years ago

To be fair to the C++ programmers, there are several legitimate reasons to avoid std::map<> - for instance, if your project doesn't use exceptions.

eranki• 14 years ago

I agree, it's a straw man. Also, who ever implements their own data structures anymore? These days people use native-language maps freely, which may be implemented as trees or hash tables.

fusiongyro4• 14 years ago

The reason functional programmers prefer trees is because it's much easier to make them persistent (in the functional sense).

tptacek4• 14 years ago

A good article, but two quick thoughts:

1. With a good hash function, it's hard to accidentally stumble on the worst-case O(n) lookup cost. But against an adversary, it is usually very easy to have that problem. This has been a well-known security issue for over a decade, and over the last 4 years we're starting to see more exploitation of it.

2. The "little trick" at the end of the document that bumps matching items to the head of their bucket chain will usually provide only a marginal speedup (if many of your lookups hit chains longer than 1, your table is too small or your hash function is broken), and that optimization comes with a cost: lookup now modifies the underlying hash table, which is sometimes very undesirable.

kibwen2• 14 years ago

Do there exist good hash functions that are resistant or immune to the attacks you mention? For example, does Python 3.3's new hash randomization provide adequate protection?

pjscott2• 14 years ago

This is what SipHash was made for: it's a cryptographic MAC that's competitive in speed with other hash functions meant for hash table use. The paper describes its design, and the weaknesses with competitors like Python's randomized hashing:

https://www.131002.net/siphash/siphash.pdf

Some code for it here:

https://www.131002.net/siphash/

mtoddh• 14 years ago

As to the first point, I remember this being described well in an older Phrack article [1] written by Solar Designer with regards to port scan detection:

In scanlogd, I'm using a hash table to lookup source addresses. This works very well for the typical case as long as the hash table is large enough (since the number of addresses we keep is limited anyway). The average lookup time is better than that of a binary search. However, an attacker can choose her addresses (most likely spoofed) to cause hash collisions, effectively replacing the hash table lookup with a linear search. Depending on how many entries we keep, this might make scanlogd not be able to pick new packets up in time.

[1] http://www.phrack.org/issues.html?issue=53&id=13#article

haberman8• 14 years ago

> and over the last 4 years we're starting to see more exploitation of it.

Interesting; this came up in the Lua community and the Lua authors (who I have a ton of respect for) agreed to fix the problem, but thought the threat was overstated. Their argument was that many other forms of DoS attack are lower hanging fruit.

http://article.gmane.org/gmane.comp.lang.lua.general/87667

bunderbunder• 14 years ago

Just to throw it out there, here's a 6th myth to consider:

> Hash tables are fast

When you're dealing with lots of keys, they're usually the best option out there. But if you're dealing with a small number of keys, a simple array can often be faster. A hash table lookup involves a constant amount of overhead resulting from calculating the key, and possibly also added indirection depending on whether the implementation uses open addressing. If the amount of time that would be spent on a simple linear or binary search of the array is less than (or even not much more than) the time that would be spent on that overhead, then the array will be faster.

Of course, the point where the hash table overtakes the array depends on a lot of factors. As usual the only sure-fire way to know which option is better in a particular situation is to measure.

fusiongyro4• 14 years ago

I recently read a story by one of Wirth's students, reminiscing about working on the Oberon compiler. They had several important principles for developing the Oberon compiler that drove development, one was something to the effect that anything you add must pay for itself or improve the speed of compilation--the benchmark being the whole Oberon system. The students had implemented a very fancy data structure, I think a balanced tree, to use with register allocation. Wirth found out and ordered them to remove it and replace it with a linked list. They groaned, but complied--and the compiler was both smaller and faster as a result, despite worsening the worst case.

marshray14• 14 years ago

Perhaps this was an example where the total number of elements was well bounded. After all, CPUs aren't growing more general-purpose registers very often, or the size of the scope considered in the scheduling may be limited by other constraints.

dchest6• 14 years ago

"I still vividly remember the day that Wirth decided to replace the elegant data structure used in the compiler’s symbol table handler by a mundane linear list. In the original compiler, the objects in the symbol table had been sorted in a tree data structure (in identifier lexical order) for fast access, with a separate linear list representing their declaration order. One day Wirth decided that there really weren’t enough objects in a typical scope to make the sorted tree cost-effective. All of us Ph.D. students were horrified: it had taken time to implement the sorted tree, the solution was elegant, and it worked well – so why would one want to throw it away and replace it by something simpler, and even worse, something as prosaic as a linear list? But of course, Wirth was right, and the simplified compiler was both smaller and faster than its predecessor."

http://www.ics.uci.edu/~franz/Site/pubs-pdf/BC03.pdf

antirez3• 14 years ago

Inside the Redis distribution you can find "dict.c" that is a very easy to understand hash table implementation that uses incremental rehashing, that is, when it needs to switch to a bigger or smaller table this happens incrementally in three ways:

1) At every operation you perform there is a rehashing step.

2) You have a function that you can call to perform a rehashing step.

3) There is an higher level function where you can say "rehash for N milliseconds" in case you have some idle time to spend for a good cause inside your program.

Another uncommon thing of dict.c is that it supports the "pick a random element" operation with guaranteed O(1) behaviour.

EDIT: Now that I look at the source, clearly while the code is easy to follow a design section should be present in the dict.c top-comment. I'll make sure to add this, but long story short:

* We use both chaining and incremental rehashing. This means that there is no need to rehash ASAP when the hash table reached the max % of elements allowed. At the same time using the incremental rehashing there is no need to block.

* We support safe and unsafe iterators: safe iterators block the rehashing when they are active, so you have the feeling you are accessing the hash table in a read-only way. Unsafe iterators are ok for looping even while an incremental rehashing is in progress, but is not ok to touch the hash table while iterating with an unsafe iterator (otherwise the iterator no longer guarantees to return all the elements, or to avoid duplicated elements).

* The hash table is rehashed both ways: if it's too full, or if it's too empty. This way there is the guarantee that a table has always a percentage between a min and max. This guarantees that our random element function is in the average case O(1).

* When we rehash, a second table is created, and stuff are moved incrementally from one to the other. When we have two tables, all the lookup / delete operations are run against both the table as the element can be in the old or in the new table. Instead insertions only happen in the new table.

Well these are the main ideas I think.

aaronblohowiak• 14 years ago

https://github.com/antirez/redis/blob/unstable/src/dict.c

antirez3• 14 years ago

Thanks, perhaps the design is even more evident here -> https://github.com/antirez/redis/blob/unstable/src/dict.h

mikeash2• 14 years ago

Just a bit of clarification, when you say "pick a random element", do you mean choosing an arbitrary element, or do you actually mean choosing one at random such that each element has a 1/N probability of being chosen?

rm9993• 14 years ago

I'd yield to someone who understands the code, but a quick glance at dictGetRandomKey() shows it is randomized, and I believe is very close to 1/N. If there are a large number of elements in a single bucket this may not be true. At an extreme, if there is one element in a bucket and N-1 in another, there is a 50% chance teh first will get picked, and 50/(N-1)% the others will.

jchonphoenix• 14 years ago

I'm not really sure this article explains any myths about hashtables at all.

Aren't all of these statements obvious is you actually understand what a hashtable is?

brey4• 14 years ago

Misses the point about B-trees.

They're not just 'good for inexact matches' - they're optimised for things like database indexes, to reduce the number of seeks over a block-based device (eg a filesystem) required for a index lookup.

tptacek4• 14 years ago

External tables are an entirely orthogonal issue to this discussion. He's comparing hash tables to in-memory balanced binary trees.

brey4• 14 years ago

third myth in the article compares B-trees to hash tables:

"Trees are better In general, trees aren’t faster for searching for exact matches. They’re slower, and here’s peer-reviewed evidence that compares B-trees, splay trees, and hashing for a variety of string types. So, why use a tree at all? Trees are good for inexact matches — say finding all names that begin with “B” — and that’s a task that hash tables can’t do."

16s• 14 years ago

C++11 has hash backed containers now if you prefer them. std::unordered_set and std::unordered_map are identical to std::set and std::map except they use hash tables rather than red black trees.

marshray14• 14 years ago

I've seen some huge (10-20x) performance gains simply by switching some of my sets and maps to unordered.

Why did they wait so ridiculously long to add this to the standard?!

malkia• 14 years ago

Isn't that implementation specific?

marshray14• 14 years ago

The standard requires amortized O(1) insert and lookup operations, so it's in practice going to be a hashtable.

CoolGuySteve• 14 years ago

Hash tables are fantastic, but:

Depending on the hash and hash table implementation, large hash tables where elements are spread across several pages in memory can pathologically thrash your caching. You can get similar behaviour to randomly accessing elements in a large array. A cache miss from L2 to RAM is extremely slow and can be about a million times slower if you have to page fault all the way into swap.

This is a good example of a case where the standard model of computer that's used in CS proofs starts to fall over because it ignores hierarchical memory and cache locality.

Hand wavily, accessing every element once in a large naive hash table will give you O(n) page faults on average whereas accessing every element sequentially in a vector will give you O(n/d) page faults where d is your page size. While asymptotically similar, in real life that constant d can be gigantic.

That being said, I'm not sure how the C++ unordered_map handles this, it's just something I experienced when running cachegrind on someone's hand rolled implementation in the past. (I 'fixed' it by making the templated class store pointers, and then locality was greatly improved because malloc's default behaviour.)

ori_b• 14 years ago

The reason this often isn't a problem in practice is that hash tables are typically used in cases where you're going to be accessing elements randomly anyways. If you're accessing elements randomly, I don't know of a data structure that will do a better job of keeping things in cache.

marshray14• 14 years ago

* A cache miss from L2 to RAM is extremely slow*

Yes, but a properly-sized hash table will result in an average of 1 to 2 cache misses per lookup regardless of how many elements. This is far better than what you get with other structures, except perhaps in specialized cases that happen to follow tree traversal.

and can be about a million times slower if you have to page fault all the way into swap.

Disk based data requires specialized algorithms.

accessing every element once in a large naive hash table will give you O(n) page faults on average whereas accessing every element sequentially in a vector will give you O(n/d) page faults where d is your page size. While asymptotically similar, in real life that constant d can be gigantic.

Sure, a vector is better when you only ever access elements in a single sequential order and don't add or remove elements anywhere except the end.

That being said, I'm not sure how the C++ unordered_map handles this

C++ defines a method of iterating over all the elements of an unordered_map. I think a typical implementation will just treat the hash memory as a vector and return values from the occupied buckets.

yason• 14 years ago

Cache locality is easily approached in closed hashing by dividing the complete slot array into aligned page-sized chunks. Then part of the hash value points to the chunk and the rest of the hash value is used to do the secondary probe linearly within that chunk so all reads take place in the L1 cache. For example, if each slot contains the hash and a pointer to the object (for final key comparison), you can fit 512 entries onto a single 4K page in a 32-bit system.

(Of course, the chunks must eventually be processed linearly if they're all full and the key isn't found till the last chunk, but this is again a degenerate case which generally isn't a problem as long as the hash table is resized often enough as it grows.)

ishbits• 14 years ago

As a developer I tend to use RB trees in the prototype phase then migrate to a hash table if the performance difference matters.

zippie• 14 years ago

I don't believe most engineers brush off hash tables because of the worst case search. Or even storage costs or implementation complexity as the author suggests.

My reason for shrugging off hash tables for most requirements: cost/complexity of inserts and deletes. Hash tables are amazing when you do offline index generation (circa Google "non-realtime" search).

However, if you ever need to have frequent updates, deletes, or inserts, you need to grow the hash table and in doing so managing the hash table usurps any search gains. For some use cases that's fine - perhaps you only optimize for reads. Hash tables are awesome for read heavy loads. Hash tables are sub-optimal for mixed read/write work loads.

On that note, I believe the Red-Black btree is far superior to hash tables for mixed work loads. RBtree's tend to be more predictable and when your application needs the insert/delete (ie, for real time updates) you don't have to worry about having to find a new data structure.

On a related note, XFS had to switch their hash over to an rbtree to fix a performance issue related to hashes falling over in costs of insert/deletes:

http://oss.sgi.com/archives/xfs/2010-09/msg00203.html

Yes there are myths about hash tables but article doesn't touch on the real truths of why engineers avoid hash tables.

dspeyer• 14 years ago

So we have two ways of dealing with overfullness. We can use linked-list buckets, which are expected O(n) or we grow and sometimes have to rehash the entire table as part of an add.

cmccabe• 14 years ago

I really disagree with this article.

"The worst case is terrible" is not a myth, it's a reality-- and it's spawned several major security vulnerabilities recently. CVE-2012-1150 for example.

"Hash tables become full, and bad things happen." Yes. Yes they absolutely do. It depends on your implementation exactly what will happen, but in every case, you are in for some pain. If you choose the "linked list per element" route, congratulations-- your hash table will gradually approximate the lookup behavior of an unsorted linked list as the number of elements gets larger. If you choose rehashing, you'll have to deal with long pauses in your program during a rehash. Hello, latency spikes! Incremental rehashing could improve this, but only at the cost of degrading memory locality even further.

"Trees are better." For most applications, trees really ARE better. Trees are simple to use and they use less memory most of the time. You really should not be using hash tables unless you have a really good idea of how many elements you are going to have, AND you believe that they will not be accessed in any particular pattern.

"Hash functions are slow." I don't even know what this statement is supposed to mean. But I do know that there are a lot of bad hash functions out there, and it's easy to choose a bad one as a novice programmer. The right hash function will depend on your data-- something I note that this article fails to mention.

"Hash tables use too much memory." A wise programmer once told me, "fancy data structures are only good when N is large-- and N is usually small." That definitely applies here. Another way to look at this is that you need to keep the hash table half empty to keep the good properties that made you choose a hash table in the first place: O(1) lookup, O(1) insert, O(1) delete, etc. So you will just have to pay the memory price.

Hash tables can be very useful for certain applications. But in general, they're an optimization that you should make only if you know what you're doing. You should be very clear on why you're using them, how many elements you expect to have, and what your strategy is if you overflow. It's not for beginners. And if you are optimizing, you should also be aware that something like a radix tree or a B-Tree may lead to much better performance, due to its much better memory locality.

Just about the only really intriguing use for hash tables on a modern CPU is in lockless data structures, but if you're considering writing one of those-- you already know all the stuff I just wrote.

afc• 14 years ago

Seems somewhat vague, I think it could be a lot more accurate. I'm a bit surprised to see it here.

It claims that it's a myth that "trees are better" than hash tables and just describes trees as better for "finding inexact matches", as in the example "finding all names that begin with B". That's too vague. It's misleading because:

1. Trees can't just answer any random vague questions, such as "Find all names that have a P anywhere". That doesn't really describe the advantages of trees. I think a more accurate formulation would be "iterating over a range of values" or "finding values based on some ordering" (eg. find the smallest element bigger than X). Or for walking the entire contents in some predefined order. Sure, this is not an article about trees, but it doesn't take more than two sentences to describe that in a much better manner.

2. For any of the former query patterns, trees are actually much better than hash tables. That's definitely not a myth, which this article would sorta have you believe.

> Chained hash tables are a very good idea. Problem solved.

Wrong. If you don't resize your hash table, the complexity of accesses will degrade linearly as it exceeds its size. If your hash uses, say, 100 buckets each with a linked lists and stores N > 100 values, an access has complexity O(N) (sure, O(N/100) in the best case (assuming perfect spread of hash keys), but that's really O(N)).

Finally, "The worst case is terrible" myth part seems somewhat naive. I think it should at least mention the idea of hash table collision DOS attacks. "This doesn't happen in practice" unless there's some attacker out to get you by triggering that. There's plenty of examples of that happening in practice, of systems vulnerable to that. See example presentation here: http://www.youtube.com/watch?v=R2Cq3CLI6H8&lr=1 Sure, that's not a reason to switch away from hash tables, but it's definitely something to consider when using them. I get a bad flavor from this simplification of "yeah, this doesn't happen in practice, at least as long as you know what your keys are".

kabdib• 14 years ago

I love hash tables. They're my favorite data structure, maybe.

A story:

Back in the 70s it appeared that every major state university had to do their own version of PL/1. At the University of Maryland it was called PL/UM. I don't know why, maybe it was a testosterone thing ("IBM took a zillion man-years to write PL/1, but look what WE did with three starving grad students, a half-soused half-professor and a keypunch operator!") (Yeah, another version of PL/1, and that doesn't necessarily make the world a better place. Anyway --)

PLUM was notorious for being slow (I don't know about bugs, but they were probably there, too), and it was pretty common for students using PLUM to have to grovel for more seconds of CPU time.

Five or six years into PLUM's use as a student language, someone discovered that all of the symbols were being hashed into the same bucket.

PLUM got amazingly fast (well, faster, at least) after that. But by then anyone with a clue had managed to scam an account on one of the bsd Vaxen and write their stuff in C.

Don't take hash tables on faith. Measure, measure, measure.

artsrc• 14 years ago

Hash Tables make iteration order hard to predict.

Hash functions rarely are meaningful outside of the context of the collection.

The tree interface leads to a simpler world.

vii• 14 years ago

Hashtables are great until they grow to a significant fraction of available memory. Then there is no way to avoid the cost of rehashing or giving up constant time access - and if your program isn't using most of memory then you can run it on a smaller computer!

ggchappell• 14 years ago

There are some good ideas here, but I must take issue with a number of the statements the author makes.

To begin with, it is not a "myth" that hash tables have poor worst-case performance. It is true that this matters little for most applications, and not at all for some, but the worst case is still there. So I would avoid using hash tables, e.g., in safety-critical systems: medical, military, etc. (Or, as I tell my students: don't program a pacemaker in Python.)

And we should note that the excuse that datasets leading to poor performance are very rare, went out 20 years ago. When the person providing your dataset is a teenager who's trying to break your system just for the fun of it, rarity does not mean quite what you might think.

Second, hash tables do indeed have performance problems when they fill up. True, there are ways around this, and any decent implementation of a mutable hash table will include a strategy for handling these situations.

And that suggests a myth the author of this article might believe: that any ol' programmer can & should write their own hash table. I don't agree. Don't write a hash table for use in production code unless you're sure you know what you're doing. And even if you do, someone else's polished & tested hash table is likely to be better than what you're going to come up with.

Lastly, balanced search trees do have better worst-case behavior. That mostly doesn't matter, but sometimes it does. (You have my permission to use a Red-Black Tree in your pacemaker code.)

norswap• 14 years ago

I'm jumping on the occasion to ask a review of my own hash table implementation:

https://github.com/norswap/nucleotides/blob/master/src/map.c (think also to peruse the documentation and the tests!)

I'm open to any remarks and criticisms: performance, code style, etc. Since the implementation is meant to be simple and educational I may not act on all of them, tough.

philluminati• 14 years ago

http://global.sitesafety.trendmicro.com/

Myths about Hash Tables

Related Stories