12.1.Hashing的引入

发表于 更新于 分类于 ， 阅读次数： 本文字数： 391 阅读时长 ≈ 1 分钟

\(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;
}

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