Member Avatar for jwill222
include<iostream>

using namespace std;
int main()
{

int Partnumber[15] = {112,130,156,173,197,150,166,113,123,143,167,189,193,117,176};
int Quantitynumber[15] = {12,30,56,17,19,50,66,13,12,14,16,18,19,11,76};
int hashTable[19][2];
int collisions = 0;
int index = 0;

for(int i = 0; i<15;i++)
{
    index = (Partnumber[i] % 19);
    hashTable[index] = Partnumber[i];

    if (hashTable[index] != 0)
    {
        do{
        index++
    }while(hashTable[index]!=0)
    }
    if(index >= sizeOf(hashTable) )
    {
    index=0;
    }
    else
    {
        hashTable[index] = Partnumber[i];
    }
    }






return 0;

}

First of all I must say that I'm am a newbie to hashing and I have an assignment for class. I'm not going to type the whole problem out but I'm having a problem creating a hashing function and handling collisions. I tried to do linear probing in the above code but I can tell that it won't work. Can somebody tell me a more efficient way of doing this. Here's a link to the problem:

I'm not asking anybody to write this program for me, but i need some direction with this hashing and linear probing algorithm. Thanks :D

Note: I have a two dimensional array to hold the part number along with it's quantity in separate columns

Edit: Also a problem that I'm having is starting back to the beginning of the hashTable if the calculated index is 19. As you can see I'm in desperate need of some help

Edited by jwill222
  • 3 Contributors
  • 3 Replies
  • 642 Views
  • 2 Weeks Discussion Span
  • Latest Post Latest Post by jwill222

Dani AI

Generated

A few concise, practical pointers that make linear probing reliable and easy to reason about.

First, treat each slot as an explicit record (part + quantity + occupied flag) instead of relying on a magic value like 0. Initialize every slot to empty (for example used=false or part=-1). Compute the home index with index = part % TABLE_SIZE, then probe with wrap-around via index = (index + 1) % TABLE_SIZE until you find an empty slot or return to the start (table full). Count a collision each time you probe past an occupied slot. As noted, if the assignment expects statistics about linked-list lengths (average nodes, longest chain) implement chaining (array of lists) instead of open addressing; ’s Knuth reference is a good theory source.

A minimal C++ pattern (keeps part and quantity together, avoids bounds mistakes):

const int TABLE_SIZE = 19;
struct Entry { int part; int qty; bool used; };
Entry table[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; ++i) table[i].used = false;
int collisions = 0;

bool insert(int part, int qty) {
    int idx = part % TABLE_SIZE;
    int start = idx;
    while (table[idx].used) {
        ++collisions;
        idx = (idx + 1) % TABLE_SIZE;
        if (idx == start) return false; // table full
    }
    table[idx].part = part;
    table[idx].qty = qty;
    table[idx].used = true;
    return true;
}

Troubleshooting notes: don’t use sizeof on a pointer or expect 0 to mean empty if 0 can be a valid key; always use modulo for wrap-around; check for a full table to avoid infinite loops; watch load factor — with linear probing performance falls as load approaches ~0.7, so resize/rehash or use chaining if you need higher occupancy. Useful for future readers: the approach above handles the common bugs that appear in the original post and makes collision accounting deterministic (and easy to report).

Recommended Answers

All 3 Replies

Member Avatar for rubberman

See Knuth, Volume 3, Sorting and Searching, Addison-Wesley Pub.

Member Avatar for histrungalot

I tried to do linear probing in the above ...

Looking at the link you gave, it looks like they want you to use link-lists for the collisions because in the section were it talks about

b. when requested, analyze the efficiency of the hashingalgorithm for this set of data. the printout format is
percentage of Prime Area Filled: xx%
Average nodes in linked list: nn
Longest linked list nn

If linked-list above is a link-list and you use linear probing, you would be able to print out these values.

Should you use linear probing?
Member Avatar for jwill222

Thanks guys i got it done

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.