創(chuàng)建于20170308
原文鏈接：https://leetcode.com/articles/hash-table/

1 把數(shù)組作為一個(gè)容器

private static void printFreq(char[] str) {
    int[] freq = new int[256];
    for (int i = 0; i < str.length; i++) {
        freq[str[i]]++;
    }
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            System.out.println("[" + (char)(i) + "] = " + freq[i]);
        }
    }
}

public static void main(String[] args) {
    char[] str = "Hello world".toCharArray();
    printFreq(str);
}

這里其實(shí)是把數(shù)組的索引下標(biāo)作為一個(gè)hash值，ASCII 取值范圍0~255。每一個(gè)ASCII 都對(duì)應(yīng)一個(gè)數(shù)字，正好可以作為數(shù)組的下標(biāo)。因此O(1)的時(shí)間，即可從數(shù)組中定位。

如果是小寫(xiě)字母，則26個(gè)字母只需要26長(zhǎng)度的數(shù)組。通過(guò)hash函數(shù)計(jì)算出字母對(duì)應(yīng)的下標(biāo)。如：

index=str[i] - 'a'

2 使用HASH表

A better method is to use a hash table, in Java it's called HashMap, in C++ it's called unordered_map, and in Python it's called dict.

我一般用python的dict實(shí)現(xiàn)。