Modulo-Division Method

Also known as division remainder, the modulo-division method divides the key by array size (table size) and uses the remainder for the address. This method gives us the simple hashing algorithm shown below where tableSize is the number of elements in the array.

address = key MODULUS tableSize

This algorithm works with any table size, but a table size that is a prime number produces fewer collisions than other table sizes. We should therefore try, whenever possible, to make the array size a prime number.

As the little company begins to grow, we realize that soon we will have more than 100 employees. Planning for the future, we create a new employee numbering system that will handle 1,000,000 employees. We also decide that we want to provide data space for up to 300 employees. The first prime number greater than 300 is 307. We therefore choose 307 as out list (array) size, which gives us a table with addresses that range from 0 through 306. Our new employee table and some of its hashed addresses are shown in Figure 6.

To demonstrate, let’s hash Bryan Devaux’s employee number, 121267.

121267/307 = 395 with remainder of 2

Therefore: hash(121267) = 2

Direct Method

In direct hashing, the key is the address without any hashing manipulation. The structure must therefore contain an element for every possible key. The situations in which you can use direct hashing are limited, but it can be very powerful because it guarantees that there are no synonyms. Let’s look at two applications.

Now let’s take an example. Imagine that a small organization has fewer than 100 employees. Each employee is assigned an employee number between 1 and 100. In this case, if we create an array of 101 employee records, the employee number can be directly used as the address of any individual record. This concept is shown in Figure 5.

Note that not every element in the array contains an employee’s record. In fact, all hashing techniques other than direct hashing require that some of the elements be empty to reduce the number of collisions.

Although this is the ideal method, its application is very limited. For example, we cannot have the National Identity Card Number as the key using this method because National Identity Card Number is 13 digits. In other words, if we use the National Identity Card Number as the key, we need an array as large as 1,000,000,000,0000 records but we would use fewer than 100 of them. Let’s turn our attention, then to hashing techniques that map a large population of possible keys into a small address space.

Probing and Probing Sequence

It should be obvious that when we need to locate an element in a hashed list, we must use the same algorithm that we used to insert it into the list. Consequently, we first hash the key and check the home address to determine whether it contains the desired element. If it does, the search is complete. If not, we must use the collision resolution algorithm to determine the next location and continue until we find the element or determine that it is not in the list. Each calculation of an address and test for success is known as a probe. In case of collisions, method of open addressing produces alternate lists of addresses. The process of probing produces a probing sequence which is a sequence of locations that we examine when we attempt to insert a new key into the hashed table, T. The first location in the probe sequence is the hash address, H (K). The second and successful locations in the probe sequence are determined by Collision Resolution Policy. To guarantee availability of always an empty location in every probe sequence, we define a “Full” Table T, to be a table having exactly one empty table entry.

Collisions in Hashing

Generally, the population of keys for a hashed list is greater than the storage area for the data. For example, if we have an array of 50 students for a class in which the students are identified by the last four digits of their National Identity Card Numbers, then there are 200 possible keys for each element in the array (10,000/50).

Because there are many keys for each index location in the array, more than one student may hash to the same location in the array. We call the set of keys that hash to the same location in our list synonyms.

Hash function H (K) are used to map keys into table addresses to store data as table entries (K, I) in hashed table. Almost always we use hashing techniques in which there are many more distinct keys K than there are table addresses, so we encounter a situation in which two distinct keys, K₁ ¹ K₂, map to the same table address, i.e.;

H (K₁) = H (K₂)

Hash Function

The idea of using the key from a large set K of keys to determine the address/location of a record into a smaller set L of table addresses leads to the form of a hash function H. A function that performs this job, such as

H (K) = L

is called a hash function or hashing function. Another way to describe hashing is as a key-to-address transformation in which the keys map to addresses in a list. This mapping transformation is shown in Figure 2. At the top of Figure 2 is a general representation of the hashing concept. The rest of the figure shows how three keys might hash to three different addresses in the list. There are various methods or functions used to map key to addresses, namely Modulo-Division Method, Midsquare Method, and Folding Method etc.

There are few criteria and purposes for hashing of keys. One is that hashing function should be very easy, simple and quick to compute. Second is to map a large possible set of keys to a smaller set of addresses in table. Usually the population of possible keys is much larger than the allocated table size. Thirdly we would like hashed addresses be distributed evenly on the smaller set so that there are a minimum number of collisions. Collision elimination is not guaranteed. Uneven distribution will cause clustering which is not desirable. Fourthly hashing allow direct access to a specific location in the table where the key of the record has been hashed. Its running time efficiency is O(1).

A hash table is a list of records in which keys are mapped by a hash function. It is similar to table, T, described in section 1.0, except here table entries T (K, I) are generated by a appropriate hash functions. A hash table generated by a perfect hash has no collisions. In this case usually all possible keys must be known before hand. This is also known as optimal hashing or perfect hashing.

Hashing Table

A table, T, is an abstract data storage structure that contains table entries that are either empty or are pairs of the form (K, I), where K is a key and I is some data or information associated with the key K.

The identity number is “key”, and name, phone etc are “information” associated with the key.

A common table operation is table searching, which is an activity in which, given a search key, K, we attempt to find the table entry (K, I) in T containing the key K. Then we may wish to retrieve or update its information, I, or we may wish to delete the entire table entry (K, I). We may also wish to insert a new table entry (K, I). We can enumerate entries in table T, e.g. to print contents of the table.

Table can be represented by various data structures like C struct, arrays and linked lists.

LIMITATION OF RECURSION

Recursion works best when the algorithm uses a data structure that naturally supports recursion. For example, Trees are a naturally recursive structure and recursion works well with them. In other cases, the algorithm is naturally suited to recursion. For example, the binary search algorithm lends itself to a natural recursive algorithm. On the other hand, not all looping algorithms can or should be implemented with a recursion.

Recursive solutions may involve extensive overhead because they use calls. When a call is made, it takes time to build a stackframe and push it into the stack. Conversely, when a return is executed, the stackframe must be popped from the stack and the local variables reset to their previous values. Again, this takes time. A recursive algorithm therefore generally runs slower than its nonrecursive implementation.

Each time we make a call we use up some of our memory allocation. If the recursion is deep – that is, if there are many recursive calls – then we may run out of memory. Therefore, the algorithms we have discussed so far (factorial and powers) are better developed iteratively if large numbers are involved. As a general rule, recursive algorithms should be used only when their efficiency is logarithmic.