漫画 | 什么是散列表（哈希表）？

梦里梦外; 2023-07-02 03:17 17阅读 0赞

创建与输入数组相等长度的新数组，作为直接寻址表。两数之和的期望是Target，将Target依次减输入数组的元素，得到的值和直接寻址表比较，如果寻址表存在这个值则返回；如果不存在这个值则将输入数组中的元素插入寻址表，再进行输入数组中的下一个元素。

再进一步优化可以将输入数组直接作为直接寻址表，控制对应的下标就好，代码如下：

##### Code：直接寻址表 #####

class Solution {
            public int[] twoSum(int[] nums, int target) {
            for (int i = 1; i < nums.length; i++) {
                int temp = target - nums[i];
                for (int j = 0; j < i; j++) {
                    if (temp == nums[j]) return new int[]{j, i};
                }
            }
            return null;
        }
    }

##### 动画：直接寻址表 #####

数组里面每一个槽位放的是8个字节，用于一个指向外部类的引用。这个外部类可以是链表对象，也可以是红黑树对象，都可以存一个或者一个以上的元素，也可以是空链表或空树。散列表在某种意义上需要的数组空间可以比直接寻址表要少的很多。

散列函数是将所有元素的键转换为自然数，自然数的数集是\{0，1，2，……\}。

如果所有元素的键是正整数，最常用的方法是求模（除留余数法）。我们选择长度为素数M的数组，对于任意正整数k，计算k mod M求得余数；

如果所有元素的键是浮点数，我们将它表示为二进制数，忽略小数点再转化为十进制，然后求模；

如果所有元素的键是字符串，可以将它字符串里面的每一个字符通过ASCII码转换，并相加得到这个字符串的hash，然后求模；

如果所有元素的键是对象或者组合键（对象里面的是属性类型不定），也可以通过上面的方法混合起来。

除了线性探测法，还有二次探测还有双重探测。

线性探测法是，通过散列函数得到散列值，检查这个散列值是否被占用，如果被占用，将索引增大，到达数组结尾时折回数组的开头，直到找到没有被占用的散列值。

线性探测采用的散列函数为：

其中h\`(k)是第一次通过散列函数得到的散列值。

二次探测采用的散列函数为：