# CS210 Lab: Hash Table Postlab Answers

Part 1

For the following two questions, use the following values:

```   67 46 88 91 123 141 152 155 178 288 390 399 465 572 621 734
```
1. Draw a diagram to show how the values are inserted into a hash table with 20 positions. Use the division method of hashing and the linear probing method of resolving collisions.

Step 1: Apply the Division Method to Get the Index
67 % 20 = 7
46 % 20 = 6
88 % 20 = 8
91 % 20 = 11
. . .
734 % 20 = 14

Step 2: Create Table Using Linear Probing Method 2. Draw a diagram to show how the values are inserted into a hash table that uses the hash function key % 10 to determine into which of ten chains to put the value.

Step 1: Apply the Division Method to Get the Index
67 % 10 = 7
46 % 10 = 6
88 % 10 = 8
91 % 10 = 1
. . .
734 % 10 = 4

Step 2: Create Table Using Chaining Method Part 2

This question is based on the lab exercise that you have just completed.

1. When implementing programs that take passwords, you might want to hide the user input, or display stars instead. You can do this using a couple of functions:
• getch()--to get a character from the console without echo. (#include <conio.h>)
• You may have to use type casting or type conversio n to change the integer return from getch() into a character.
• The following format should work:
(char)getch() or char(getch()) .

• putchar('*')--to echo stars. (#include <stdio.h>)

Look these up using "Help" and try to modify your code so that you program will run something like the following:

```Login: mary
Authentication successful
```
```
#include <stdio.h>
#include <conio.h>
#define MAXPASSCHAR 15  //maximum password length

// prototypes
char *getpasswd(void);
.
.
.
//replace two commented lines with the following
// cout << "Password: ";
// cin >> pass;
pass=getpasswd();
.
.
.
//define the following function at the end
char *getpasswd(void)
{
char temp;
static char buf[MAXPASSCHAR+1]; //use static so that you can access data in buf from main
bool inputdone;
unsigned int i;

inputdone=false;
i = 0;

buf[i]='\0';  //initialize buff incase empty password

do
{
//temp = (char)_getche();  //with echo
temp = (char)_getch();

if (temp=='\b') //backspace character
{
putchar('\b');
i--;
}
else if(temp != '\r') //carriage return
{
putchar('*');
buf[i++] = temp;
}
else
{
inputdone = true;
putchar(temp);
buf[i]='\0';
}

}while(!inputdone & (i<MAXPASSCHAR));

// if user inputted all MAXPASSCHAR characters, then
// we need to put in an end of string for the
// printf following
if(i == MAXPASSCHAR)
buf[i]='\0';

// this is just to see if it was inputted ok
printf("\nPassword was %s\n", buf);

return buf;
}
``` Copyright: Department of Computer Science, University of Regina.