4 ms·

Hash table realization seems to be harmful with the "no collisions" assumption. That's like writing a red black tree and assuming that insert/delete operations

Hash table realization seems to be harmful with the "no collisions" assumption. That's like writing a red black tree and assuming that insert/delete operations will keep tree balanced so we don't need rotations.

duaneb 10y ago
Yea, a hash table without even bucketing(?) is laughably useless.
elliotec 10y ago
At least the ASCII art for the hash table section was pretty funny.
ksk 10y ago
How is it harmful? You really think that somebody who is going to write a red black tree implementation (or similar) is going to use this document as a reference? That'd be like complaining about a high school physics textbook because somebody from Boeing might use it to design a plane.
- hexane360 10y ago
  I'm not sure I understand. OP just made an analogy to red black trees. He's not suggesting anyone will make bad trees because of this document. He's just saying that the hash table is pretty useless if two random keys could access the same memory.
  - ksk 10y ago
    >He's just saying that the hash table is pretty useless if two random keys could access the same memory. That is already mentioned in the document itself. Also mentioned is that a proper implementation would have to deal with collisions. As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have.
    - coldtea 10y ago
      >As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have. The value of an explanation of simple concepts is in their simple AND adequate explanation. You can cut the implementation details, but can't cut essential properties to simplify, because then you're not explaining the original concept at all.
- xg15 10y ago
  Some simplifications may actually be harmful to understanding if they throw away key points or introduce logical contradictions. For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") - and of course actual hash tables solve the conundrum by acknowledging collisions and defining ways to deal with them. But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. That can lead to frustration in the best case or to serious misconceptions in the worst case. Of course there is nothing wrong with saying "let's ignore those points for now, I'll explain later". Also I guess it depends very much on the learning style of the reader. But bad simplification can be very annoying for some learners.
  - ksk 10y ago
    >For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function Well, AFAICT there is no mention of any of this in the document. No "promise" or any such thing has been said or implied. Please stick to what the author has actually said rather than what you imagine people are thinking about when reading the document. >. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") No, it doesn't tell me that at all, because that point is not brought up in the document. But is that how you think most people learn? Using common sense? >But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. Sure, you think those are the logical contradictions in the readers' minds. Can you actually establish that? > But bad simplification can be very annoying for some learners. A list of what is annoying for "some" learners is quite possibly very very large. Lets not.... -- Anyway, we can go down this rabbit hole, but it isn't actually productive, and quite boring to be honest. My point is that every-time someone tries simplify something for beginners, people seem to relish that opportunity to show everyone how "smart" they are about trivial data-structures. Yes, if you want somebody to make an expository article for beginners with the detail of something like TAOCP, then yeah, you're going to be disappointed. But, you can and should learn Newtonian physics, even if its "wrong", before you move on to Einstein.

duaneb 10y ago

Yea, a hash table without even bucketing(?) is laughably useless.

elliotec 10y ago

At least the ASCII art for the hash table section was pretty funny.

ksk 10y ago

How is it harmful? You really think that somebody who is going to write a red black tree implementation (or similar) is going to use this document as a reference? That'd be like complaining about a high school physics textbook because somebody from Boeing might use it to design a plane.

hexane360 10y ago
I'm not sure I understand. OP just made an analogy to red black trees. He's not suggesting anyone will make bad trees because of this document. He's just saying that the hash table is pretty useless if two random keys could access the same memory.
- ksk 10y ago
  >He's just saying that the hash table is pretty useless if two random keys could access the same memory. That is already mentioned in the document itself. Also mentioned is that a proper implementation would have to deal with collisions. As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have.
  - coldtea 10y ago
    >As to it being useless.. the value of content is in its explanation of simple concepts, not in some imagined production-quality requirement that people want to assume it must have. The value of an explanation of simple concepts is in their simple AND adequate explanation. You can cut the implementation details, but can't cut essential properties to simplify, because then you're not explaining the original concept at all.
xg15 10y ago
Some simplifications may actually be harmful to understanding if they throw away key points or introduce logical contradictions. For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") - and of course actual hash tables solve the conundrum by acknowledging collisions and defining ways to deal with them. But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. That can lead to frustration in the best case or to serious misconceptions in the worst case. Of course there is nothing wrong with saying "let's ignore those points for now, I'll explain later". Also I guess it depends very much on the learning style of the reader. But bad simplification can be very annoying for some learners.
- ksk 10y ago
  >For a hash table, the general "promise" is that you map a very large space of keys (e.g. all strings) to a very small space of indexes using a simple function Well, AFAICT there is no mention of any of this in the document. No "promise" or any such thing has been said or implied. Please stick to what the author has actually said rather than what you imagine people are thinking about when reading the document. >. Common sense might tell you that this shouldn't be possible ("how can you put something big into something small?") No, it doesn't tell me that at all, because that point is not brought up in the document. But is that how you think most people learn? Using common sense? >But by saying "let's assume no collisions" the reader is asked to just ignore the logical contradiction instead of solving it. Sure, you think those are the logical contradictions in the readers' minds. Can you actually establish that? > But bad simplification can be very annoying for some learners. A list of what is annoying for "some" learners is quite possibly very very large. Lets not.... -- Anyway, we can go down this rabbit hole, but it isn't actually productive, and quite boring to be honest. My point is that every-time someone tries simplify something for beginners, people seem to relish that opportunity to show everyone how "smart" they are about trivial data-structures. Yes, if you want somebody to make an expository article for beginners with the detail of something like TAOCP, then yeah, you're going to be disappointed. But, you can and should learn Newtonian physics, even if its "wrong", before you move on to Einstein.