|
Re: Re: Graphs & Hash Tables (re: programming)
| quote: | Originally posted by DigiNut
A hash table is a system of storing objects based on some numeric function of that object. A hash can be any function, but as an example, let's say you're storing strings in a 100-element hash table, one way of hashing would be to take the ASCII codes of all the characters, add them together (sum), and store the string in array element (sum % 100).
The purpose is to provide a faster method of storing and searching, i.e. rather than having to sort alphabetically or scan through the entire array to find something.
Of course there also needs to be a system of dealing with hash conflicts, since no hashing function is completely unique. But that's a whole other topic.
As for graphs... I think we need some context there. |
yes, basically.
hash tables are among the most convenient data-storage structures when it comes to insertion and searching (it's practically o[1] in the big-o notation). coders usually use them when there's a need to look up tens of thousands of items in less than a second. in fact, hash tabels *are* the fastest data structure. they are especially useful when large amounts of data are involved. they are what is typically used in spell checkers and as symbol tables in compilers. another advantage of the tables is their insensitivity toward the order in which data is stored/inserted (unlike trees). as a result, programming for hash tables is much and much easier than for (binary) trees. there are three kinds of their conceptual implementations: linear probing, quadric probing and separate chaining. all of them have their pros and cons. though hash tables with separate chaining are the hardest to program.
of course, as with all data-storage structures, hash tables have their own disadvantages. for one thing, all of them are based on arrays, and arrays are somewhat hard to expend once they've been created. in addition, with hash tables, there's no way to visit the stored items in any kind of order - that is, no ordered traversal is basically possible. that's where binary search trees would be a better choice. also, the efficiency of some particular kinds of hash tables is inversely proportional to their "fullness." their performance might decrease drastically if they become too full.
as for the graphs, i *think* in this case it referes to the big-o notation, which is merely a measure of the efficiency of a particular algorithm. one important thing to remember is that the purpose of a big-o graph (which shows the relationship between time and number of items) is NOT to depict an actual figure for running time, but rather to demonstrate the way running times are affected by the number of items. in other words, this is a kind of comparison that is directly related to the number of items. different algorithms have different running time in big-o notation and therefore have different graphs. for example,
the running time of linear search is represented through the o(n) notation where n is the number of items in the array.
the running time of insertion in an *unoredered* array is always o(1) = 1
the running time of insertion in an ordered array is o(n)
the running time of deletion in any array is o(n) as well
binary search is proportional to log(n)
etc. etc.
another important thing to know is the fact that the majority of these algorithms are represented through monotonously-increasing functions, which is a very bad thing because it in fact shows that the efficiency drops when the number of items increases. i can't think of any algorithm whose graph is a monotonously-decreasing function, which would be just perfect. because of this limitation, an algorithm that runs in o(1) time is the best.
this is why hash tables are almost ideal when working with huge amounts of data. no mattar how many data items there are, insertion and searching take close to constant time, the perfect o(1)!
___________________
Last edited by Noisician on Jan-10-2004 at 03:05
|
