2020. 2. 18. 18:28ㆍ카테고리 없음
Hash TablesBy Eric SuhHash tables are an efficient implementation of a keyed array data structure,a structure sometimes known as an associative array or map. If you're workingin C, you can take advantage of thefor keyed arrays implemented using, butthis article will give you some of the theory behind how a hash tableworks.
Keyed Arrays vs. Indexed ArraysOne of the biggest drawbacks to a language like C is that there are nokeyed arrays. In a normal C array (also called an indexed array), the only wayto access an element would be through its index number. To find element 50 ofan array named 'employees' you have to access it like this:employees50;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. So, if you have a keyed array of employee records, you could access the record of employee 'John Brown' like this:employees'Brown, John';One basic form of a keyed array is called the hash table.
In a hash table, akey is used to find an element instead of an index number. Since the hash tablehas to be coded using an indexed array, there has to be some way oftransforming a key to an index number. That way is called the hashing function. Hashing FunctionsA hashing function can be just about anything. How the hashing function isactually coded depends on the situation, but generally the hashing functionshould return a value based on a key and the size of the array the hashingtable is built on. Also, one important thing that is sometimes overlooked isthat a hashing function has to return the same value every time it is given thesame key.Let's say you wanted to organize a list of about 200 addresses by people'slast names.
A hash table would be ideal for this sort of thing, so that you canaccess the records with the people's last names as the keys.First, we have to determine the size of the array we're using. Let's use a 260 element array so that there can be an average of about 10 element spaces per letter of the alphabet.Now, we have to make a hashing function. First, let's create a relationship between letters and numbers:A - 0B - 1C - 2D - 3.and so on until Z - 25.The easiest way to organize the hash table would be based on the first letter of the last name.Since we have 260 elements, we can multiply the first letter of the last name by 10. 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 use a simple function to generate an index number quickly, and we use the fact that the index number can be used to access an element directly, a hash table's access time is quite small. A of keys and elements wouldn't be nearly as fast, since you would have to search through every single key-element pair.
Collisions and Collision HandlingProblems, of course, arise when we have last names with the same first letter. So 'Webster' and 'Whitney' would correspond to the same index number, 22. A situation like this when two keys get sent to the same location in the array is called a collision. If you're trying to insert an element, you might find that the space is already filled by a different one.Of course, you might try to just make a huge array and thus make it almost impossible for collisions to happen, but then that defeats the purpose of using a hash table.
One of the advantages of the hash table is that it is both fast and small. Collision handling with open addressingThe simplest collision handling algorithm is known as the open address method or the closed hashing method. When you are adding an element, say 'Whitney,' and you find that another element is already there ('Webster,' for instance) then you would just proceed to the next element space (the one after 'Webster'). If that is filled, you go on to the next one, and so on, until you find an empty space to insert the new element (all those extra elements came in handy after all!).220 'White'.
HashingIn previous sections we were able to make improvements in our searchalgorithms by taking advantage of information about where items arestored in the collection with respect to one another. For example, byknowing that a list was ordered, we could search in logarithmic timeusing a binary search. In this section we will attempt to go one stepfurther by building a data structure that can be searched in(O(1)) time. This concept is referred to as hashing.In order to do this, we will need to know even more about where theitems might be when we go to look for them in the collection.
If everyitem is where it should be, then the search can use a single comparisonto discover the presence of an item. We will see, however, that this istypically not the case.A hash table is a collection of items which are stored in such a wayas to make it easy to find them later. Each position of the hash table,often called a slot, can hold an item and is named by an integervalue starting at 0. For example, we will have a slot named 0, a slotnamed 1, a slot named 2, and so on.
Initially, the hash table containsno items so every slot is empty. We can implement a hash table by usinga list with each element initialized to the special Python valueNone. Shows a hash table of size (m=11).In other words, there are m slots in the table, named 0 through 10. Figure 5: Hash Table with Six ItemsNow when we want to search for an item, we simply use the hash functionto compute the slot name for the item and then check the hash table tosee if it is present. This searching operation is (O(1)), sincea constant amount of time is required to compute the hash value and thenindex the hash table at that location.
If everything is where it shouldbe, we have found a constant time search algorithm.You can probably already see that this technique is going to work onlyif each item maps to a unique location in the hash table. For example,if the item 44 had been the next item in our collection, it would have ahash value of 0 ( (44% 11 0)). Since 77 also had a hashvalue of 0, we would have a problem.
According to the hash function, twoor more items would need to be in the same slot. This is referred to asa collision (it may also be called a “clash”). Clearly, collisionscreate a problem for the hashing technique. We will discuss them indetail later. Figure 7: Hashing a String Using Ordinal Values with WeightingYou may be able to think of a number of additional ways to compute hashvalues for items in a collection.
The important thing to remember isthat the hash function has to be efficient so that it does not becomethe dominant part of the storage and search process. If the hashfunction is too complex, then it becomes more work to compute the slotname than it would be to simply do a basic sequential or binary searchas described earlier. This would quickly defeat the purpose of hashing.
Collision ResolutionWe now return to the problem of collisions. When two items hash to thesame slot, we must have a systematic method for placing the second itemin the hash table. This process is called collision resolution.
Aswe stated earlier, if the hash function is perfect, collisions willnever occur. However, since this is often not possible, collisionresolution becomes a very important part of hashing.One method for resolving collisions looks into the hash table and triesto find another open slot to hold the item that caused the collision. Asimple way to do this is to start at the original hash value positionand then move in a sequential manner through the slots until weencounter the first slot that is empty.
Note that we may need to go backto the first slot (circularly) to cover the entire hash table. Thiscollision resolution process is referred to as open addressing inthat it tries to find the next open slot or address in the hash table.By systematically visiting each slot one at a time, we are performing anopen addressing technique called linear probing.shows an extended set of integer items under thesimple remainder method hash function (54,26,93,17,77,31,44,55,20).above shows the hash values for the original items.shows the original contents. When we attempt toplace 44 into slot 0, a collision occurs. Under linear probing, we looksequentially, slot by slot, until we find an open position. In thiscase, we find slot 1.Again, 55 should go in slot 0 but must be placed in slot 2 since it isthe next open position.
The final value of 20 hashes to slot 9. Sinceslot 9 is full, we begin to do linear probing. We visit slots 10, 0, 1,and 2, and finally find an empty slot at position 3. Figure 8: Collision Resolution with Linear ProbingOnce we have built a hash table using open addressing and linearprobing, it is essential that we utilize the same methods to search foritems. Assume we want to look up the item 93. When we compute the hashvalue, we get 5. Looking in slot 5 reveals 93, and we can returnTrue.
C Program To Implement Dictionary Using Hashing Functions In Excel
What if we are looking for 20? Now the hash value is 9, andslot 9 is currently holding 31. We cannot simply return False sincewe know that there could have been collisions. We are now forced to do asequential search, starting at position 10, looking until either we findthe item 20 or we find an empty slot.A disadvantage to linear probing is the tendency for clustering;items become clustered in the table.
This means that if many collisionsoccur at the same hash value, a number of surrounding slots will befilled by the linear probing resolution. This will have an impact onother items that are being inserted, as we saw when we tried to add theitem 20 above. A cluster of values hashing to 0 had to be skipped tofinally find an open position. This cluster is shown in. Figure 9: A Cluster of Items for Slot 0One way to deal with clustering is to extend the linear probingtechnique so that instead of looking sequentially for the next openslot, we skip slots, thereby more evenly distributing the items thathave caused collisions.
This will potentially reduce the clustering thatoccurs. Shows the items when collisionresolution is done with a “plus 3” probe.
This means that once acollision occurs, we will look at every third slot until we find onethat is empty. Figure 10: Collision Resolution Using “Plus 3”The general name for this process of looking for another slot after acollision is rehashing. With simple linear probing, the rehashfunction is (newhashvalue = rehash(oldhashvalue)) where(rehash(pos) = (pos + 1)% sizeoftable). The “plus 3” rehashcan be defined as (rehash(pos) = (pos+3)% sizeoftable). Ingeneral, (rehash(pos) = (pos + skip)% sizeoftable). It isimportant to note that the size of the “skip” must be such that all theslots in the table will eventually be visited. Otherwise, part of thetable will be unused.
To ensure this, it is often suggested that thetable size be a prime number. This is the reason we have been using 11in our examples.A variation of the linear probing idea is called quadratic probing.Instead of using a constant “skip” value, we use a rehash function thatincrements the hash value by 1, 3, 5, 7, 9, and so on. This means thatif the first hash value is h, the successive values are (h+1),(h+4), (h+9), (h+16), and so on. In other words,quadratic probing uses a skip consisting of successive perfect squares.shows our example values after they are placed usingthis technique.
Figure 11: Collision Resolution with Quadratic ProbingAn alternative method for handling the collision problem is to alloweach slot to hold a reference to a collection (or chain) of items.Chaining allows many items to exist at the same location in the hashtable. When collisions happen, the item is still placed in the properslot of the hash table. As more and more items hash to the samelocation, the difficulty of searching for the item in the collectionincreases.
Shows the items as they are added to a hashtable that uses chaining to resolve collisions. Q-2: Suppose you are given the following set of keys to insert into a hash table that holds exactly 11 values: 113, 117, 97, 100, 114, 108, 116, 105, 99 Which of the following best demonstrates the contents of the hash table after all the keys have been inserted using linear probing?. 100, , , 113, 114, 105, 116, 117, 97, 108, 99. It looks like you may have been doing modulo 2 arithmentic. You need to use the hash table size as the modulo value. 99, 100, , 113, 114, , 116, 117, 105, 97, 108.
Using modulo 11 arithmetic and linear probing gives these values. 100, 113, 117, 97, 14, 108, 116, 105, 99, ,. It looks like you are using modulo 10 arithmetic, use the table size. 117, 114, 108, 116, 105, 99, , , 97, 100, 113. Be careful to use modulo not integer division.
Implementing the Map Abstract Data TypeOne of the most useful Python collections is the dictionary. Recall thata dictionary is an associative data type where you can store key–datapairs.
The key is used to look up the associated data value. We oftenrefer to this idea as a map.The map abstract data type is defined as follows. The structure is anunordered collection of associations between a key and a data value. Thekeys in a map are all unique so that there is a one-to-one relationshipbetween a key and a value. The operations are given below.Map Create a new, empty map. It returns an empty mapcollection.put(key,val) Add a new key-value pair to the map.
If the key isalready in the map then replace the old value with the new value.get(key) Given a key, return the value stored in the map orNone otherwise.del Delete the key-value pair from the map using a statement ofthe form del mapkey.len Return the number of key-value pairs stored in the map.in Return True for a statement of the form key in map, ifthe given key is in the map, False otherwise.One of the great benefits of a dictionary is the fact that given a key,we can look up the associated data value very quickly. In order toprovide this fast look up capability, we need an implementation thatsupports an efficient search. We could use a list with sequential orbinary search but it would be even better to use a hash table asdescribed above since looking up an item in a hash table can approach(O(1)) performance.In we use two lists to create aHashTable class that implements the Map abstract data type. Onelist, called slots, will hold the key items and a parallel list,called data, will hold the data values. When we look up a key, thecorresponding position in the data list will hold the associated datavalue. We will treat the key list as a hash table using the ideaspresented earlier. Note that the initial size for the hash table hasbeen chosen to be 11.
Although this is arbitrary, it is important thatthe size be a prime number so that the collision resolution algorithmcan be as efficient as possible.Listing 2. Class HashTable: def init ( self ): self. Size = 11 self. Slots = None. self.
Data = None. self. Sizehashfunction implements the simple remainder method. The collisionresolution technique is linear probing with a “plus 1” rehash function.The put function (see ) assumes thatthere will eventually be an empty slot unless the key is already presentin the self.slots. It computes the original hash value and if thatslot is not empty, iterates the rehash function until an empty slotoccurs.
If a nonempty slot already contains the key, the old data valueis replaced with the new data value. Dealing with the situation where there areno empty slots left is an exercise.Listing 3. Def put ( self, key, data ): hashvalue = self. Hashfunction ( key, len ( self.
Slots )) if self. Slots hashvalue None: self. Slots hashvalue = key self. Data hashvalue = data else: if self. Slots hashvalue key: self.
Data hashvalue = data #replace else: nextslot = self. Rehash ( hashvalue, len ( self.
Slots )) while self. Slots nextslot != None and self. Slots nextslot != key: nextslot = self. Rehash ( nextslot, len ( self.
Slots )) if self. Slots nextslot None: self. Slots nextslot = key self.
Data nextslot = data else: self. Data nextslot = data #replace def hashfunction ( self, key, size ): return key% size def rehash ( self, oldhash, size ): return ( oldhash + 1 )% sizeLikewise, the get function (see )begins by computing the initial hash value.
If the value is not in theinitial slot, rehash is used to locate the next possible position.Notice that line 15 guarantees that the search will terminate bychecking to make sure that we have not returned to the initial slot. Ifthat happens, we have exhausted all possible slots and the item must notbe present.The final methods of the HashTable class provide additionaldictionary functionality. We overload the getitem andsetitem methods to allow access using````. This means thatonce a HashTable has been created, the familiar index operator willbe available.
We leave the remaining methods as exercises.Listing 4. Def get ( self, key ): startslot = self.
Hashfunction ( key, len ( self. Slots )) data = None stop = False found = False position = startslot while self. Slots position != None and not found and not stop: if self. Slots position key: found = True data = self. Data position else: position = self.
Rehash ( position, len ( self. Slots )) if position startslot: stop = True return data def getitem ( self, key ): return self.
Get ( key ) def setitem ( self, key, data ): self. Put ( key, data )The following session shows the HashTable class in action.
First wewill create a hash table and store some items with integer keys andstring data values.