12.1.Hashing的引入
\(12.1\)\(Hashing\)的引入
1.\(Hasing\)的引入
在先前的树结构中,我们实现了对数据的高效查找。但树的使用有以下的限制:
- 树需要对象具有可比较性(\(comparable\))。对于某些元素(比如字符串),它们不能进行比较,因此就无法插入\(BST\)中了。
- \(BST\)的运行时间为\(\Theta(\log N)\),但我们希望有更优的运行时间。
假设我们想要实现对整数的查找,我们可以通过检测数组第\(i\)位是否为\(1\),从而得到该整数是否存在。该数据结构如下实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14public class DataIndexedIntegerSet {
private boolean[] present;
public DataIndexedIntegerSet() {
present = new boolean[2000000000];
}
public void add(int x) {
present[i] = true;
}
public boolean contains(int x) {
return present[i];
}
该数据结构的查找与插入都只需要\(\Theta(1)\)的运行时间。然而,它有以下的问题:
- 空间浪费较大。
- 不具有普适性。该数据结构只适用于整数。
2.字符串到整数的转换
以字符串为例,我们可以考虑将字符串按如下的方式转换成一个整数:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static int letterNum(String s, int i) {
/** Converts ith character of String to a letter number.
* e.g. 'a' -> 1, 'b' -> 2, 'z' -> 26 */
int ithChar = s.charAt(i)
if ((ithChar < 'a') || (ithChar > 'z')) {
throw new IllegalArgumentException();
}
return ithChar - 'a' + 1;
}
public static int englishToInt(String s) {
int intRep = 0;
for (int i = 0l i < s.length(); i += 1) {
intRep = intRep * 26;
intRep += letterNum(s, i);
}
return intRep;
}
这样,我们就实现了字符串到整数的转换。然而,这并未解决我们提出的问题。