[SPOJ] HASHIT – Hash it!

http://www.chenguanghe.com/spoj-hashit-hash-it/
http://www.spoj.com/problems/HASHIT/

Your task is to calculate the result of the hashing process in a table of 101 elements, containing keys that are strings of length at most 15 letters (ASCII codes 'A',...,'z'). Implement the following operations:

• find the index of the element defined by the key (ignore, if no such element),
• insert a new key into the table (ignore insertion of the key that already exists),
• delete a key from the table (without moving the others), by marking the position in table as empty (ignore non-existing keys in the table)

When performing find, insert and delete operations define the following function: 
integer Hash(string key),
which for a string key=a1...an returns the value:
Hash(key)=h(key) mod 101, where 
h(key)=19 *(ASCII(a1)*1+...+ASCII(an)*n).
Resolve collisions using the open addressing method, i.e. try to insert the key into the table at the first free position: (Hash(key)+j2+23*j) mod 101, for j=1,...,19. After examining of at least 20 table entries, we assume that the insert operation cannot be performed.

Input

t [the number of test cases <= 100] 
n1 [the number of operations (one per line)[<= 1000] 
ADD:string 
[or] 
DEL:string [other test cases, without empty lines betwee series]

Output

For every test case you have to create a new table, insert or delete keys, and write to the output: 
the number of keys in the table [first line] 
index:key [sorted by indices]

Example

Input:
1
11
ADD:marsz
ADD:marsz
ADD:Dabrowski
ADD:z
ADD:ziemii
ADD:wloskiej
ADD:do
ADD:Polski
DEL:od
DEL:do
DEL:wloskiej


Output:
5
34:Dabrowski
46:Polski
63:marsz
76:ziemii
96:z

题目大意:设计个一个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;

    }

 

}