3 ms·

Regarding the dispute of whether Ada wrote the first program. On a related topic, I believe that credit for the invention of hashing should go to certain schol

Regarding the dispute of whether Ada wrote the first program. On a related topic, I believe that credit for the invention of hashing should go to certain scholars in China. The invention of a data structure and algorithm must not be confused with its first implementation in electronic computers. For at least a century before the computing revolution, hashing was used in China to find characters in dictionaries. First, a character is examined, and reduced to a numeric code according to steps that constitute a hashing function. For instance the Four Corner Code. The code is then used to find a page or section of the dictionary by direct access: the mapping between codes and dictionary sections is straightforward. The character is then found within a small bucket of collisions by a linear search.

poulpy123 2y ago
She certainly didn't write the first code, except if you think that babbage could have worked for year on his machine without ever writing a code. However the first program published that was designed to work on what is considered as a computer is under her name. As their names say, algorithms and code are much older
lmm 2y ago
The Four Corner Code is not really a hash, just an index. Do you have evidence of the use of unnatural, random-looking "hash" functions for the sake of an even distribution? That's the key insight that makes a hash table what it is.
- firesteelrain 2y ago
  Four corner code is foundational to modern hash tables and helped with collision resolution.
- kazinator 2y ago
  The 4cc gets a decent distribution in that you don't have to examine very many collisions to find the character you're looking for (or conclude it's not found). A poor distribution is an obvious bug in hashing; if you don't suffer from that bug, you don't have to do anything. If you have the bug, it's obvious you have to change your hash calculation to avoid it. The developers of 4cc may have struggled with bugs where they had buckets that were too large for efficient searching. Convoluted hashing functions are not always used for hash tables. When hash tables are pointers (e.g. object identities themselves are used as keys to associated objects with additional properties), sophisticated hashing functions are not needed; e.g. simply extracting a few bits of the pointer, avoiding the lowest bits (which might all be zero due to alignment!). I believe that the 4cc dictionaries hit upon the key insights of hashing: calculating a numeric key from an object which then directly identifies a small search bucket. The Four Corner Code abandons semantics like radicals. Codes are assigned according to certain stroke patterns in the four quadrants of the character, without regard for their semantic role. The inventors hit a key insight there: that any way of calculating a hash code is valid as long as it can be consistently followed, and leads to short searches. The function can look at meaningless fragments of the object (exactly like when we take the middle bits of a pointer). A character's etymology need not play any role in how it is digested. Whereas in the radical methods, you have to know that for instance 火 and 灬 both mean "fire" and are understood as the same radical #86. So in some sense, the predecessor methods like radical indexing may have been almost-hashing. It's hard to argue that 4cc isn't.
  - lmm 2y ago
    > A poor distribution is an obvious bug in hashing; if you don't suffer from that bug, you don't have to do anything. Right, but if you don't have and solve that problem then what you have made isn't a hash table. Often you don't need a hash table - if you have something that already has a nice distribution, you can use a simpler data structure (like, IDK, a radix tree) and get all the properties you wanted. > The inventors hit a key insight there: that any way of calculating a hash code is valid as long as it can be consistently followed, and leads to short searches. If they did, then I would agree you're right. But do we know that they did? Or might they have seen it as just a different way of considering radicals? (E.g. did they ever try indexing anything else that way, not just characters?)
    - kazinator 2y ago
      Note that a radix tree and hash table are not mutually exclusive. A radix tree is a way of representing a sparse table. That could be used as a hash table. There's a trade off there because if the table is very sparse, and we're using hashing, we could just shrink the table so as not to have it so sparse, and then just make it a regular array. The key aspect of the four corner code is that it mashes together completely unrelated characters. There's no meaningful index to it. It's not easy to look at a four corner code to figure out the list of characters it aliases for.

poulpy123 2y ago

She certainly didn't write the first code, except if you think that babbage could have worked for year on his machine without ever writing a code. However the first program published that was designed to work on what is considered as a computer is under her name. As their names say, algorithms and code are much older

lmm 2y ago

The Four Corner Code is not really a hash, just an index. Do you have evidence of the use of unnatural, random-looking "hash" functions for the sake of an even distribution? That's the key insight that makes a hash table what it is.

firesteelrain 2y ago
Four corner code is foundational to modern hash tables and helped with collision resolution.
kazinator 2y ago
The 4cc gets a decent distribution in that you don't have to examine very many collisions to find the character you're looking for (or conclude it's not found). A poor distribution is an obvious bug in hashing; if you don't suffer from that bug, you don't have to do anything. If you have the bug, it's obvious you have to change your hash calculation to avoid it. The developers of 4cc may have struggled with bugs where they had buckets that were too large for efficient searching. Convoluted hashing functions are not always used for hash tables. When hash tables are pointers (e.g. object identities themselves are used as keys to associated objects with additional properties), sophisticated hashing functions are not needed; e.g. simply extracting a few bits of the pointer, avoiding the lowest bits (which might all be zero due to alignment!). I believe that the 4cc dictionaries hit upon the key insights of hashing: calculating a numeric key from an object which then directly identifies a small search bucket. The Four Corner Code abandons semantics like radicals. Codes are assigned according to certain stroke patterns in the four quadrants of the character, without regard for their semantic role. The inventors hit a key insight there: that any way of calculating a hash code is valid as long as it can be consistently followed, and leads to short searches. The function can look at meaningless fragments of the object (exactly like when we take the middle bits of a pointer). A character's etymology need not play any role in how it is digested. Whereas in the radical methods, you have to know that for instance 火 and 灬 both mean "fire" and are understood as the same radical #86. So in some sense, the predecessor methods like radical indexing may have been almost-hashing. It's hard to argue that 4cc isn't.
- lmm 2y ago
  > A poor distribution is an obvious bug in hashing; if you don't suffer from that bug, you don't have to do anything. Right, but if you don't have and solve that problem then what you have made isn't a hash table. Often you don't need a hash table - if you have something that already has a nice distribution, you can use a simpler data structure (like, IDK, a radix tree) and get all the properties you wanted. > The inventors hit a key insight there: that any way of calculating a hash code is valid as long as it can be consistently followed, and leads to short searches. If they did, then I would agree you're right. But do we know that they did? Or might they have seen it as just a different way of considering radicals? (E.g. did they ever try indexing anything else that way, not just characters?)
  - kazinator 2y ago
    Note that a radix tree and hash table are not mutually exclusive. A radix tree is a way of representing a sparse table. That could be used as a hash table. There's a trade off there because if the table is very sparse, and we're using hashing, we could just shrink the table so as not to have it so sparse, and then just make it a regular array. The key aspect of the four corner code is that it mashes together completely unrelated characters. There's no meaningful index to it. It's not easy to look at a four corner code to figure out the list of characters it aliases for.