C Programming function on hash tables to get all tuples

Question

// Traverse the hash table pointed to by "ht" and store

// all the key-value tuples encountered in the hash table in the

// array "tuples". The capacity of the array "tuples" is "max".

// Thus, the function should not store more than "max" entries

// in "tuples".

//

// Return the actual number of key-value tuples

// written to "tuples".

int htable_get_all_tuples(htable_t *ht, kv_t *tuples, int max)

{

 //TODO: Your code here

}

Answer 1

Hi Kathy

I have uploaded some source code for you.

The filename is Hash.c and is in the RESOURCES

section under this link.

The Hash Abstract Data Type (ADT) requires at least

FOUR (4) items, which are neither specified nor

clearly defined in your posting.

(1) the Hash Table, An Array containing data or list of data items

stored in a particular order according to a

KEY value, which you have stated

Typically the array is thought of as a set of BINS or BUCKETS;

each of which contains the data that belongs inside that particular section.

(2) a Hash FUNCTION that returns the data in the array

BASED on the key value

(3) the values of the KEY MUST BE UNIQUE

(4) there must be some mechanism for inputting

the key and passing it into the function, along

with the dimensions of the hash table

There could be multiple values in the hash table associated

with one key, which is called "one-to-many" relationship

These four items are kept TOGETHER typically in a single data

structure.

In your posting, there is no description about the types of

data stored in the table and how it is to be organized. So

item #1 is violated.

Items 2 and 4 are violated because there is no function that

relates the key to it's data members. There is only one function

htable_get_all_tuples() that takes a pointer to the hash table

and a pointer to the array vector that contains the results.

There is no clear connection between the data in the hash table

to the key. In fact, there is no hash function at all and

no data specifications either.

Finally the verbiage is slightly confusing. Returning ALL of the

data items in the hash table will certainly exceed the limit of

your max capacity that you are passing to your function.

=====================================================

Here is what I have given...

The code demonstrates TWO Hash ADTs.

#1)

The first is a hash table that stores the FREQUENCIES of

the numbers 0-99 as they occur.

The hash table is simply an array with with bins 0,1,2,3....9

bin #0 stores the frequencies of the numbers 0,1,2,3,..9

bin #1 stores the frequencies of the numbers in the teens:10,11,12,....,19

bin #2 stores the frequencies of the numbers in the 20s: 20,21,22,....,29

bin #3 stores the frequencies of the numbers in the 30s: 30,31,32,....,39

etc etc etc

bin #9 stores the frequencies of the numbers in the 90s: 90,91,92,...99

So in essence, the bin# is the ten's place. It is basically just

a STEM and LEAF plot, stored in an array.

The hash function determines which BIN# it belongs by dividing by 10.

The frequency of that number is updated by accessing it's address

via the mod operator %

For example 56 belongs in bin #5 because 56/10 = 5.

The frequency is increased by 1 at position index of 56%10 = 6

Random numbers are generated and put into the hash table..

Finally, in a for-loop from 0 to 99, the program reports the frequencies of

each as they occurred in the random number generation.

The can be verified by the debugging statements stating what is the integer

being put into the hash table and the bin# and index of exactly where.

==========================================================================

#2)

There are TWO hash tables. The first contains an array of city names.

Each city can have up to 5 names, including but not limited to UPPERCASE,

lowercase, and a "nickname"

Ex. New York, NYC, the big apple

Admittedly, some records are actually STATES, not cities, but the reason shall

soon become apparent.

The second hash table contains a list of the names professional sports teams

belonging to each of the cities, from the sports of football, baseball,

basketball, hockey , and even the prominent colleges.

TWO hash functions map the array index to the city names and their

respective professional sports teams.

You are then asked to input the city # and the city name(s) and their sports teams

are output

========================================================================================

Finally per item #3, which has not been discussed extensively until now,

states the key must be UNIQUE...

Two sets of tuples CANNOT have the same key..

For that reason, the key value is best chosen to be a NUMBER rather

than a string.

Databases in fact use what is called a RECORD NUMBER as a PRIMARY key

which gets incremented every time a new record is added to the table.

This GUARANTEES the primary key is unique.

Other types of primary keys that are found in databases include

but are not limited to, emails, account #, social security #, case #, order #, student id #,

and license #

Notice a pattern.....they're all NUMBERS;

Even the email addresses are unique because they are associated with an IP Address

which is just more numbers.

Compile the code, run it a few times examining and reading the output.

Study, peruse, and digest the code so you FULLY understand what is going

on. ASK QUESTIONS!!!

Hopefully you have a better understanding of the Hash ADT.