Search by hashing techniques 1) Hashing with linear probing 2) (bonus) Hashing w
ID: 659662 • Letter: S
Question
Search by hashing techniques
1) Hashing with linear probing
2) (bonus) Hashing with quadratic probing
3) (bonus) Hashing with chaining
Choose your hash function and hash table size that suits your test data such that collision code can be verified.
As an example, if I'm searching just 6 integers, I may have a table of 11 entries and a hashing function of "fold digits mod 11". By mindfully choosing the test data, I would be able to know if my collision algorithm and search algorithm works.
You should write the insertion routine to "add" items into the hash table. It will make it easier to create your database.
Try to do a delete routine too. There are additional considerations to be exercised.
Explanation / Answer
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ofstream out_stream;
search as,asr,bs,bsr,ll,llr ;
int i , num;
out_stream.open("output.txt");
do
{
out_stream << " Preloaded list of numbers array and linked list" << endl;
out_stream << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout << " Preloaded list of numbers array and linked list" << endl;
cout << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout<<" Choose type of search:";
cout<<" 1. Arrays: Sequential Search without recursion";
cout<<" 2. Arrays: Sequential Search with recursion";
cout<<" 3. Ordered Arrays: Binary Search without recursion";
cout<<" 4. ordered Arrays: Binary Search with recursion";
cout<<" 5. Linked List: Search with recursion";
cout<<" 6. Linked List: Search without recursion";
cout<<" Enter 0 exit ";
out_stream<<" Choose type of search:";
out_stream<<" 1. Arrays: Sequential Search without recursion";
out_stream<<" 2. Arrays: Sequential Search with recursion";
out_stream<<" 3. Ordered Arrays: Binary Search without recursion";
out_stream<<" 4. ordered Arrays: Binary Search with recursion";
out_stream<<" 5. Linked List: Search with recursion";
out_stream<<" 6. Linked List: Search without recursion";
out_stream<<" Enter 0 exit ";
cin>>i;
cout <<"Picked # " << i << " ";
out_stream << "Picked # " << i << " ";
switch(i){
case 1: as.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: ";
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(as.seqsearch(num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
as.cleararray();
break;
case 2: asr.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(asr.seqserachRecursion(0,num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
asr.cleararray();
break;
case 3: bs.load();
bs.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bs.orderedbinarysearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bs.cleararray();
break;
case 4: bsr.load();
bsr.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bsr.orderedbinarysearchRecursion(num,0,11)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bsr.cleararray();
break;
case 5: ll.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(ll.linkedsearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
ll.clearlist();
break;
case 6: llr.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(llr.linkedsearchRecursion(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
llr.clearlist();
break;
}
}while(i!=0);
out_stream.close();
}
#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <chrono>
using namespace std;
search::search(){
}
bool search::seqsearch(int num){
for(unsigned int i=0; i < array.size();i++){
if(array[i] == num){
return true;
}
}
return false;
}
bool search::seqserachRecursion(unsigned int start, int num){
if(start == array.size()){ //base case
return false;
}
if(array[start] == num){
return true;
}else{
seqserachRecursion(start+1, num);
}
}
bool search::orderedbinarysearch(int num){
int max = array.size();
int min = 0;
while(max>=min){
int mid = (max+min)/2;
if(array[mid] == num){
return true;
}
else if(array[mid]< num){// upper
min = mid+1;
}else{ // lower
max = mid-1;
}
}
return false;
}
bool search::orderedbinarysearchRecursion(int num, int min, int max){
if(max < min){
return false;
}else{
int mid = (min+max)/2;
if(array[mid]> num){
orderedbinarysearchRecursion(num,min,mid-1);
}
else if(array[mid]<num){
orderedbinarysearchRecursion(num,mid+1,max);
}
else{
return true;
}
}
}
bool search::linkedsearch(int num){
while(!nodes.empty()){
if(num == nodes.front()){
return true;
}else{
nodes.pop_front();
}
}
return false;
}
bool search::linkedsearchRecursion(int num){
if(nodes.empty()){
return false;
}
else if(nodes.front() == num){
return true;
}
else{
nodes.pop_front();
linkedsearchRecursion(num);
}
}
void search::load()
{
array.push_back(41);
array.push_back(67);
array.push_back(34);
array.push_back(0);
array.push_back(69);
array.push_back(24);
array.push_back(78);
array.push_back(58);
array.push_back(62);
array.push_back(64);
}
void search::orderloaded(){ // smallest to largest
for(unsigned int i=0; i<array.size(); i++){
for(unsigned int j=0; j< array.size()-1;j++){
if(array[j]> array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
void search::loadlinked()
{
nodes.push_back(41);
nodes.push_back(67);
nodes.push_back(34);
nodes.push_back(0);
nodes.push_back(69);
nodes.push_back(24);
nodes.push_back(78);
nodes.push_back(58);
nodes.push_back(62);
nodes.push_back(64);
}
void search::cleararray(){
while(!array.empty()){
array.pop_back();
}
}
void search::clearlist(){
while(!nodes.empty()){
nodes.pop_front();
}
}
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class search{
public:
search();
bool seqsearch(int num);
bool seqserachRecursion(unsigned int start, int num);
bool orderedbinarysearch(int num);
bool orderedbinarysearchRecursion(int num, int min, int max);
bool linkedsearch(int num);
bool linkedsearchRecursion(int num);
void load();
void orderloaded();
void loadlinked();
void cleararray();
void clearlist();
private:
vector<int> array;
list <int> nodes;
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.