哈希表概述①力扣945——数据结构筑基

---

闭散列表

闭散列称之为开放地址法，是在线性存储空间上的解决方案，若发生冲突后，采用冲突处理方法来在线性空间上探测其他的位置。

hash'(key) = (hash(key) + d) % m
1

这里，hash(Key)是原始散列函数，hash′(key)是探测函数，d是增量序列，m是表长。

这里仅仅只是比较了关键增量序列，指的是hash(key)这个位置发生冲突需要从该位置往前移动的距离。
另根据增量序列的差异，开发地址方法还分为：线性探测法、二次探测法等等。
对于线性探测，增量序列就是1，2，…，m - 1，设定当前发生冲突的位置就是pos，线性探测的下一个考察的位置如下所示：

pos = (pos + 1) % sizetable;
1

闭散列也存在如下的问题；

• 容易产生堆积问题。

堆积问题：由于同义词之间冲突产生了探查序列和非同义词之间冲突导致产生的探查序列互相交织，延长了搜索到下一个空位的时间，导致搜索性能下降。

• 需要额外的字段来保存节点的状态，记录数据是被删除的而不是空白的，下次查找的时候继续向后走。

---

题目——使数组唯一的最小增量

题目链接：力扣945题。

---

思路①

• 数组排序，利用Java API Arrays.sort。
• 再次遍历数组元素，若当前元素小于等于前一个元素，则将其变为前一个元素 +1

①代码

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int move = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i - 1]) {
                int pre = nums[i];
                nums[i] = nums[i - 1] + 1;
                move += nums[i] - pre;
            }
        }
        return move;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路②——线性探测法O(N)（包含路径压缩）

可以把原数组映射到一个地址不冲突的区域，映射后的地址不能小于原数组对应的元素。

例如，[3, 2, 1, 2, 1, 7]可以映射成为[3, 2, 1, 4, 5, 7]。
类似解决hash冲突的线性探测法；若地址存在冲突，则探测下一个位置，若下一个位置存在冲突，继续向后面探测，直至为空位。

• 关键点：直接线性探测会导致时间复杂度过高，可以考虑探测过程中利用路径压缩。
• 路径压缩：经过某条路径会最终探测到一个空位置x后，这条路径上的数值都会变成空位置所在的下标x，设定下次探测的点是该路径上的点，则可以直接跳转这次探测的空位置x，从x继续开始探测。

②代码

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        if (A.empty()) return 0;
        int res = 0;
        // -1表示空位
        vector<int> pos(80000, -1); 
        // 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
        for (int a: A)
        {
            int b = findPos(a, pos);
            res += b-a;
        }
        return res;
    }
    // 线性探测寻址(状态压缩)
    int findPos(int a, vector<int> &pos)
    {
        int b = pos[a];
        // a对应的位置pos[a]是空位，直接放入
        if (b==-1)
        {
            pos[a] = a;
            return a;
        }
        // 向后寻址
        b = findPos(b+1, pos);
        pos[a] = b;
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

开散列表

开散列表的方案就是建立一个邻接表的结构，以哈希函数的数值域作为邻接表的表头数组。映射之后的数值相同的原始信息放到同一个桶对应的链表中，插入到相应的表头之上。

邻接表

邻接表可以看成带有索引数组的多个数据链表。索引数组称为表头数组，其中每一项指向一个数据链表的表头。

邻接表中的数据天然地被分为若干类，每一类的数据在一个链表中。

这里的表头数组和数据链表均可以根据插入删除以及查询的需要选择用动态数组或链表实现。

开散列表

在用邻接表实现的开散列表中。表头数组用数组实现。没有插入删除操作，支持快速查询(随机访问)。数据链表用链表实现。支持快速插入删除，链表比较长的时候查询性能弱。

相当于在哈希表每一个节点持有一个链表，某个数据项对的关键字还是像通常一样映射到哈希表的节点中，而数据项本身插入到节点持有的链表中。发生冲突时，在链表后面追加数据。

开散列也是有缺点的：存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型，哈希表的跳转访问会带来额外的时间开销。