性能分析:
散列表中条目数的比例较小时,使用线性探查法的效率较高.
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
}
}
分享到:
相关推荐
散列表有关线性和拉链探查的实验报告包括检索 插入 删除的算法
数据结构基本的操作,作用不大,但是思路清晰,值得一看!
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对关键序列(22,41,53,46,30,01,67)构造哈希表并求等概率情 况下查找成功与不成功过的平均查找长度
【视频】Excel精讲专题-VBA变量
哈希表中线性探查法解决冲突,查找,删除、插入关键字等操作
线性探查法处理散列表中的冲突 二叉树 二叉树的前、中、后序以及层次遍历 支持插入、删除、查找的二叉查找树 查找二叉查找树中的最大、最小节点 查找二叉查找树中某个节点的前驱、后继节点 堆 小顶堆 大顶堆 堆排序 ...
算法 L//线性探查空缺散列表的查找和插入算法//取 K 的散列位置}//检索成功,返回 k 的散列位置 i} //把 K 插入到链表位置 i//检索、插入都不
三、简作题(共10分)假设一个散列表中已装入100个表项并采用线性探查法解决冲突,要求搜索到表中已有表项时的平均搜索次数不超过4,插入表中没有的表项时找到插入位
10.5.3 线性探查 10.5.4 链式散列 10.6 一个应用——文本压缩 10.6.1 LZW压缩 10.6.2 LZW压缩的实现 10.6.3 LZW解压缩 10.6.4 LZW解压缩的实现 10.6.5 性能评价 10.7 参考及推荐读物 第11章 二叉树和其他树 11.1 树 ...
)栈(堆栈)类别(队列)链表(LinkedList)单链表(LinkedList)双链表(Doubly...散列表(哈希表)分离链接(HashCollisionSeparateChaining)线性探查(HashCollisionLinearProbing)托普找第k大的元素(Quick...
leetcode算法题主函数如何写 数据结构 1、如何高效学习数据结构与算法 一、数据结构的存储方式 数据结构的存储方式只有两种:数组(顺序存储)和链表(链式存储)。 这句话怎么理解,不是还有散...线性探查法就需要数