So, when a key like "Smith" is given, the key would be transformed to the index 180 (S is the 19 letter of the alphabet, so S -> 18, and 18 * 10 = 180). Since we have 260 elements, we can multiply the first letter of the last name by 10. The easiest way to organize the hash table would be based on the first letter of the last name. First, let's create a relationship between letters and numbers: Let's use a 260 element array so that there can be an average of about 10 element spaces per letter of the alphabet. A hash table would be ideal for this sort of thing, so that you canĪccess the records with the people's last names as the keys.įirst, we have to determine the size of the array we're using. Let's say you wanted to organize a list of about 200 addresses by people's That a hashing function has to return the same value every time it is given the Also, one important thing that is sometimes overlooked is Should return a value based on a key and the size of the array the hashing How the hashing function isĪctually coded depends on the situation, but generally the hashing function Hashing FunctionsĪ hashing function can be just about anything. Has to be coded using an indexed array, there has to be some way of Key is used to find an element instead of an index number. One basic form of a keyed array is called the hash table. So, if you have a keyed array of employee records, you could access the record of employee "John Brown" like this: In a keyed array, however, you would be able to associate each element with a "key," which can be anything from a name to a product model number. To find element 50 ofĪn array named "employees" you have to access it like this: To access an element would be through its index number. In a normal C array (also called an indexed array), the only way One of the biggest drawbacks to a language like C is that there are no This article will give you some of the theory behind how a hash table In C++, you can take advantage of the STL map containerįor keyed arrays implemented using binary trees, but Hash tables are an efficient implementation of a keyed array data structure,Ī structure sometimes known as an associative array or map.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |