12.1.Hashing的引入

\(12.1\)\(Hashing\)的引入

1.\(Hasing\)的引入

  在先前的树结构中,我们实现了对数据的高效查找。但树的使用有以下的限制:

  1. 树需要对象具有可比较性(\(comparable\))。对于某些元素(比如字符串),它们不能进行比较,因此就无法插入\(BST\)中了。
  2. \(BST\)的运行时间为\(\Theta(\log N)\),但我们希望有更优的运行时间。

  假设我们想要实现对整数的查找,我们可以通过检测数组第\(i\)位是否为\(1\),从而得到该整数是否存在。该数据结构如下实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public 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)\)的运行时间。然而,它有以下的问题:

  1. 空间浪费较大。
  2. 不具有普适性。该数据结构只适用于整数。

2.字符串到整数的转换

  以字符串为例,我们可以考虑将字符串按如下的方式转换成一个整数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public 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;
}

  这样,我们就实现了字符串到整数的转换。然而,这并未解决我们提出的问题。