Purchase Solution

Division method for a hash function

Not what you're looking for?

Ask Custom Question

Please review the problem and explain each step of the solution listed below, and give me an example of an application which this property would be undesirable in a hash function.

problem
----------
Consider a version of the division method in which h(k) = k mod m, where m = (2^p) -1 and k is a character string interpreted in radix 2^p. Show that if a string x can be derived from string y by permuting its characters, then x and y hash to the same value. <B>Give an example of an application in which this property would be undesirable in a hash function.</B>

solution
---------
All permutations can be generated by a sequence of two character interchanges. If two arbitrary characters, i and j, are switched, then the values hash to the same place.

We consider two numbers x and y which have characters i and j interchanged, and i > j.

Note: in this solution xi = x sub i and xj = x sub j (same goes for y).
x - y = (xi - yi)(m + 1)^(i-1) + (xj - yj)(m+1)^(j-1)
= (xi - xj)(m + 1)^(i-1) - (xi - xj)(m+1)^(j-1)
= (xi - xj)[(m + 1)^(i-1) - (m + 1)^(j-1) ]
= (xi - xj)(m + 1)^(j-1) * [(m + 1)^(i-j) -1]
= (xi - xj)(m + 1)^(j-1) * [(m + 1) - 1] * Summation of (m + 1)^k [from k = 0 to i - j - 1]

= 0 mod m

Purchase this Solution
Solution Summary

Division method for a hash function is examined.

Purchase this Solution
Free BrainMass Quizzes
Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

C# variables and classes

This quiz contains questions about C# classes and variables.

Javscript Basics

Quiz on basics of javascript programming language.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

View More Free Quizzes
Related BrainMass Solutions

  • Hash Division Function Numbers

    The division function for hash tables divides the data value by the number of buckets, and the *remainder* is used for the bucket number.

  • C++: Hash function object type (hFint256)

    Consider the hash function object type Class hFint256 { Public: unsigned int operator() (int item) const { Return (item/16 % 256); } }; (a) What is the size of the hash table?

  • Client-Server system and password protection by hashing

    Lets try to build a simple hash function for a string values: Hash function for string values - if we convert the characters of the string into integer values, by assigning 1 to a and 26 to z (small letters), 27 to A and 52 to Z (capital letters

  • Understanding a bad hash function

    270171 Understanding a bad hash function 12.16 Consider the given hashing function object for strings. What can you say about strings "aefghk" and "gaefkh"? Is this a good hashing function? Why?

  • Hush table

    Exercise 12.13 Assume that a hash function has the following characteristics: Keys 257 and 567 hash to 3. Keys 987 and 313 hash to 6. Keys 734, 189, and 575 hash to 5. Keys 122, 391 hash to 8.

  • Country names parser and simple hash table in C++

    Write a C++ program that includes a suitable hashing function and hash table to store this list of countries into your hash table.

  • Cryptography and Information Security Problem

    For a message, he calculates the hash value H = (VChar 1 x VChar 2 x VChar 3 ...x VChar N) mod(26). Bob uses this function to send a one-word message, PANEL, to his banker Bill, along with his calculated hash value for the message.

  • Hashed file design

    94648 Design a hashed file Design a hashed file of words that could be used as a spell checker. What would you use as a hash function? Would your choice of a hash function depend on the language from which the words are chosen?

  • Compare the Two Non-Sequential File Structure Models

    The weakness comes from the limitation of having only one hash value for a record. If you need to order the list by employee number, last name, and first name, you've got quite a problem.

View More Related Solutions