Java 哈希表原理与实现

**开散列：**开散列法又叫链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

这里主要用的是通过**开散列 (哈希桶)**来解决冲突。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

哈希桶的实现

从上图哈希桶图所示，我们可以把它看成是数组 + 链表的形式，这样我们就可以定义相关变量了。

// 定义相关变量
static class Node {
    public int val;
    public int key;
    public Node next;
    
    public Node(int val, int key) {
        this.val = val;
        this.key = key;
    }
}

插入数据

插入数据的第一步是要在数组中找到它所在的位置，然后进行链表的插入，头插法。

public void push(int key, int val){
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null){
        if(cur.key == key){
            cur.val = val;
            return;
        }
        cur = cur.next;
    }
    //没有找到当前链表中有这个 key 的节点
    //头插法
    Node node = new Node(val, key);
    node.next = array[index];
    array[index] = node;
    useSize++;
    if(doLoadFactor() >= DEFAULT_LOAD_FACTOR){
        //扩容
        resize();
    }
}

不过，这里有个重点，要注意负载因子，计算负载因子。

以代码的数据为例，如果数组中的所放数据个数大于 7，那么就会有很大概率产生冲突，这时我们要解决冲突，就要对哈希表进行扩容。这里并不是简单地把数组扩大两倍，在扩大后还要把前面整个数组的数据遍历一遍，然后再次进行对应位置的存储。

像是没扩容之前，array[4] 中可能放着 4 和 14 两个数据，现在数组长度从 10 扩容到 20，那么 4 还应该放在 array[4] 里面，而 14 应该放在 array[14] 里面。

故要包括扩容以及再次哈希来进行。

resize 方法

public void resize(){
    Node[] newArray = new Node[2*array.length];
    for (int i = 0; i < array.length; i++) {
        Node cur = array[i];
        while(cur != null){
            int newIndex = cur.key % newArray.length;
            Node curN = cur.next;
            cur.next = newArray[newIndex];
            newArray[newIndex] = cur;
            cur = curN;
        }
    }
    array = newArray;
}

注意：这里的 DEFAULT_LOAD_FACTOR 是在定义在相关变量里的，其完整代码如下。

public static final double DEFAULT_LOAD_FACTOR = 0.75f;

这里我们可以简单进行调试，Test 类代码为：

public class Test {
    public static void main(String[] args) {
        HashBucket hashBucket = new HashBucket();
        hashBucket.push(1, 9);
        hashBucket.push(11, 9);
        hashBucket.push(14, 9);
        hashBucket.push(4, 9);
        hashBucket.push(2, 9);
        hashBucket.push(15, 9);
        hashBucket.push(6, 9);
        hashBucket.push(5, 9);
    }
}

调试的断点放在了第 7 个数的位置，因为再往下走需要进行扩容了，可以看到代码是按照上面的数组 + 链表的方式进行存储的。

然后是扩容的部分。

可以看到，扩容后数组的长度来到 15，证明扩容部分也是可以正常进行的。

getVal 方法

通过 key 的值，来得到 val 值，这部分代码，其实和插入里部分代码有些相同的部分:

通过 key 值来找到数据的位置，如果相同返回 val 值，没找到返回 -1。

public int getVal(int key){
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null) {
        if(cur.key == key){
            return cur.val;
        }
        cur = cur.next;
    }
    return -1;
}

完整代码

public class HashBucket {
    // 定义相关变量
    static class Node {
        public int val;
        public int key;
        public Node next;

        public Node(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }

    public Node[] array = new Node[10];
    public int useSize;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public void push(int key, int val){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //没有找到当前链表中有这个 key 的节点
        //头插法
        Node node = new Node(val, key);
        node.next = array[index];
        array[index] = node;
        useSize++;
        if(doLoadFactor() >= DEFAULT_LOAD_FACTOR){
            //扩容
            resize();
        }
    }

    public void resize(){
        Node[] newArray = new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null){
                int newIndex = cur.key % newArray.length;
                Node curN = cur.next;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curN;
            }
        }
        array = newArray;
    }

    private double doLoadFactor() {
        return useSize*1.0 / array.length;
    }

    public int getVal(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}