多元组作为哈希表的键

有时候我们需要在集合中存储一个元素的二维坐标，我们不需要自己定义二元组存储，我们可以：

只存储第几个格子即可：i*n+j
将各种参数组合成独一无二的 String 来作为 Key："12,23,24" 或 "a=1,b=2,c=3"。如需分离，可使用 string.split(regex) 函数进行分离。

离散化

离散化是一种数据处理的技巧，本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

被离散化的可以是大整数、浮点数、字符串等等。

偏序与全序

设 R 为非空集合 S 上的关系，如果 R 是自反、反对称和传递的关系，则称 R 为 S 上的偏序关系，简称偏序，记作 $\preceq$ 。「大于或等于 $\ge$ 」关系是整数集合上的偏序。

如果 a $\preceq$ b 或 b $\preceq$ a，偏序集<S, $\preceq$ >中的元素 a 和 b 称为可比的。

如果<S, $\preceq$ >是偏序集，且 S 中的每对都是可比的，则 S 称为全序集或线序集，且 $\preceq$ 称为全序或线序。

简单来说，离散化后的数，它们之间的大小关系不变。

离散化案例

例 1：100 200 300 200 100 200
离散化：1 2 3 2 1 2

例 2：123456 123456 123456
离散化：1 1 1

实现方式

相同的元素离散化为相同的数据

通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据。

方法：

创建原数组的副本。
将副本中的值从小到大排序。
将排序好的副本去重。
查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值。

基本功练习：

🟩 26. 删除有序数组中的重复项 - 力扣（LeetCode）：题目条件苛刻的时候离散化需要原地去重
🟩 704. 二分查找 - 力扣（LeetCode）：二分查找算法练习。推荐看这篇：站内文章为什么二分查找总是写不对？

参考实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
        }

        long[] dup = Arrays.copyOf(arr, n);
        Arrays.sort(dup);
        int m = unique(dup);

        for (long e: arr) {
            int ans = b(m, dup, e);
            System.out.print((ans + 1) + " ");
        }
    }

    // 二分查找
    public static int b(int m, long[] nums, long k) {
        int l = 0, r = m - 1;
        int mid;
        while (l <= r) {
            mid = (r - l) / 2 + l;
            if (k == nums[mid]) return mid;
            if (k < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    // 有序数组去重
    public static int unique(long[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int i = 1, j = 1;
        for (; j < nums.length; j++) {
            if (nums[i - 1] != nums[j]) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
}

相同的元素根据输入顺序离散化为不同的数据

根据题目要求，有时候会把相同的元素根据输入顺序离散化为不同的数据。方法：

创建原数组的副本，同时记录每个元素出现的位置。
将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序。
将离散化后的数字放回原数组。

复杂度分析

步骤	相同的元素离散化为相同的数据	相同的元素根据输入顺序离散化为不同的数据
去重	$O(n)$	-
排序	$O(n\log n)$
查找	$O(n)$ 次查找，二分查找 $O(\log n)$	-
时间复杂度	$O(n\log n)$
空间复杂度	$O(n)$

粗糙的哈希

我们还可以自己实现简单字符串的哈希算法。

不同哈希算法的粗略分析

下面列举出的算法是在通过例题 🟨 3137. K 周期字符串需要的最少操作次数 - 力扣（LeetCode）前提下，对计算时间和复杂性权衡后的结果。

Hash 算法	时间 (ms)	内存 (MB)	时间击败比率 (%)
简易位运算 Hash	23	45.2	100
简易乘法 Hash	28	45.2	88.37
Java Map `hash()`	43	44.85	11.63

// 乘法 Hash
public int genHash(char[] cc,int start,int length){
	int hash=0,i;
	for (hash=length, i=0; i<length; ++i)
	   // 推荐的乘数还有：31, 131, 1313, 13131, 131313等等。
	   hash = 33*hash+cc[start+i]; 
	return hash;
}

// 位运算 Hash
public int genHash(char[] cc,int start,int length){
	int hash,i;
	for (hash=length, i=0; i<length; ++i)
	   hash = (hash<<5)^(hash>>27)^cc[i+start];
	return hash;
}