Interview/hash.cpp at master · ravikumarj/Interview · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include "hash.h"
using namespace std;
/*struct list
{
	int val;
	struct list *next;
};

struct Table
{
	int tableSize;
	struct list **table;
};

typedef struct Table Hashtable;*/
Hashtable *init(int tablesize)
{
	Hashtable *ptr;
	int i=0;
	ptr=new Hashtable;
	ptr->table=(struct list **)malloc(sizeof(list *)*tablesize);
	for(i=0;i<tablesize;i++)
	{
		ptr->table[i]=NULL;
	}
	ptr->tableSize=tablesize;
	return ptr;
}

int Hash(Hashtable *hash,int val)
{
	int index=0;
	index=val%hash->tableSize;
	return index;
}
bool lookup(Hashtable *hash,int val)
{
        int index=Hash(hash,val);
        if(hash->table[index] == NULL)
        {
                //      cout<<"\nitem not in Hash table";
                return false;
        }
        else
        {
                struct list *cur=hash->table[index];
                while(cur != NULL)
                {
                        if(cur->val == val)
                        {
                                return true;
                                break;
                        }
                        else
                        {
                                cur=cur->next;
                        }
                }
                return false;

        }

}
//Returns true if element was added in Hash
bool add(Hashtable *hash,int val)
{
	struct list *ptr;
	struct list *newnode=new list;
	newnode->val=val;
	newnode->next=NULL;
	int index=Hash(hash,val);
	if(hash->table[index]==NULL)
	{
		hash->table[index]=newnode;
	}
	else
	{
		if(lookup(hash,val)==false)
		{
			ptr=hash->table[index]; //collision!!
			while(ptr->next!=NULL)
			{
				ptr=ptr->next;
			}
			ptr->next=newnode;
			ptr=ptr->next;
		}
		else
		{
		//cout<<"\nItem already present duplicate";
		return false;
		}
	}
return true;
}
/*main()
{
	Hashtable *hash_ptr;
	int tablesize=10;
	hash_ptr=init(10);
	cout<<"\nHash() --> "<<Hash(hash_ptr,20)<<"\n"<<Hash(hash_ptr,25);
	add(hash_ptr,20);
	add(hash_ptr,25);
	add(hash_ptr,25);
	cout<<"\n"<<lookup(hash_ptr,20);
	cout<<"\n"<<lookup(hash_ptr,21);
	cout<<"\n"<<lookup(hash_ptr,25);

}*/