Java hashcode without using the Object#hashCode method
Use meaningful names for your fields:

private int N;
private int M;


What do those fields hold? What is the purpose of them?
Ask yourself those questions and use names that represent the meaning of your field:

private int size;
private int capacity;


Don't cast where you don't need to:

keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];


This makes no sense; why do you cast a generic Object[] array to a Key[]/Value[] array?
Simply create them without casting:

keys = new Key[M];
vals = new Value[M];


Your hashing methods don't return hashes

Your code is entirely broken in that regard. They only work for Strings and you use them for getting your index. This is not how hashing works!
I don't know if this is a restriction of your assignment, but no matter how large the capacity of your table is, your hashing method should always return the same value in order to be comparable to other objects.