ハッシュ・リストの設計-->線形プローブ
2575 ワード
パフォーマンス分析:
ハッシュリスト中の項目数の割合が小さい、線形探査法を用いる効率が高い.
ハッシュリスト中の項目数の割合が小さい、線形探査法を用いる効率が高い.
package Hash;
import java.nio.BufferOverflowException;
/**
*
* (linear probing)
* @author baby69yy2000
*/
public class LinearProbingHash<T> {
private T[] table;
private int tableCapacity;
private int size;
public LinearProbingHash(int tableSize) {
table = (T[]) new Object[tableSize];
this.tableCapacity = tableSize;
size = 0;
}
public void add(T item) {
int index, origIndex;
index = (item.hashCode() & 0x7FFFFFFF) % tableCapacity;
origIndex = index;
do {
if(table[index] == null) {
table[index] = item;
size++;
return;
}else
index = (index + 1) % tableCapacity;
} while(index != origIndex);
throw new BufferOverflowException();
}
public boolean contains(T item) {
return (find(item) < 0)? false: true;
}
public int size() {
return size;
}
private int find(T item) {
int index, origIndex;
index = (item.hashCode() & 0x7FFFFFFF) % tableCapacity;
origIndex = index;
do {
if(item.equals(table[index]))
return index;
else
index = (index + 1) % tableCapacity;
if(index == origIndex)
return -1;
} while(index != origIndex);
return -1;
}
public String toString() {
int max = tableCapacity - 1;
StringBuffer buf = new StringBuffer();
buf.append("[");
for(int i = 0; i < tableCapacity; i++) {
if(table[i] != null) {
buf.append(table[i]);
if(i < max)
buf.append(", ");
}
}
buf.append("]");
return buf.toString();
}
public static void main(String[] args) {
LinearProbingHash<Integer> lp = new LinearProbingHash<Integer>(10);
lp.add(new Integer(54));
lp.add(new Integer(77));
lp.add(new Integer(94));
lp.add(new Integer(89));
lp.add(new Integer(14));
lp.add(new Integer(45));
lp.add(new Integer(35));
lp.add(new Integer(76));
System.out.println(lp); // [35, 76, 54, 94, 14, 77, 45, 89]
System.out.println(lp.contains(new Integer(45))); // true
System.out.println(lp.size()); // 8
}
}