Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I took an algorithms class on Coursera. The professor in the video about hash tables said that

What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?

share|improve this question

3 Answers 3

up vote 11 down vote accepted

Pathological data is supposed to be data that makes things go wrong in some way for your intended computation. It can be called pathological when it is rare enough in actual uses, so that things work OK most of the time. This can sometimes be made mathematically more precise (for example with probabilities), but the use of the word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for pathological people, meaning those people who are allergic to tomatoes. It can actually kill in some cases. But people allergic to tomatoes are very rare so that tomato dishes are considered excellent, except in pathological cases.

There are many algorithms that, while having a worst case complexity above the optimal one, are on the average as good or better than worst case optimal algorithm. If you compare quicksort and merge sort, quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst case. But people will often use quicksort, because they both are time $O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the fact that the $O(n^2)$ time complexity actually occurs only on pathological (implying bad but rare) cases.

share|improve this answer
1  
As an aside on sorts, it can also be important that mergesort is stable while quicksort is not. –  WChargin Jun 14 at 23:26

Pathological data is data that will make the algorithm perform bad. For hash tables, pathological data is data that causes collisions. That of course depends on the hash function being used.

For example, if your hash function adds the characters together: hash("abcd") = 'a' + 'b' + 'c' + 'd'. Then pathological data looks like:

{"abcd", "dcba", "cbda", ...}. Any permutation of "abcd" will hash to the same position so you will end up with a linked list which you were trying to avoid in the first place.

Non-pathological data is data that is not pathological.

share|improve this answer

another way to think about this: hash keys are like separate "bins" that contain the data. one would expect/hope that the data is evenly distributed between all the bins, "balanced". for nonpathological data each bin has/contains roughly the same amount of data. if the data is pathological (wrt key hashing algorithm), it all "piles up" in fewer bins, and some bins have far less. this is inefficient because the lookup time increases (and efficiency decreases/converges to that of looking up an unsorted list) when the bins are filled larger. note that merely changing the key hashing algorithm could turn the data from "pathological" to "non pathological" or vice versa, hence the importance of the hashing algorithm.

also there are many other algorithms for which the distinction of "pathlogical vs nonpathological" might be applied, with basically the "pathological" data making the algorithm perform in worse case (eg the concept is also used with sorting algorithms). as you can see its a statistical concept. also for the same problem, data that is "pathological" for one algorithm might not be "pathlogical" for another. etc.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.