Timeline for Hash table collisions: why use a linked list if we can use a hash set?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Jan 4, 2016 at 6:54 | comment | added | Kaveh | en.wikipedia.org/wiki/Perfect_hash_function | |
| Dec 30, 2015 at 10:29 | comment | added | Raphael | @yshavit Good point. (I'll note, though, that this discussion does not fit the question here. If you think it useful, feel free to post a question along the lines of "Why is it useful to use BSTs in hashtables?".) | |
| Dec 30, 2015 at 4:56 | comment | added | yshavit |
The tree-based approach has the benefit that it's resistant DoS attacks in which an attacker intentionally creates a lot of collisions, in the hope of turning an O(1) map into O(n) -- and thus a loop that's expected to take O(n) into O(n^2). For instance, a web server that throws query string params (?a=1&b=2&...) into a map can be attacked by creating a long query where all the parameters hash the same way, if you know the hashing algorithm. There are a few ways to defend against this; one is to have collisions resolve in a balanced tree (this is what Java 8 does, for instance).
|
|
| Dec 29, 2015 at 17:17 | comment | added | Raphael | @DarrelHoffman Yes, that's definitely possible. Depending on the search tree of choice it's never worse than a linear list but strictly better if there are many collisions. | |
| Dec 29, 2015 at 15:33 | comment | added | Darrel Hoffman | On the other hand, I have seen implementations that use some sort of balanced binary tree (AVL, red-black, etc.) instead of a linked list to handle collisions. This brings the worst-case down to O(log n) rather than O(n), though it does considerably increase the complexity, and is most likely to be only marginally beneficial unless you have a LOT of collisions - a situation which can be more easily avoided simply by using a larger hash table and/or a better hash function. | |
| Dec 29, 2015 at 12:24 | comment | added | Raphael | It works in a programming context, sure. It may even outperform an implementation with linear lists (I doubt it). We are on a site about computer science, though, and then the answer is: you don't get to implement A using A. If you can't follow that, I'm not sure this is the right site for you (yet). | |
| Dec 29, 2015 at 12:21 | comment | added | programmer | It does work, I used it to solve a coding challenge and it passed. I used it as a way to store an adjacency list for a graph. | |
| Dec 29, 2015 at 12:19 | comment | added | Raphael | In your C++ code, just use a HashSet implementation. From a CS perspective, that approach does not make sense for the reasons I state in my answer. | |
| Dec 29, 2015 at 12:17 | comment | added | programmer | Many thanks. Yes I understand that, so I think I phrased my question incorrectly. What I was saying was that we almost always get collisions, and linked lists provide a way to deal with that but with a non constant lookup time. And I was suggesting using a hash set instead as in my C++ code (to get constant time lookup), although I am not sure how this would work in memory. | |
| Dec 29, 2015 at 12:14 | comment | added | Raphael | @programmer Yes, but that's an unlikely event. Anyway, unqualified statements about running time in CS always mean worst-case performance. Hence, the statement "hashtables have [WC] constant lookup" is wrong. Both "hashtables have AC constant lookup" and "hashtables have BC constant lookup" are true, though. I recommend you study some basics of algorithm analysis. | |
| Dec 29, 2015 at 12:11 | comment | added | programmer | Assuming we never get collisions, the lookup time for a hash table is constant, isn't it? I create the hash set as in the C++ code I wrote, but I am indeed confused as to how this would work in memory | |
| Dec 29, 2015 at 12:08 | history | answered | Raphael | CC BY-SA 3.0 |