java - 我不知道为什么 ArrayIndexOutOfBoundsException 出现在单独链接中

Question

我在实现单独链接哈希时遇到问题。 我制作了如下哈希函数，期望生成小于M的哈希值。

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

我不知道为什么会收到 ArrayIndexOutOfException。当我尝试调试时，我输入了“def” key ，它的哈希值为 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的代码:

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;
    }