CareerCup

Use two data structures
1. An array of size N, with index nextEmpty, which indicates where the next element should be added.
2. A hashmap with key as the number itself and value as the index of that number in the array.
For add operation - Just add the number at nextEmpty location, update hashmap and do nextEmpty++.
For remove operation - Get the index of the number from hashmap, remove it from hashmap. Then swap last element in the array(nextEmpty-1) with that element. Update the hashmap and do nextEmpty--
Both operations will be O(1)

<Programming Pearls> has the answer:

two array: from[], to[] (from[to[i]] == i).
initial:
top = 0;
push one element:
to[top] = data; from[data]=top++;
check data:
to[from[data]] == data

In your solution, how are you implementing the constraint of HashSet size being 'M'?

by a size variable...
if no elements are added then size=0.
gradually on adding elements size will increase and finally it will become M.
When size will be M then no more elements can be added.

obviously things will be reverse for deleting elements from hashset.

You could use an array of linked lists of size M. The hashing function could be (val % M). Every time you have to insert a no., you pass it through the hashing function to get the index where the no. would be inserted.
If there isn't any linked list at that index, you will have to create a node. And then that index would have to point to that node. Thus in this you don't need any initialization in the beginning.

1. Create an array of size M.
2. Since N>M, collisions may occur. Use a linked List for collision(most common).
3. Find element using key(or value, if key is the value) and hashcode.

that way takes O(n) space and n is very large. implement a hash function for size m if collision occurs maintain a list

maybe BST, each node in BST is a linked list?
However, this solution will increase the complexity of the algo