我不知道为什么ArrayIndexOutOfBoundsException出现在Separate Chaining中

Question

我在实现Separate Chaining Hash时遇到问题。我做了哈希函数如下，并期望使哈希值小于M.

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

我不知道为什么我得到ArrayIndexOutOfException。当我尝试调试时，我输入了“def”的键，它的哈希值为5.但是，我将M大小配置为5并尝试模块化。我绝对不明白为什么def的哈希值是5.如何解决？

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

第一个谜团：你的哈希值是5，因为你正在做一个按位AND。

如果输入key作为'def'，则String返回一个99333的散列。在二进制中，就是

0001 0100 0000 0101

那对5：

0000 0000 0000 0101

只有那些都有1的列才会产生1：

0000 0000 0000 0101

......等于5。

第二个谜，你不是在对抗M，你在做另一个按位AND。您可以尝试更改最后一个＆％：

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