I know strings are just allocating a blob of bytes and usually reserving the last for null terminator, but what about arrays? Is it just like in C where you allocate a blob of bytes but now you manually calculate where the index is based on item size?
Yes, that is roughly it, although there is more to the topic, related to arrays and pointers, etc. In fact C's way of doing it is pretty low-level too and similar to assembly - it just adds the address of the origin of the array (i.e. the array name. which is a pointer to the start of the array) and the index times the size of the array element, to get to the memory location of the indexed item in the array.
A surprising point I read a while ago is that due to this, in C, the expression a[i] is equivalent to i[a], where a is the array name and i is the index (int variable). This is because C resolves a[i] to:
*(a + i),
meaning, dereference the pointer calculated by adding the offset i to the pointer a, and that expression:
*(a + i),
by the commutativity law of arithmetic, is the same as:
*(i + a),
which can be converted to i[a] by the same C resolution rule in reverse. I actually tried this out earlier when I first read it, on either Microsoft C compilers on Windows or gcc on Linux, or both, and it worked. Not sure, it might have changed for some reason now, maybe due to later versions of the C standard. Should try it out again.
The Kernighan and Ritchie book "The C Programming Language" is be a good introduction to how arrays and pointers work (and their inter-relationship). (Seeing your profile, I guess you may have read it, but just saying.) I had read the original version and the 2nd (ANSI C) version. Not sure if there is an updated version after that.
In the versions I read, they explain arrays and pointers in C pretty well (although you have to do some work yourself, it is not dumbed-down teaching like some you see nowadays).
What about hash tables, that seems even more confusing...
The K&R book had a nice simple implementation of a hash table in C too. The hash function (from memory) was something like just adding up all the characters's int values (in the string used as the hash key) and doing a division modulo some prime number (like 31). There was other stuff for handling collisions and buckets and so on. And that was of course only a demo version (though it did work), there are more advanced versions.
(Sorry for a few multiple edits, I was not familiar with how asterisks are used in HN as markup, so had to edit it a few times.)
Here are a few links for others who might not know about how they are used:
Comments
Yes, that is roughly it, although there is more to the topic, related to arrays and pointers, etc. In fact C's way of doing it is pretty low-level too and similar to assembly - it just adds the address of the origin of the array (i.e. the array name. which is a pointer to the start of the array) and the index times the size of the array element, to get to the memory location of the indexed item in the array.
A surprising point I read a while ago is that due to this, in C, the expression a[i] is equivalent to i[a], where a is the array name and i is the index (int variable). This is because C resolves a[i] to:
meaning, dereference the pointer calculated by adding the offset i to the pointer a, and that expression: by the commutativity law of arithmetic, is the same as: which can be converted to i[a] by the same C resolution rule in reverse. I actually tried this out earlier when I first read it, on either Microsoft C compilers on Windows or gcc on Linux, or both, and it worked. Not sure, it might have changed for some reason now, maybe due to later versions of the C standard. Should try it out again.The Kernighan and Ritchie book "The C Programming Language" is be a good introduction to how arrays and pointers work (and their inter-relationship). (Seeing your profile, I guess you may have read it, but just saying.) I had read the original version and the 2nd (ANSI C) version. Not sure if there is an updated version after that.
In the versions I read, they explain arrays and pointers in C pretty well (although you have to do some work yourself, it is not dumbed-down teaching like some you see nowadays).
The K&R book had a nice simple implementation of a hash table in C too. The hash function (from memory) was something like just adding up all the characters's int values (in the string used as the hash key) and doing a division modulo some prime number (like 31). There was other stuff for handling collisions and buckets and so on. And that was of course only a demo version (though it did work), there are more advanced versions.
(Sorry for a few multiple edits, I was not familiar with how asterisks are used in HN as markup, so had to edit it a few times.)
Here are a few links for others who might not know about how they are used:
Google search for:
how to disable meaning of asterisk in hacker news
https://www.google.com/search?q=how+to+disable+meaning+of+as...
and from it:
https://news.ycombinator.com/item?id=12521497