Timeline for Pset6: Is it possible implement a 3D Hash table Matrix?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2020 at 8:37 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 24, 2014 at 21:37 | vote | accept | Erin Magner | ||
| Dec 24, 2014 at 18:42 | history | edited | abelinux | CC BY-SA 3.0 |
extended explanation based on comment's questions
|
| Dec 24, 2014 at 18:09 | comment | added | abelinux | This is starting to feel like a new question ;) See my edited answer. | |
| Dec 24, 2014 at 17:21 | comment | added | Erin Magner |
Excellent! Thank you again, you are very helpful, and I hope you have a happy holiday. One thing I am still unsure about, is how the hash table is different from an array, in terms of malloc. This quote in particular from the Wiki hash table article about separate chaining vs with list head cells "The disadvantage is that an empty bucket takes the same space as a bucket with one entry." Does this mean that the hash doesn't return a value in an array (ie table[0] table[1])? Does this mean a million possible buckets have the same malloc as 100000 if there are only 20000 entries?
|
|
| Dec 24, 2014 at 2:35 | comment | added | abelinux |
Here's an example of a widely used hash function (Bob Jenkins' "One-at-a-Time Hash"). As you see, the implementation turns out to be "simple" (of course, the merit lies in it being fast and reliable), and there's no randomness whatsoever: the returned int is "merely" the result of adding up the value of each char in the key, and then applying several bitwise operations to the result. That way you guarantee the final value is in the range of an int. And, according the the author, bitwise operations are way faster than mod (%).
|
|
| Dec 24, 2014 at 2:15 | comment | added | abelinux | There's a nice Wiki about hash functions you should check. Underneath the jargon there's the Properties seccion which explains clearly the requirements for a good hash function. I'm not (even close to) an expert in the subject, but I do can say that "random number generators" is not the way to go. Simply because there's no way you can guarantee you'll get the same hashed value every time for the same input, which is the most important atribute of a viable hash function. | |
| Dec 24, 2014 at 2:01 | comment | added | Erin Magner | and perhaps to use that formula on the middle three letters, because that would likely produce the least collisions? Am I getting it yet? | |
| Dec 24, 2014 at 1:11 | comment | added | Erin Magner | Actually, Formula: (a*26*26(+26)+((26*b)+c)...because the other formula might repeat itself...sort of like x^3 +x^2+2x | |
| Dec 24, 2014 at 0:14 | comment | added | Erin Magner | Thank you, this is a very clear and helpful response. If I understand you correctly, is that ideal hash functions might use a random number generator in the arithmetic to store each data at unique numbers to minimize collisions? Considering how little I understand it, would you recommend me trying out one of the common hash functions, like the additive hash or the XOR hash, or do you think I would be able to write one? I wanted to use the formula a((26*b)+c) as ...{a, b, c}+[rest of word] to return the int, but also code which returned int's map to unique hash, to avoid space for consonants | |
| Dec 23, 2014 at 15:07 | history | answered | abelinux | CC BY-SA 3.0 |