Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
