Printable View
As long as you do modulus on the ID by the number of buckets (which is pre-determined), yeah. You cannot just use the ID itself, if I have 5 records and the ids are:Quote:
Originally Posted by Subsonics
1234523533
9922883
42
1
23456234134
I suppose I could be safe and use a 10000000000 element array, but...
That's obvious MK but, first of all. No one in their right mind would implement a database for student record from scratch using c and hash tables. But, if that was the case you would create ID's from 1 and up, so list of students of 5 would have ID 1-5 (or 0-4). Then perhaps if some rules are involved in creating the ID like year, and so on, you could easily make a formula such that you end up at 0 for the first student in the database.Quote:
Originally Posted by MK27
Speak for yourself! I've never looked at the source code for (eg) mySQL and would refuse to do so :p, but it's in C and I bet there's some very hash tablish stuff in there.Quote:
Originally Posted by Subsonics
There's a difference between an ID number you can make up (meaning it is internal) and one which is a given (part of what you are responsible for recording).
I never looked at MySQL source code either, and only superficially at SQLite source code, but according to the documentation, SQLite uses B-trees.Quote:
Originally Posted by MK27
But I suspect Subsonics might have intended to say that a sane person would use a database engine like SQLite instead of coding the nitty gritty database details from scratch :)
Yes but that was sort of my point, you would choose some working database solution, mySQL, Oracle etc. And I'm sure there are hash tables involved somewhere in their source, but I'm not going to look into it to confirm it either haha.Quote:
Originally Posted by MK27
Absolutely, but if you are given these requirements, and probably some other (like being able to search on all terms in the record) then you would probably not choose a hash table to begin with. My point was that a numeric key that is an ID, (that is, it's unique and serve only as identification) can be arbitrarily chosen and still serve this same purpose. If you are going to search on name or make a dictionary where a word is a key and the definition is the value, then you don't have the option to choose the key.Quote:
Originally Posted by MK27
Yes, that was what I had in mind. SQLite seems like a nice solution for c, I have just looked over it briefly yet but.Quote:
Originally Posted by laserlight
Hmmm. There's a bit of a catch here. If you assign an ID number, internally, to each record, how can you search for a given record (based on content) by using the ID number you have arbitrarily assigned? I have five students:Quote:
Originally Posted by Subsonics
Bob
Mickey
Troubadour
Ruffian
Sally-Anne
So I give them ID numbers 1-5. Now the user wants to find the record for "Troubadour"...unless I have a separate hash table (to look up the keys for "the real" hash table), we have an issue.
Anyway, I think hash tables do have a tremendous purpose in general programming. I don't actually use them in C that much, but I use the "built in" equivalent else where (eg, perl hashes). If you make the "key" a sequential number, you are not talking about a hash table -- that's just an array.
SQlite is also great for general purpose programming because you don't need a server to run it, you have a discrete file. MySQL and postgres work in a very similar way, but require a running server. The server model (presumably) has higher performance.Quote:
Originally Posted by Subsonics
Yes but that applies to hash tables in general, there is one key and one value, but suppose you want to search for name, phone number or grades, or a combination of all of these, or only students enrolled this year who got at least one A and are male.Quote:
Originally Posted by MK27
I agree, but on that last part. If you have an array of pointers to structs, each struct containing the information. Then if you make an ID that is the array index or calculate the index using a hashing function should not matter the way I see it. Other than that a direct relation should be faster and simpler to implement since you don't have to search thru a linked list at the index your hashing function gives you, and you also don't need to calculate the hash.Quote:
Originally Posted by MK27
If you don't actually need a database server, then an embedded database engine could actually provide higher performance as there would be no need to communicate with the database server.Quote:
Originally Posted by MK27
You would need to maintain a set of hash tables, one for each criteria. But in this case SQL is definitely the way to go.Quote:
Originally Posted by Subsonics
I think a one to one key/value relationship is a much more common "task" tho. Eg, you parse a directory tree of uniquely named files (I keep all my mp3's this way). You want to know the exact path of "songx", the key is "songx" -- the value associated with the key can be a pointer containing more info. Chances are, there is only one criteria that's unique (in this case the name), the other details are just...details. You *can* do operations on those other criteria (show me only files under a certain size) but I still think just using the primary key (name) and rejecting long ones is how to do it.
If you use interpreted languages (perl, python, ruby, php, etc) hashes (or whatever they are called) are a staple, that kind of thing is totally normative and gives you a *HUGE* amount of functionality over an array. I use hashes about as much as arrays. C++ maps are the same but C++ is pretty awkward, comparatively. IMO.
Within a single process, yeah, that makes sense. I have never tried this. But if you have a forked/threaded web server, it's relationship to the SQL server amounts to the same thing I think. Currently these aren't choices I get to make ;)Quote:
Originally Posted by laserlight