Timeline for How does a hash table work?
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 13, 2018 at 8:31 | history | suggested | k.wig | CC BY-SA 4.0 |
"with" defines the action in which you want to fill the library up. Grammatical error
|
| Oct 12, 2018 at 17:50 | review | Suggested edits | |||
| S Oct 13, 2018 at 8:31 | |||||
| Feb 13, 2018 at 6:25 | comment | added | Tony Delroy |
@KyleDelaney: need the "@Tony" thing to get notified of your comments. Seems you're wondering about chaining: say we have three value nodes A{ptrA, valueA}, B{ptrB, valueB}, C{ptrC, valueC}, and a hash table with three buckets [ptr1, ptr2, ptr3]. Regardless of whether there are collisions when inserting, the memory usage is fixed. You may have no collisions: A{NULL, valueA} B{NULL, valueB} C{NULL, valueC} and [&A, &B, &C], or all collisions A{&B, valueA} B{&C, valueB}, C{NULL, valueC} and [NULL, &A, NULL]: are the NULL buckets "wasted"? Kinda, kinda not. Same total memory used.
|
|
| Sep 1, 2017 at 13:08 | comment | added | Kyle Delaney | Don't the extra null pointers make the memory usage worse? Won't the hash table contain a lot of zeroes that it wouldn't have to contain otherwise? | |
| Aug 31, 2017 at 4:11 | comment | added | Tony Delroy | @KyleDelaney: No for closed hashing (where collisions are handled by finding an alternative bucket, which means the memory usage is fixed but you spend more time searching across buckets). For open hashing aka chaining in a pathological case (terrible hash function or inputs deliberately crafted to collide by some adversary/hacker) you could end up with most hash buckets empty, but the total memory usage is no worse - just more pointers NULL instead of indexing into the data usefully. | |
| Jan 26, 2017 at 7:56 | comment | added | Lasse V. Karlsen | Muahaha, it's my secret plan to conquer the world, leave evil answers on Stack Overflow. Oops, not so secret anymore... | |
| Jan 19, 2017 at 2:31 | history | edited | aug | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Jan 19, 2017 at 2:20 | history | edited | aug | CC BY-SA 3.0 |
Added some formal terminology for those curious
|
| Dec 21, 2016 at 5:12 | comment | added | Kyle Delaney | Do hash tables have the potential to leave a lot of empty wasted space where nothing is being stored, forcing the data to take up more room than it would otherwise? | |
| May 2, 2016 at 4:49 | comment | added | Tony Delroy | @user107986: "I'd use first algorithm, second algorithm and so on until I find the book whose title is the one I'm looking for?" - yes. Still, it's more common to search as a a sequence of offsets from the original hashed-to position, such as each position thereafter until one's empty (indicating no match/a place you can insert a new book/value) (called linear probing), or at +1, +4, +9, +16 etc. (called quadratic probing).... | |
| S Oct 18, 2015 at 16:19 | history | suggested | Student | CC BY-SA 3.0 |
grammar and spelling
|
| Oct 18, 2015 at 15:34 | review | Suggested edits | |||
| S Oct 18, 2015 at 16:19 | |||||
| Sep 6, 2015 at 9:45 | comment | added | user107986 | 'Various collision handling methods exist, including running the data into yet another calculation to get another spot in the table' - what do you mean by another calculation? It is just another algorithm? OK, so suppose we use another algorithm that outputs a different number based on the book name. Then later on, if I were to find that book, how would I know which algorithm to use? I'd use first algorithm, second algorithm and so on until I find the book whose title is the one I'm looking for? | |
| Mar 12, 2015 at 13:40 | comment | added | Lasse V. Karlsen | No, it is just a number. You would just number each shelf and slot starting at 0 or 1 and increasing by 1 for each slot on that shelf, then continue numbering on the next shelf. | |
| Jan 26, 2015 at 10:14 | comment | added | Johnny_D | Thanks for such a great explanation. Do you know where I can find more technical details regarding how it's implemented in 4.x .Net framework? | |
| Dec 30, 2014 at 11:38 | history | edited | Lasse V. Karlsen | CC BY-SA 3.0 |
fixed modulus counting
|
| Dec 30, 2014 at 4:25 | review | Suggested edits | |||
| Dec 30, 2014 at 5:09 | |||||
| Dec 28, 2014 at 23:28 | history | edited | Zach Saucier | CC BY-SA 3.0 |
Fixed the English - used way too many commas and some other things
|
| Oct 16, 2013 at 22:46 | history | edited | fncomp | CC BY-SA 3.0 |
Minor typos
|
| Jan 24, 2013 at 16:04 | history | edited | David Burrows | CC BY-SA 3.0 |
edited body
|
| Apr 8, 2009 at 16:33 | history | answered | Lasse V. Karlsen | CC BY-SA 2.5 |