## Thursday, August 11, 2016

### [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]
[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
DEL:od
DEL:do
DEL:wloskiej

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

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();
for (int i = 0; i < m; i++) {
String[] strs = s.split(":");
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;
}

}