欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

散列

程序员文章站 2022-03-15 21:12:25
...

散列的解释:

将元素通过一个函数转换为整数,使该整数可以尽量唯一地代表这个元素。

如果元素在转换前为key,那么转换后就是一个整数H(key).


key是整数的情况下:

1、直接定址法

     直接把key作为数组下标(或是线性变换  H(key)=a*key+b)

2、除留取余法

     把key除以一个数mod得到的余数作为hash值的方法

     即: H(key) = key % mod

     

字符串hash:

是指将一个字符串c映射为一个整数,使得该整数可以尽可能唯一地代笔字符串c

例子:

public class Main {

	static int hashFun(char c[]) {
		int id = 0;
		int len = c.length;
		for (int i = 0; i < len; i++) {
			if (c[i] >= 'A' && c[i] <= 'Z')
				id = id * 62 + (c[i] - 'A' + 1);
			else if (c[i] >= 'a' && c[i] <= 'a')
				id = id * 62 + (c[i] - 'a' + 1) + 26;
			else if (c[i] >= '0' && c[i] <= '9')
				id = id * 62 + (c[i] - '0' + 1) + 52;
		}
		return id;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.next();
		char[] c = s.toCharArray();
		int n = hashFun(c);
		System.out.println(n);

	}
}

这样可以保证每个字符串的id都不一样


问题:给出N个字符串(由三位或以下的大写字母组成),再给出M个查询字符串,

          问每个查询字符串在N个字符串中出现的次数。

解:

public class Main {

	static int hashFun(char c[]) {
		int id = 0;
		int len = c.length;
		for (int i = 0; i < len; i++)
			id = id * 26 + (c[i] - 'A' + 1);
		return id;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int max = 26 * 26 * 26;
		int[] a = new int[max];
		for (int i = 0; i < n; i++) {
			int id = hashFun(in.next().toCharArray());
			a[id]++;
		}
		int m = in.nextInt();
		for (int i = 0; i < m; i++) {
			String s = in.next();
			char[] c = s.toCharArray();
			int id = hashFun(c);
			System.out.println(s + ":" + a[id]);
		}
	}
}
相关标签: Java