Java 哈希表原理与实现

哈希表

概念

哈希表是一种理想的从顺序表以及平衡树中查找元素的方式，它可以不经过任何比较，一次直接从表中得到想要搜索的元素。如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

• **插入元素：**根据待插入元素的关键码，根据函数计算出存储位置并进行存放
• **搜索元素：**对元素的关键码进行计算，把求得的数据当作元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该种方法即为哈希 (散列) 方法，哈希方法中使用的转换函数称为哈希 (散列) 函数，构造出来的结构称为哈希表。

例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity 为存储元素底层空间总的大小。

上面这种存放元素的方式，不用多次进行关键码的比较，搜索速度比较快。但是，如果集合里再添加一个 14，那么 14 应该放在哪里呢？这里便是要提到冲突。

---

冲突

对于两个数据元素的关键字 $k_1$ 和 $k_2$ ($i \neq j$)，有 $k_1 \neq k_2$，但有：Hash($k_1$) == Hash($k_2$)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为'同义词'。

对于冲突，我们要认识到：

由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

引起哈希冲突的一个原因可能是：**哈希函数设计不够合理。**哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

常见的哈希函数有：

• 直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。优点是简单、均匀。缺点是需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况
• 除留余数法：设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
• 负载因子调节，这个下面会重点讲解

其他的方法还有：平方取中法、折叠法、随机数法、数学分析法等，感兴趣的话可以了解一下。

---

负载因子调节

产生冲突的概率叫做冲突率，已知哈希表中已有的关键字个数是不变的，那么我们能调整的就只有哈希表中的数组的大小。

Java 中负载因子的值为 0.75，即当 填入表中的元素个数 / 散列表的长度 > 0.75 时，产生冲突的概率会很大，这时候我们就要来解决冲突。

---

冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列。

**闭散列：**当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把 key 存放到冲突位置中的'下一个'空位置中去。

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

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

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

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

---

哈希桶的实现

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

// 定义相关变量
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;
    }
}