[SPOJ] HASHIT – Hash it!

原题: http://www.spoj.com/problems/HASHIT/

---

题目大意:设计个一个hash函数, 可以insert, exist 和 delete. 然后通过执行一系列命令, 返回key的数量和table的内容.

---

分析: 这里需要注意的是nextpos的函数需要mod 101,

public class hashit {
    final int mod = 101;
    final int num = 19;
    int count = 0;
    String[] hash = new String[mod];

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        reset();
        int m = in.readInt();
        for (int i = 0; i < m; i++) {
            String s = in.readLine();
            String[] strs = s.split(":");
            if (strs[0].equals("ADD") && !exist(strs[1]))
                insert(strs[1]);
            else if (strs[0].equals("DEL") && exist(strs[1]))
                delete(strs[1]);
        }
        out.printLine(count);
        for (int i = 0; i < mod; i++) {
            if (!hash[i].equals(""))
                out.printLine(i + ":" + hash[i]);
        }
    }

    public boolean exist(String key) {
        for (int i = 0; i < mod; ++i)
            if (hash[i].equals(key))
                return true;
        return false;
    }

    public boolean insert(String key) {
        for (int i = 0; i <= num; i++) {
            if (hash[nextPos(key, i)].equals("")) {
                hash[nextPos(key, i)] = key;
                count++;
                return true;
            }
        }
        return false;
    }

    public void delete(String key) {
        for (int i = 0; i <= num; ++i) {
            if (hash[nextPos(key, i)].equals(key)) {
                hash[nextPos(key, i)] = "";
                count--;
            }
        }
    }

    public int nextPos(String key, int j) {
        return (hash(key) + j * j + 23 * j) % mod;
    }

    public int hash(String key) {
        int ans = 0;
        for (int i = 0; i < key.length(); ++i)
            ans += ((int) key.charAt(i) * (i + 1));
        return (ans * 19) % mod;
    }

    public void reset() {
        for (int i = 0; i < hash.length; i++) {
            hash[i] = "";
        }
        count = 0;
    }

}