Separate chaining to resolve collisions

Posted on 2011-10-23
Medium Priority
Last Modified: 2012-05-12
I neew to write a C++ program that inserts N random integers into
a table of size N=100 using separate chaining to resolve collisions, and
then nds and prints the length of the shortest and longest lists for
N = 10 3 (in power of three)
Question by:gudni12345
  • 2
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37015815
Sounds fun. Did you have a question?

Author Comment

ID: 37016588
Sorry!!.The question is how.  I do know how to insert the random numbers in to af table but how to  use separate chaining to resolve collisions, and then find and prints the length of the shortest and longest lists., that is a mistery for me.

LVL 75

Accepted Solution

käµfm³d   👽 earned 1000 total points
ID: 37017641
Hashing algorithms are not my forte, but according to http://www.brpreiss.com/books/opus5/html/page225.html , separate chaining involves creating a linked list, which I assume you've studied prior to this point, for each slot in the hash table and inserting collisions into the linked lists. When you are done with your inserts, printing the length of the longest and shortest would be a matter of iterating over each linked list in the hash table, checking for the shortest and longest lists. It may be simpler to keep two separate variables which track the current longest and shortest lists. In this manner, you wouldn't have to iterate over the whole hash later. This is up to you, though.

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Suggested Courses
Course of the Month17 days, 12 hours left to enroll

831 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