Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 638
  • Last Modified:

HASHING

how do i create a hash index and store say names and addresses in that array. how do i avoid generating the same hash index value for the same name. i have basically worked out how to put together most of the program but i am lost when it comes to this nothing i do seems to work..
0
CODY439
Asked:
CODY439
  • 2
2 Solutions
 
imladrisCommented:
How you create a hash index, and how you (attempt to) avoid generating duplicates depends a great deal on your data.

Given the reference to "avoiding generating the same has index value for the same name", I assume you have names as a key, and addresses as the data. This is then supposed to allow you to, given a name, find the address for that name. You are supposed to do that by getting a hash code for the name, and then retreiving the address at that location.

Hashing schemes can go from simple to elaborate. What you want is to "translate" every name into a position in the array. A simple tactic would be to add up all the letters in the name and use the result as the hashcode. You could get more elaborate by doubling or cubing it and taking the middle digits of the result. The objective is to be as sure as possible that a small change in the name, will result in a change in the hash code.

Note though, that no matter what you do, you usually can't guarantee that all names will come up with unique hash codes. Normally you must take the possibility of "collisions" into account.
0
 
Kent OlsenData Warehouse Architect / DBACommented:


One of the "down sides" to hashing is that the algorithm may well produce collisions (two data items reduce to the same value).  Your program can allow for it in several different ways (or combinations of ways).

Often times, the value that the hash returns is an index.  This index is usually to a buffer (page) where the data is stored.  This buffer (page) is usually large enough to contain several items.  When the buffer (page) is full and the algorithm needs to store another item in the buffer, it must allocate another buffer, called an "overflow block".  A field in the original buffer's header indicates if an overflow block is present.  If enough items hash to the same buffer, the overflow block may also link to another overflow block in a linked-list effect.  Whenever the block is search for a particular item, all overflow blocks must also be searched.


The algorithm that you choose to generate the index is extremely important.  A really bad algorithm might be to return "even or odd", in which case all data will be stored in one of two buffers (and their overflow chains).  Another really bad algorithm is to produce an index so large that no collisions ever occur AND the returned indexed are sparse (not all numbers in the range are returned.)  You'll waste a bunch of space because all of the buffers won't be used.  (Actually, this is used in a few time-critical applications where the amount of data is small and "memory is cheap", but it's not suitable for "general purpose" needs.)


In short, you're going to have to come up with an algorithm that works well for your data, and you're very likely going to have to code overflow blocks.

Kent
0
 
AjarCommented:
Lets  define  a data structure to hold  key ,value pair as

struct hash_node
{
 void * key ;
 void * value ;
 struct hash_node * next
};// a link list node

a hash table will be an array of such hash nodes


struct hash_node * hash_table[10]  ; // array with ten nodes say
// initialize to null nodes

when ever we want to put a new entry into hash table  we
create  a hash_node type of object by malloc e.g

struct hash_node * new_node = (struct hash_node *) malloc(sizeof(struct hash_node));

Then you can attach the key and value like

new_node->key = KEY;
new_node->value = VALUE;


to calculate the position of the new node  in hash_table array

int pos =  ((int)new_node->key)%10

if this position is empty place the new entry there
if this position is not empty then this position will have a hash_node which
is actually a link list so append the new value to its end

thus you can place new items of same hashcode value at the same pos in the array

diagram is

0
|
1-121-191
|
72-3002
|
33-3-93-43
|
NULL
|
345-65
|

with each of these number representing the  (int) ((void *) key)



0
 
imladrisCommented:
Did any of those answers help?

If so, it is now time to select one and grade it to close the question.

If not, perhaps a clarifying question would help.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now