Solved

Hash tables

Posted on 2000-03-27
5
283 Views
Last Modified: 2010-04-02
Hi. I'm trying to implement the following hash functions.
1. h(x)= 1 + (x/k) * M
2. h(x)= 1 + x mod M
3. h(x)=1 + @x mod M

Where M is the table size. They should change keys into integers in the range from 1 to M. I'm using this to generate the numbers and send them to the hash function:

#include<iostream.h>
#include<stdlib.h>
main()
{
 int tablesize=32;
 int a[200];
 for(int i=0;i<200;i++)
 {
      i=rand()%5001;
        h(x)=hash(tablesize,i)
   }
 return 0;
}

1. How do I make the hash function?
2. Can hashing be used with text? Can you provide some examples?
Thanx
0
Comment
Question by:q_low
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 
LVL 10

Expert Comment

by:RONSLOW
ID: 2662927
something like this would probably do...

int hash1(int M, int x) { return 1 + (x / k) * M; }
int hash2(int M, int x) { return 1 + x % m; }
int hash3(int M, int x) { return 1 + ???x % m; }
// whatever @x means
// don't know what you're talking about there
// you'll have to code that yourself

static int method = 1;

int hash(int M, int x) {
  switch (method) {
  case 1: return hash1(M,x);
  case 2: return hash1(M,x);
  case 3: return hash1(M,x);
  }
  return 0; // not a valid hash method
}

You can then set method to be 1, 2 or 3 as required.

And I think you want you code to say
  int x;
  for(int i=0;i<200;i++) {
    x=rand()%5001;
    a[x]=hash(tablesize,x);
  }
And then print out (or do something with) the hash values rather than just end the program.

To use with text, you usually loop for each each character, hash it and combine with the overall running hash value (eg add, or shift and add or whatever).  There are lots of examples around of hashing.

0
 

Author Comment

by:q_low
ID: 2663948
in the first equation k will be the key.
what does the key means if i have a table of size 32?
0
 

Author Comment

by:q_low
ID: 2667660
....
0
 
LVL 10

Accepted Solution

by:
RONSLOW earned 50 total points
ID: 2672700
the way you have shown the code, x is the key.  k being the key doesn't make sense .. because then what is x and where does k come from.

if your table size is 32, then .. well, your table size is 32.  Don't think it means anything in particular.

I think I answred you question satisfactorily.

0
 

Author Comment

by:q_low
ID: 2692064
thanx
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Create string splitting user defined function in C++ 23 356
mixing C++ & C# in Vis Studio 2013 7 283
VS2015 compilation and missing DLLs 9 193
DCT of  2D array using fftw in c++ 9 137
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question