/****************************/
/* ハッシュ法 */
/* coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;
/*****************************************/
/* クラス List（衝突リスト，二分探索木） */
/*****************************************/
class List
{
String st;
List left, right;
// コンストラクタ
List () { }
List (String s)
{
st = new String(s);
}
/***************************************/
/* データの追加 */
/* dt : Listクラスのオブジェクト */
/* return : =1 : 追加 */
/* =0 : 同じデータが存在 */
/***************************************/
int add(List dt)
{
List lt = this;
int k, sw = -1;
// トップ
if (lt.st == null) {
lt.st = dt.st;
sw = 1;
}
// トップでない
else {
while (sw < 0) {
k = (dt.st).compareTo(lt.st);
// 同じデータがある
if (k == 0)
sw = 0;
// 大きい
else if (k > 0) {
if (lt.right == null) {
lt.right = dt;
sw = 1;
}
else
lt = lt.right;
}
// 小さい
else {
if (lt.left == null) {
lt.left = dt;
sw = 1;
}
else
lt = lt.left;
}
}
}
return sw;
}
/***************************************/
/* データの削除 */
/* st : 文字列 */
/* return : =1 : 削除した */
/* =0 : 削除できなかった */
/***************************************/
int del(String st)
{
List lt, lt1 = this, lt2 = this, dt;
int k, rl = 0, sw = 0;
if (lt2.st != null) {
while (sw == 0 && lt2 != null) {
k = st.compareTo(lt2.st);
// 削除
if (k == 0) {
sw = 1;
if (lt2.right == null) {
// 子供無し
if (lt2.left == null) {
if (rl == 0)
lt2.st = null;
else {
if (rl > 0)
lt1.right = null;
else
lt1.left = null;
}
}
// 右無し
else {
if (rl == 0) {
lt2.st = (lt2.left).st;
lt2.right = (lt2.left).right;
lt2.left = (lt2.left).left;
}
else {
if (rl > 0)
lt1.right = lt2.left;
else
lt1.left = lt2.left;
}
}
}
else {
// 左無し
if (lt2.left == null) {
if (rl == 0) {
lt2.st = (lt2.right).st;
lt2.left = (lt2.right).left;
lt2.right = (lt2.right).right;
}
else {
if (rl > 0)
lt1.right = lt2.right;
else
lt1.left = lt2.right;
}
}
// 左右あり
else {
dt = lt2.left;
if (rl == 0) {
lt = lt2.right;
lt2.st = lt.st;
lt2.right = lt.right;
lt2.left = lt.left;
}
else {
if (rl > 0)
lt1.right = lt2.right;
else
lt1.left = lt2.right;
}
lt1.add(dt);
}
}
}
// 次のデータ
else {
lt1 = lt2;
if (k > 0) {
lt2 = lt2.right;
rl = 1;
}
else {
lt2 = lt2.left;
rl = -1;
}
}
}
}
return sw;
}
/***********************************/
/* データの探索 */
/* st : 文字列 */
/* return : =1 : 見つかった */
/* =0 : 見つからない */
/***********************************/
int search(String st)
{
List lt = this;
int k, sw = 0;
if (lt.st != null) {
while (sw == 0 && lt != null) {
k = st.compareTo(lt.st);
// 見つかった
if (k == 0)
sw = 1;
// 次のデータ
else if (k > 0)
lt = lt.right;
else
lt = lt.left;
}
}
return sw;
}
}
/***********************************/
/* クラス Hash（ハッシュテーブル） */
/***********************************/
class Hash {
private int size; // ハッシュテーブルの大きさ
private List table[]; // 衝突リスト
// ハッシュ関数
// s : 文字列
int hash(String s) throws UnsupportedEncodingException
{
int hash = 0, g;
int i1, len;
byte bs[] = s.getBytes("ASCII");
len = bs.length;
for (i1 = 0; i1 < len; i1++ ) {
hash = (hash << 4) + bs[i1]; // 左に4ビットシフトし文字を加える
g = hash & 0xf0000000; // ビット毎のＡＮＤ
if (g != 0) {
hash ^= g >> 24; // 排他的論理和
hash ^= g;
}
}
hash = hash & 0x7fffffff;
return hash % size;
}
// コンストラクタ
Hash(int sz)
{
int i1;
size = sz;
table = new List [size];
for (i1 = 0; i1 < size; i1++)
table[i1] = new List();
}
// データの追加
// str : データ（文字列）
// return : =1 : 追加
// =0 : 同じデータが存在
int add(String str) throws UnsupportedEncodingException
{
List lt = new List(str);
return table[hash(str)].add(lt);
}
// データの削除
// str : データ（文字列）
// return : =1 : 削除した
// =0 : 削除できなかった
int del(String str) throws UnsupportedEncodingException
{
return table[hash(str)].del(str);
}
// データの探索
// str : データ（文字列）
// return : =1 : 見つかった
// =0 : 見つからない
int search(String str) throws UnsupportedEncodingException
{
return table[hash(str)].search(str);
}
}
/****************/
/* main program */
/****************/
public class Test
{
public static void main (String[] args) throws IOException
{
int i1, k, n = 0, ct = 0, sw;
String st, s[] = new String [100000];
Hash H = new Hash (3000000);
long tm1, tm2, tm3;
Random rn = new Random((long)12345);
System.out.printf("ハッシュ法\n");
tm1 = System.currentTimeMillis();
while (ct < 2000000) {
k = rn.nextInt();
st = Integer.toString(k);
sw = H.add(st);
if (sw > 0) {
ct++;
if (n < 100000) {
s[n] = st;
n++;
}
}
}
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
for (i1 = 0; i1 < n; i1++)
H.search(s[i1]);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
}