I don't know why ArrayIndexOutOfBoundsException occur in Separate Chaining

Question

I have a problem implementing Separate Chaining Hash. I made hash function as follows and expected to made hash value that is smaller than M.

private int hash(K key) {
    return (key.hashCode() & 0x7fffffff) & M;   
}

I don't know why I'm getting ArrayIndexOutOfException. When I tried to debug, I entered key for "def" and it's got hash value of 5. However, I configured M size for 5 and try to modular for it. I absolutely don't understand why def's hash value is 5. How can I fix it??

class SeparateChainingHashST<K, V> {
    private int N;
    private int M;
    private SequentialSearchST<K, V>[] st;

    public SeparateChainingHashST() {
        this(5);
    }

    public SeparateChainingHashST(int M) {
        this.M = M;
        st = (SequentialSearchST<K, V>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++)
            st[i] = new SequentialSearchST<>();
    }

    public void insert(K key, V val) {
        int idx = hash(key);
        st[idx].insert(key, val);

    }

    public void delete(K key) {
        st[hash(key)].delete(key);
    }

    public void keys() {
        for (int i = 0; i < M; i++) {
            for (K key : st[i].keys())
                System.out.print(key + " ");
            System.out.println("");
        }
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) & M;
    }
}

public class Main {
    public static void main(String[] args) {
        SeparateChainingHashST<String, Integer> dictionary = new SeparateChainingHashST<>();
        Scanner scan = new Scanner(System.in);

        while (true) {
            System.out.print("Input key and value: ");
            String key = scan.next();
            Integer val = scan.nextInt();
            if (key.equals("quit"))
                break;
            dictionary.insert(key, val);
        }
        dictionary.keys();
    }
}

sequentialSearchST's code:

class Node<K,V> {
    K key;
    V val;
    Node<K,V> next;

    public Node(K key, V val, Node<K,V> next) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}


class SequentialSearchST<K, V> {
    Node<K, V> head;
    int numOfData;

    public void insert(K key, V val) {
        for (Node<K, V> node = head; node != null; node = node.next) {
            if (key.equals(node.key)) {
                node.val = val;
                return;
            }
        }
        head = new Node<>(key, val, head);
        numOfData++;
    }

    public void delete(K key) {
        if (key.equals(head.key)) {
            head = head.next;
            numOfData--;
            return;
        }
        for (Node<K, V> node = head; node.next != null; node = node.next) {
            if (key.equals(node.next.key)) {
                node.next = node.next.next;
                numOfData--;
                return;
            }
        }
    }

    public Iterable<K> keys() {
        ArrayList<K> list = new ArrayList<K>();
        for (Node<K, V> node = head; node != null; node = node.next)
            list.add(node.key);
        return list;
    }

    public V get(K key) {
        if (head == null)
            return null;

        for (Node<K, V> node = head; node != null; node = node.next) {
            if (key.equals(node.key))
                return node.val;
        }
        return null;
    }
}

Answer 1

First mystery: your hash is coming out as 5 because you're doing a bitwise AND.

If you enter key as 'def' then String returns a hash of 99333. In binary, that's

0001 0100 0000 0101

AND that against 5:

0000 0000 0000 0101

And only those columns that both have a 1 will result in a 1:

0000 0000 0000 0101

... which equals 5.

Second mystery, you're not modding against M, you're doing another bitwise AND. You could try changing that last & for a %:

    private int hash(K key) {
        int keyHash = key.hashCode();
        keyHash = (keyHash & 0x7fffffff);
        keyHash = keyHash % M;  // <-- here
        return keyHash;
    }